Tamas Heger:
Generalized polygons as extremal graphs
Abstract:
The girth of a graph is the length of the shortest cycle in it. An old
question of extremal graph theory is to determine the least number of
vertices a k regular graph of girth g may have. The incidence graphs of
generalized n-gons of order (q,q) are well-known to be the extremal examples
in case of g=2n and k=q+1. Generalized quadrangles and hexagons are usually
constructed using quadratic surfaces of projective spaces. In the talk we
present some graph constructions of various authors and exhibit their
connections to generalized polygons.
Some references:
R. Wenger: Extremal graphs with no C^4's, C^6's, or C^10's. JCT B v52 (1991)
F. Lazebnik, V.A. Ustimenko, A.J. Woldar: Upper bounds on the order of
cages. Electronic J. Comb. v4(2) (1997)
F. Lazebnik, A.J. Woldar: Geenral properties of some families of graphs
defined by systems of equations. J Graph Theory 38(2) (2001)
V. Dmytrenko, F. Lazebnik, J. Williford: On monomial graphs of girth eight.
FFA v13(4) (2007)