Premium
Regular graphs constructed from the classical generalized quadrangle Q (4, q )
Author(s) -
Beukemann L.,
Metsch K.
Publication year - 2011
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20266
Subject(s) - mathematics , quadrangle , valency , combinatorics , prime power , graph , girth (graph theory) , strongly regular graph , prime (order theory) , order (exchange) , discrete mathematics , graph power , line graph , philosophy , linguistics , archaeology , finance , economics , history
Let c k be the smallest number of vertices in a regular graph with valency k and girth 8. It is known that c k + 1 ⩾ 2 ( 1 + k + k 2 + k 3 ) with equality if and only if there exists a finite generalized quadrangle of order k . No such quadrangle is known when k is not a prime power. In this case, small regular graphs of valency k + 1 and girth 8 can be constructed from known generalized quadrangles of order q > k by removing a part of its structure. We investigate the case when q = k + 1 is a prime power, and try to determine the smallest graph under consideration that can be constructed from a generalized quadrangle of order q . This problem appears to be much more difficult than expected. We have general bounds and improve these for the classical generalized quadrangle Q ( 4 , q ), q even. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:70‐83, 2010