Skip to main content
edited tags
Link
Source Link

Dense vertex-symmetric graphs with high girth

I am looking for existing constructions of vertex-symmetric graphs on $n$ nodes that have a girth at least $g$ and are dense, i.e., have at least $n^{1 + \epsilon}$ edges, where $\epsilon>0$ may depend on $g$: in particular, if $g = O(1)$, then $\epsilon$ must be a constant bounded away from $0$ (w.r.t. $n$).

I am aware of Cayley graphs, which are vertex-transitive, but I did not find any high-girth constructions that give dense graphs.