On the extrema of the mean subtree order of graphs
Stijn Cambie, Jorik Jooken, Stephan Wagner · 2025
Read On the extrema of the mean subtree order of graphs by Stijn Cambie, Jorik Jooken, Stephan Wagner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20593.txt.
Introduction
Stijn Cambie, Jorik Jooken, and Stephan Wagner settled a guess on the mean subtree order of graphs, in a paper from twenty twenty-five. The guess: among linked graphs on n nodes, the path graph gives the least mean subtree order and the full clique gives the most. They grow tricks of Haslegrave and Vince. The path side falls: the least is in fact reached by the path.
For the most, they show the clique maxes the ratio of spanning to near spanning trees. A double count then seals the clique as the top. Readers in graph theory get both ends of a standing guess closed in one paper.
Catalog record
| CREATOR | Stijn Cambie, Jorik Jooken, Stephan Wagner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20593
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the extrema of the mean subtree order of graphs Stijn Cambie, Jorik Jooken, Stephan Wagner Abstract It has been conjectured that the minimum and maximum of the mean subtree order among connected graphs of order n n are attained by the path P n P_{n} and clique K n K_{n} , respectively. Extending ideas due to Haslegrave and Vince, we confirm that the minimum is indeed attained by P n P_{n} . On the other hand, we discuss different approaches (both promising and flawed) that could lead to a proof of the extremality of K n K_{n} . 1 Introduction The mean subtree order, i.e., the average order of the subtrees of a tree, was first studied by Jamison about 40 years ago, see [ 9 ] and [ 10 ] . The study of the mean subtree order (where a subtree of a graph is any subgraph that is a tree, i.e., not necessarily induced) was extended to arbitrary graphs by Chin, Gordon, MacPhee and Vincent [ 6 ] . The concluding section of [ 6 ] contains a number of open questions and conjectures, most of which have since been addressed, see [ 3 , 12 , 16 ] . The main extremal question concerning the mean subtree order asks for the minimum and maximum values among all connected graphs of given order n . The answer is believed to be as stated below (see for example the introduction in [ 7 ] ). In the following, we write \mu(G) for the mean subtree order of a (connected) graph G . Conjecture 1.1 . Let G be a connected graph of order n . Then (i) \mu(P_{n})\leq\mu(G) with equality if and only if G=P_{n} , (ii) \mu(G)\leq\mu(K_{n}) with equality if and only if G=K_{n} . Let us remark that the restricted version of ( i ) , where G is required to be a tree, was already proven by Jamison [ 9 ] . We combine ideas from [ 8 , 15 ] to prove ( i ) in Section 2 . Theorem 1.2 . Let G be a connected graph of order n . Then \mu(G)\geq\frac{n+2}{3} with equality if and only if G=P_{n}. We further consider a number of conjectures that imply 1.1 ( i ) or ( i i ) , or both (i.e., stronger forms of 1.1 ) and give an overview of some directions that are of independent interest. A first potential approach would be based on adding or removing edges. Let G+e denote the graph G with the edge e added. More generally, for a set of edges M , the graph G+M is the graph with vertex set V(G) and edge set E(G)\cup M . Chin, Gordon, MacPhee and Vincent conjectured that for every two non-adjacent vertices u,v in a graph G , adding the edge e=uv increases the mean subtree order, i.e., \mu(G+e)>\mu(G) (see [ 6 , Conj. 7.4] ). The upper bound ( 1.1 ( i i ) ) would be an easy corollary, and the lower bound ( 1.1 ( i ) ) would follow from Jamison’s result that the path is extremal among trees. However, the conjecture was disproved by Cameron and Mol [ 3 ] , who provided explicit counterexamples. Recently, two groups independently generalised these counterexamples by proving that for every positive integer k , there is a graph and a choice of k edges whose addition decreases the mean subtree order [ 2 , 4 ] . 1 1 1 Here [ 2 ] was submitted first and [ 4 ] was published first. A conjecture presented in the conclusion of [ 4 ] is refuted by one of the examples in [ 2 ] , where it is demonstrated that the mean subtree order can decrease by as much as \frac{1}{3}(1-o(1))n when k edges are added. We provide an even more robust counterexample to the conjecture presented in [ 6 , Conj. 7.4] by proving the following theorem in Section 3 . Theorem 1.3 . There are sparse graphs G of order n for which there is only one edge e up to isomorphism ( o(n) many out of the \Theta(n^{2}) edges in G^{c} ) for which \mu(G+e)>\mu(G) . There are also graphs for which adding any maximal matching M in G^{c} reduces the mean subtree order, i.e., \mu(G+M)<\mu(G) . 1.1 would also be a corollary of the following conjecture 2 2 2 Note that 1.4 ( i i ) has been stated before in [ 3 , Conj. 1.2] . . Here, G\setminus e denotes the graph obtained by deleting the edge e in the graph G . Conjecture 1.4 . Let G be a graph of order n . (i) If G is not a tree, then there exists an edge e\in G such that G\setminus e is connected and \mu(G\setminus e)<\mu(G). (ii) If G\neq K_{n} , then there exist two non-adjacent vertices u,v such that \mu(G+uv)>\mu(G). In Subsection 3.2 we show that both statements are false when the existence is replaced by a “for all” statement. Another direction that would imply 1.1 ( i ) would be a two-step argument in which one proves some monotonicity results analogous to those obtained in [ 10 ] for trees. However, this approach also fails. In Section 4 , we show that analogous monotonicity results do not hold for arbitrary connected graphs. Another interesting direction is related to Jamison’s contraction conjecture. We let G/e denote the graph G with the edge e contracted. Conjecture 1.5 . [ 10 , Conj. 5.6] In a tree T , the contraction of any edge e\in E(T) reduces the mean subtree order by at least \frac{1}{3} ; \mu(T)-\mu(T/e)\geq\frac{1}{3} . This conjecture was proven in [ 13 , 17 ] (with equality if and only if T is a path). It is tempting to generalise the conjecture to arbitrary connected graphs. Conjecture 1.6 . In a connected graph G , the contraction of any edge e\in E(G) reduces the mean subtree order by at least \frac{1}{3} ; \mu(G)-\mu(G/e)\geq\frac{1}{3}, with equality if and only if G is a path. Proving 1.6 would immediately lead to an alternative proof of 1.1 ( i ) . As we will see in Section 4 , it is also sufficient to prove 1.6 in the case that e is a bridge of the graph G. A different direction for a possible proof of 1.1 ( i i ) is the following conjecture on the ratio of spanning trees and subtrees of order n-1 . Let s_{k}(G) denote the number of (not necessarily induced) subtrees of G with k vertices. Conjecture 1.7 . For a graph G of order n , we have s_{n-1}(G)\geq\frac{s_{n-1}(K_{n})}{s_{n}(K_{n})}s_{n}(G). In Section 5 , we formally prove that 1.7 implies 1.1 ( i i ) , and that 1.7 would also imply that K_{n} maximises p(G) , the fraction of subtrees that are spanning ( 5.2 ). We close this section by briefly discussing another generalisation of the study of the mean subtree order of trees. For a graph G=(V,E) , we call a vertex set S\subseteq V connected if G[S] is connected and denote