Graffiti's average-distance lower bound for the independence number

About 3 years old · traced to

Let GG be a graph, let α(G)\alpha(G) be its independence number, and let dˉ\bar d be the average distance between distinct vertices of GG. Graffiti's average-distance conjecture.

α(G)≥dˉ\alpha(G) \geq \bar d

The paper verifies this bound for several graph classes considered there, using dˉ≤3≤α(G)\bar d\leq 3\leq\alpha(G), but the conjecture is attributed to Graffiti and is not resolved in the source.

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.