The problem is motivated by generalizing Moore graphs, graphs with maximum possible girth ($2\text{diam}+1$) given the diameter.

Question. Does there exist a graph $G$ with $\text{g}(G)-\text{diam}(G)>8$ and minimum degree at least $3$, where $\text{g}(G)$ and $\text{diam}(G)$ are the girth and diameter of $G$, respectively?

Remark. There's an infinite class of graphs with $\text{g}(G)-\text{diam}(G)=8$: the (point,line) incidence graphs of generalized octagons have $\text{g}(G)=16$ and $\text{diam}(G)=8$.

Bonus points (+200 bounty) for a proof that $\text{g}-\text{diam}$ is unbounded for graphs with minimum degree at least $3$.

  • 1
    $\begingroup$ Have you checked any of the cubic cages in here for whether they give you examples? $\endgroup$ – M. Winter Mar 20 '20 at 9:38
  • $\begingroup$ Maybe relevant: mathoverflow.net/q/145045 $\endgroup$ – M. Winter Mar 20 '20 at 9:46
  • $\begingroup$ The graphs of girth 19, 20 and 22 have diameters 14, 15 and 16 respectively. The graph of girth 21 is missing. $\endgroup$ – LeechLattice Mar 20 '20 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.