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

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.