ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.