Moore graph extremality conjecture for the connected-set growth constant
Let denote the exponential growth constant for the maximum number of connected vertex subsets among -regular graphs of order . A Moore graph is a -regular graph of a given girth that attains the theoretical lower bound, the Moore bound, on its order. If is a -regular Moore graph of order , then Moore graph extremality conjecture. For every ,
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 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
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.