On kk-pairable regular graphs

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