On k-pairable graphs from trees

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11-15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p(G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p(G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees G with p(G) = 1 and prove that p(G □ H) = p(G) + p(H) when both G and H are trees.

Original languageEnglish (US)
Pages (from-to)377-386
Number of pages10
JournalCzechoslovak Mathematical Journal
Issue number1
StatePublished - Mar 2007

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'On k-pairable graphs from trees'. Together they form a unique fingerprint.

Cite this