Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 3334-3350 |
Number of pages | 17 |
Journal | Discrete Mathematics |
Volume | 310 |
Issue number | 23 |
DOIs | |
State | Published - Dec 6 2010 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics