Sharp bounds on the size of pairable graphs and pairable bipartite graphs

The k-pairable graphs, introduced by Chen in 2004, constitute a wide class of graphs with a new type of symmetry, which includes many graphs of theoretical and practical importance, such as hypercubes, Hamming graphs of even order, antipodal graphs (also called diametrical graphs, or symmetrically even graphs), S-graphs, etc. Let k be a positive integer. A connected graph G is said to be k-pairable if the automorphism group of G contains an involution φ with the property that the distance between x and φ(x) is at least k for any vertex x of G. The pair length of G is k if G is k-pairable but not (k + 1)-pairable. It is known that any graph of pair length k > 0 has even order at least 2k. In this paper, we give sharp bounds for the size of a graph G of order n and pair length k for any integer k > 0 and any even integer n ≥ 2k, when G is bipartite and when G is not restricted to be bipartite, respectively.