| Title:
|
On $k$-pairable graphs from trees (English) |
| Author:
|
Che, Zhongyuan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
57 |
| Issue:
|
1 |
| Year:
|
2007 |
| Pages:
|
377-386 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
$k$-pairable graph |
| Keyword:
|
pair length |
| Keyword:
|
Cartesian product |
| Keyword:
|
$G$-layer |
| Keyword:
|
tree |
| MSC:
|
05C05 |
| MSC:
|
05C60 |
| MSC:
|
05C75 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 1174.05106 |
| idMR:
|
MR2309971 |
| . |
| Date available:
|
2009-09-24T11:46:19Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128177 |
| . |
| Reference:
|
[1] Z. Chen: On $k$-pairable graphs.Discrete Math. 287 (2004), 11–15. Zbl 1050.05026, MR 2094052, 10.1016/j.disc.2004.04.012 |
| Reference:
|
[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. MR 1289277, 10.2307/2974696 |
| Reference:
|
[3] W. Imrich, S. Klavžar: Product Graphs: Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization.Wiley, Chichester, 2000. MR 1788124 |
| . |
