Regular graphs constructed from the classical generalized quadrangle Q (4, q )

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