On k-pairable regular graphs

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.