On the mean subtree order of trees under edge contraction

Zuwen Luo, Kexiang Xu, Stephan Wagner, Hua Wang

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

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 languageEnglish
Pages (from-to)535-551
Number of pages17
JournalJournal of Graph Theory
Volume102
Issue number3
DOIs
StatePublished - Mar 2023

Scopus Subject Areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • edge contraction
  • mean subtree order
  • subtree
  • tree

Fingerprint

Dive into the research topics of 'On the mean subtree order of trees under edge contraction'. Together they form a unique fingerprint.

Cite this