On k-pairable regular graphs

Zhongyuan Che, Zhibo Chen

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Let k be a positive integer. A graph G is said to be k-pairable if its automorphism group contains an involution φ such that d(x,φ(x))<k for any vertex x of G. The pair length of a graph G, denoted as p(G), is the maximum k such that G is k-pairable; p(G)=0 if G is not k-pairable for any positive integer k. Some new results have been obtained since these concepts were introduced by Chen [Z. Chen, On k-pairable graphs, Discrete Mathematics 287 (2004) 1115]. In the present paper, we first introduce a new concept called strongly induced cycle and use it to give a condition for a graph G to have p(G)=k. Then we consider the class G(r,k) of prime graphs which are r-regular and have pair length k. For any integers r,k<2, except r=k=2, we show that the set G(r,k) is not empty, determine the minimum order of a graph in G(r,k), and give a construction for such a graph with the minimum order. With this approach, we also obtain the minimum order of an r-regular graph with pair length k for any integers r,k<2. Finally, we post an open question for further research.

Original languageEnglish (US)
Pages (from-to)3334-3350
Number of pages17
JournalDiscrete Mathematics
Issue number23
StatePublished - Dec 6 2010

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this