On the excess of vertex-transitive graphs of given degree and girth

We consider the problem of finding the smallest vertex-transitive k-regular graphs of girth g. Counting cycles and using number theory’s theorems we extend Biggs’s result proving that the asymptotic density of the set of all odd girths g for which exists a vertex-transitive (k,g)-cage with excess not exceeding e is 0. Also, we consider the existence of (k,g)-vertex-transitive graphs when g is even and the excess is 4 or smaller than min{k-2,g}.

Based on joint work with Robert Jajcay.