Abstract
Motivated by a 1994 result of Graham et al. (Amer. Math. Monthly 101(7) (1994) 664) about spanning trees of the graphs with an antipodal isomorphism, we introduce the concept of k-pairable graphs and extend the result in Graham et al. (Amer. Math. Monthly 101(7) (1994) 664) to this larger class of graphs. We then define a new graph parameter p(G), called the pair length of graph G. This parameter measures the maximum distance, in some sense, between a subgraph induced by half the vertices of G with the isomorphic subgraph induced by the other half of V(G). An upper bound for the parameter p(G) is given. Some properties of the k-pairable graphs and their product graphs are studied. We also post some problems for further research.
Original language | English (US) |
---|---|
Pages (from-to) | 11-15 |
Number of pages | 5 |
Journal | Discrete Mathematics |
Volume | 287 |
Issue number | 1-3 |
DOIs | |
State | Published - Oct 28 2004 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics