$k$-pairable graph; pair length; Cartesian product; $G$-layer; tree
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 \square H)=p(G)+p(H)$ when both $G$ and $H$ are trees.
 N. Graham, R. C. Entringer, L. A. Székely: New tricks for old trees: maps and the pigeonhole principle
. Amer. Math. Monthly 101 (1994), 664–667. DOI 10.2307/2974696
| MR 1289277
 W. Imrich, S. Klavžar: Product Graphs: Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization
. Wiley, Chichester, 2000. MR 1788124