ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a graph of order nn in which every vertex is redundant and no vertex is surrounded. Its diameter is the graph distance between vertices at maximum distance.

Maximum-diameter conjecture. The maximum diameter of such a graph is

⌊log⁡2(n)⌋;\left\lfloor \log_2(n)\right\rfloor;

when nn is a power of 22, this maximum is attained only by the kk-cube and by graphs containing the kk-cube as a subgraph.

The kk-cube is given in the surrounding text as an example with 2k2^k vertices, diameter kk, all vertices redundant, and no surrounded vertices. The supplied text does not establish the asserted upper bound or the uniqueness claim.

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.