Graffiti's radius lower bound for the independence number

At least 2 years old · documented by

Let GG be a graph, let α(G)\alpha(G) be its independence number, and let r(G)r(G) be its graph radius. Graffiti's radius conjecture.

α(G)≥r(G)\alpha(G) \geq r(G)

The source verifies the intended bound for the listed graph classes from r(G)≤diam⁡(G)≤3≤α(G)r(G)\leq\operatorname{diam}(G)\leq 3\leq\alpha(G), but does not state that Graffiti's conjecture is solved in general.

References

Primary source

Boris Brimkov and Valentin Brimkov, “Graphs with degree sequence \m^m-1,n^n-1\ and \m^n,n^m\”, arXiv:2308.06670 (2023).

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.