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.

Back to all abstracts