The path and clique extremality conjecture for mean subtree order

Let GG be a connected graph of order nn, and let μ(G)\mu(G) denote its mean subtree order. Write PnP_n for the path and KnK_n for the clique on nn vertices.

Mean subtree order extremality conjecture.

μ(Pn)μ(G)with equality if and only if G=Pn,\mu(P_n) \le \mu(G) \quad\text{with equality if and only if }G=P_n,

and

μ(G)μ(Kn)with equality if and only if G=Kn.\mu(G) \le \mu(K_n) \quad\text{with equality if and only if }G=K_n.

The minimum assertion is proved in the paper, while the maximum assertion remains open; thus the full conjecture is not resolved.

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

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.