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 - Sep 12 2022 |
Scopus Subject Areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- edge contraction
- mean subtree order
- subtree
- tree