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

✍ Scribed by L. Beukemann; K. Metsch

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 144 KB
• Volume: 19
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20266

✦ Synopsis

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.