Premium
On the mean subtree order of trees under edge contraction
Author(s) -
Luo Zuwen,
Xu Kexiang,
Wagner Stephan,
Wang Hua
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22885
Subject(s) - combinatorics , mathematics , conjecture , order (exchange) , tree (set theory) , enhanced data rates for gsm evolution , upper and lower bounds , path (computing) , computer science , mathematical analysis , telecommunications , finance , economics , programming language
For a treeT $T$ , the mean subtree order ofT $T$ is the average order of a subtree ofT $T$ . In 1984, Jamison conjectured that the mean subtree order ofT $T$ decreases by at least 1/3 after contracting an edge inT $T$ . In this article we prove this conjecture in the special case that the contracted edge is a pendant edge. From this result, we have a new proof of the established fact that the pathP n${P}_{n}$ has the minimum mean subtree order among all trees of ordern $n$ . Moreover, a sharp lower bound is derived for the difference between the mean subtree orders of a treeT $T$ and a proper subtreeS $S$ (ofT $T$ ), which is also used to determine the tree with second‐smallest mean subtree order among all trees of ordern $n$ .