On k-pairable graphs

Zhibo Chen

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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 languageEnglish (US)
Pages (from-to)11-15
Number of pages5
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Oct 28 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On k-pairable graphs'. Together they form a unique fingerprint.

Cite this