Maximum diameter of redundant non-surrounded graphs

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

log2(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.

Sources & referencesView supporting material

Primary source

Andrew Steane, “Distance-critical and distance-redundant graphs”, arXiv:2403.16197 (2024).

Additional references

2 papers in this index state this conjecture (2017–2024). The statement above is taken from the most recent of them; the others are arXiv:1709.03974.

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.