## 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