TY - JOUR

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

AU - Che, Zhongyuan

AU - Chen, Zhibo

N1 - Publisher Copyright:
© 2015, University of Queensland. All rights reserved.

PY - 2015/7/24

Y1 - 2015/7/24

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84937879427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937879427&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84937879427

SN - 1034-4942

VL - 62

SP - 172

EP - 183

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

IS - 2

ER -