Moore graph extremality conjecture for the connected-set growth constant

About 11 years old · traced to

Let cd(n)c_d(n) denote the exponential growth constant for the maximum number of connected vertex subsets among dd-regular graphs of order nn. A Moore graph is a dd-regular graph of a given girth that attains the theoretical lower bound, the Moore bound, on its order. If GG is a dd-regular Moore graph of order nn, then Moore graph extremality conjecture. For every n′>nn'>n,

cd(n′)<cd(n)=cd(G).c_d(n')<c_d(n)=c_d(G).

The conjecture asserts that Moore graphs are extremal and that increasing the order beyond a Moore graph strictly lowers the corresponding growth constant. The paper notes that exact extremal graphs are difficult to describe in general and that cd(n)c_d(n) is not monotone decreasing, so the claim is a specific strict comparison after an order attained by a Moore graph; no resolution is supplied.

References

Primary source

Stijn Cambie, Jan Goedgebeur and Jorik Jooken, “The maximum number of connected sets in regular graphs”, arXiv:2311.00075 (2024).

Additional references

3 papers in this index state this conjecture (2015–2023). The statement above is taken from the most recent of them; the others are arXiv:1611.01474, arXiv:1503.00157.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.