On k-pairable graphs from trees
Zhongyuan Che · Czechoslovak Mathematical Journal · 2007
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.