Geodesic
On $k$-pairable graphs from trees
Czechoslovak Mathematical Journal, Tome 57 (2007) no. 1, pp. 377-386 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C05, 05C60, 05C75, 68R10
Keywords: $k$-pairable graph; pair length; Cartesian product; $G$-layer; tree 
@article{CMJ_2007_57_1_a27,
     author = {Che, Zhongyuan},
     title = {On $k$-pairable graphs from trees},
     journal = {Czechoslovak Mathematical Journal},
     pages = {377--386},
     year = {2007},
     volume = {57},
     number = {1},
     mrnumber = {2309971},
     zbl = {1174.05106},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2007_57_1_a27/}
}
TY  - JOUR
AU  - Che, Zhongyuan
TI  - On $k$-pairable graphs from trees
JO  - Czechoslovak Mathematical Journal
PY  - 2007
SP  - 377
EP  - 386
VL  - 57
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_2007_57_1_a27/
LA  - en
ID  - CMJ_2007_57_1_a27
ER  - 
%0 Journal Article
%A Che, Zhongyuan
%T On $k$-pairable graphs from trees
%J Czechoslovak Mathematical Journal
%D 2007
%P 377-386
%V 57
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2007_57_1_a27/
%G en
%F CMJ_2007_57_1_a27
Che, Zhongyuan. On $k$-pairable graphs from trees. Czechoslovak Mathematical Journal, Tome 57 (2007) no. 1, pp. 377-386. http://geodesic.mathdoc.fr/item/CMJ_2007_57_1_a27/