Connected-graph contraction conjecture for mean subtree order
Connected-graph contraction conjecture for mean subtree order
Let be a connected graph and let . Write for the graph obtained by contracting , and let denote mean subtree order.
Connected-graph contraction conjecture. Contracting any edge should reduce the mean subtree order by at least , with equality only for a path:
with equality if and only if is a path. The source presents this as a proposed generalisation of the proved tree case and says that proving it would imply the path-minimum result.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.