# Article

Full entry | PDF   (0.2 MB)
Keywords:
\$k\$-pairable graph; pair length; Cartesian product; \$G\$-layer; tree
Summary:
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.
References:
[1] Z.  Chen: On \$k\$-pairable graphs. Discrete Math. 287 (2004), 11–15. DOI 10.1016/j.disc.2004.04.012 | MR 2094052 | Zbl 1050.05026
[2] 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
[3] W.  Imrich, S.  Klavžar: Product Graphs: Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Chichester, 2000. MR 1788124

Partner of