Premium
Maximizing the mean subtree order
Author(s) -
Mol Lucas,
Oellermann Ortrud R.
Publication year - 2019
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.22434
Subject(s) - mathematics , lemma (botany) , combinatorics , order (exchange) , simple (philosophy) , vertex (graph theory) , tree (set theory) , path (computing) , weight balanced tree , discrete mathematics , binary tree , computer science , graph , binary search tree , botany , philosophy , poaceae , finance , epistemology , economics , biology , programming language
This article focuses on properties and structures of trees with maximum mean subtree order in a given family; such trees are called optimal in the family. Our main goal is to describe the structure of optimal trees in T n and C n , the families of all trees and caterpillars, respectively, of order n . We begin by establishing a powerful tool called the Gluing Lemma , which is used to prove several of our main results. In particular, we show that if T is an optimal tree in T n or C n for n ≥ 4 , then every leaf of T is adjacent to a vertex of degree at least 3 . We also use the Gluing Lemma to answer an open question of Jamison and to provide a conceptually simple proof of Jamison's result that the path P n has minimum mean subtree order among all trees of order n . We prove that if T is optimal in T n , then the number of leaves in T is O ( log 2 n ) and that if T is optimal in C n , then the number of leaves in T is Θ ( log 2 n ) . Along the way, we describe the asymptotic structure of optimal trees in several narrower families of trees.