3
$\begingroup$

Is there an infinite class of graphs with diameter 2, girth 5, and minimum degree at least 2?

Girth 5 is necessary, since otherwise complete bipartite graphs are an answer. Minimum degree at least 2 is necessary, since otherwise stars are an answer.

The Hoffman–Singleton graph (which has 60 vertices) is the largest graph I know with the properties in the question.

The question is interesting if "minimum degree at least 2" is replaced by "minimum degree at least 3", but I think it makes little difference because degree 2 vertices are highly restricted in a graph with diameter 2.

This question is related (but different) to the question Girth and diameter of a graph with minimum degree at least 3.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

No infinite family exists. In fact all graphs with diameter $d$ and girth $2d+1$ have to be regular, and thus are Moore graphs. This was proved in

R. Singleton, "There is no irregular Moore graph", Amer. Math. Monthly 75 (1968), 42–43

See also the textbook "Algebraic Graph Theory" by Godsil and Royle (p. 90). It is unknown whether the Hoffman-Singleton graph is the largest Moore graph of girth 5 but if there are more, they have to be of degree 57 and of order 3250, thus there can only be finitely many more.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I don't think it's known that there is at most one Moore graph of degree $57$? $\endgroup$
    – verret
    Commented Oct 4, 2023 at 5:06
  • 1
    $\begingroup$ @verret You are absolutely right. One hears the phrase "the missing Moore graph" so often, it is easy to forget there could be more than one. $\endgroup$
    – Gjergji Zaimi
    Commented Oct 4, 2023 at 5:18
  • $\begingroup$ Thanks Gjergji. $\endgroup$
    – David Wood
    Commented Oct 5, 2023 at 3:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .