Complete-graph extremality conjecture for mean subtree order

Let GG be a graph with nn vertices, and let μ(G)\mu(G) denote its mean subtree order. Let KnK_n be the complete graph on nn vertices.

Complete-graph extremality conjecture. For every graph GG with nn vertices,

μ(G)μ(Kn).\mu(G)\le\mu(K_n).

This is the maximum part of the main extremal problem for mean subtree order. The source identifies it as open.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Jorik Jooken and Stephan Wagner, “On the extrema of the mean subtree order of graphs”, arXiv:2508.20593 (2025).

Additional references

12 papers in this index state this conjecture (2006–2025). The statement above is taken from the most recent of them; the others are arXiv:2502.12291, arXiv:2402.09254, arXiv:2007.03064, arXiv:1907.11328, arXiv:1811.02018, arXiv:1801.01225, arXiv:1610.08370, arXiv:1606.06370, arXiv:1411.0290, arXiv:1003.5444, arXiv:math/0607326.

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.