Abstract
For a tree (Formula presented.), the mean subtree order of (Formula presented.) is the average order of a subtree of (Formula presented.). In 1984, Jamison conjectured that the mean subtree order of (Formula presented.) decreases by at least 1/3 after contracting an edge in (Formula presented.). 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 path (Formula presented.) has the minimum mean subtree order among all trees of order (Formula presented.). Moreover, a sharp lower bound is derived for the difference between the mean subtree orders of a tree (Formula presented.) and a proper subtree (Formula presented.) (of (Formula presented.)), which is also used to determine the tree with second-smallest mean subtree order among all trees of order (Formula presented.).
Original language | English |
---|---|
Pages (from-to) | 535-551 |
Number of pages | 17 |
Journal | Journal of Graph Theory |
Volume | 102 |
Issue number | 3 |
DOIs | |
State | Published - Mar 2023 |
Scopus Subject Areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- edge contraction
- mean subtree order
- subtree
- tree