Large Cayley graphs of given degree and diameter from finite geometries
Jozef Šir\'{a}\v{n}
Slovak University of Technology, Bratislava, Slovakia
Jana Šiagiov\'{a}
Slovak University of Technology, Bratislava, Slovakia
Martin Bachrat\'{y}
Comenius University, Bratislava, Slovakia
PDF
Minisymposium: FINITE GEOMETRY
Content: It has been known that for diameters $k\in \{2,3,5\}$, graphs of diameter $k$ and maximum degree $q+1$ for infinite sets of prime powers $q$ and with orders asymptotically approaching the corresponding Moore bounds can be obtained from generalised triangles, quadrangles and hexagons. These graphs, however, are not vertex-transitive, as they are not even regular. We will show how to use finite geometries to construct {\em Cayley} graphs with the above properties for $k=2$ and $3$; the case $k=5$ still remains open.