On -pairable graphs from trees
Czechoslovak Mathematical Journal (2007)
- Volume: 57, Issue: 1, page 377-386
- ISSN: 0011-4642
Access Full Article
topAbstract
topHow to cite
topChe, Zhongyuan. "On $k$-pairable graphs from trees." Czechoslovak Mathematical Journal 57.1 (2007): 377-386. <http://eudml.org/doc/31135>.
@article{Che2007,
abstract = {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.},
author = {Che, Zhongyuan},
journal = {Czechoslovak Mathematical Journal},
keywords = {$k$-pairable graph; pair length; Cartesian product; $G$-layer; tree; -pairable graph; pair length; Cartesian product; -layer; tree},
language = {eng},
number = {1},
pages = {377-386},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On $k$-pairable graphs from trees},
url = {http://eudml.org/doc/31135},
volume = {57},
year = {2007},
}
TY - JOUR
AU - Che, Zhongyuan
TI - On $k$-pairable graphs from trees
JO - Czechoslovak Mathematical Journal
PY - 2007
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 57
IS - 1
SP - 377
EP - 386
AB - 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.
LA - eng
KW - $k$-pairable graph; pair length; Cartesian product; $G$-layer; tree; -pairable graph; pair length; Cartesian product; -layer; tree
UR - http://eudml.org/doc/31135
ER -
References
top- 10.1016/j.disc.2004.04.012, Discrete Math. 287 (2004), 11–15. (2004) Zbl1050.05026MR2094052DOI10.1016/j.disc.2004.04.012
- 10.2307/2974696, Amer. Math. Monthly 101 (1994), 664–667. (1994) MR1289277DOI10.2307/2974696
- Product Graphs: Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, Chichester, 2000. (2000) MR1788124
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.