10
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ Have you checked any of the cubic cages in here for whether they give you examples? $\endgroup$
    – M. Winter
    Mar 20, 2020 at 9:38
  • 1
    $\begingroup$ Maybe relevant: mathoverflow.net/q/145045 $\endgroup$
    – M. Winter
    Mar 20, 2020 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$ Mar 20, 2020 at 13:51

1 Answer 1

7
$\begingroup$

The recent preprint "A randomized construction of high girth regular graphs" by Linial and Simkin suggests in its closing remarks that the answer (at least, to your bonus question) is unknown:

The possible relation between a graph’s girth and its diameter is particularly intriguing. It follows from [12] and Moore’s bound that $$2 \ge \mathrm{lim\ sup} \frac{\mathrm{girth}(G)}{\mathrm{diam}(G)} \ge 1,$$ where the lim sup ranges over all graphs where all vertex degrees are $\ge 3$. Nothing better seems to be known at the moment. Even more remarkably, we do not know whether $$\mathrm{sup}(\mathrm{girth}(G) − \mathrm{diam}(G))$$ is finite or not. The sup is over all $G$ in which all vertex degrees are $\ge 3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.