On -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) 11–15]. 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.