Maximizing the mean subtree order

DOI10.1002/JGT.22434zbMATH Open1417.05031arXiv1707.01874OpenAlexW2964114505WikidataQ128821669 ScholiaQ128821669MaRDI QIDQ5229538FDOQ5229538

L. A. S. Mól, Ortrud R. Oellermann

Publication date: 15 August 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: 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 $mathcal{T}_n$ and $mathcal{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 $mathcal{T}_n$ or $mathcal{C}_n$ for $ngeq4$, 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 $mathcal{T}_n$, then the number of leaves in $T$ is $mathrmO(lo{g}_{2}n)$, and that if $T$ is optimal in $mathcal{C}_n$, then the number of leaves in $T$ is $mathrmTheta(lo{g}_{2}n)$. Along the way, we describe the asymptotic structure of optimal trees in several narrower families of trees.

Full work available at URL: https://arxiv.org/abs/1707.01874

Recommendations

• On the maximum mean subtree order of trees
• On the local and global means of subtree orders
• On the mean subtree order of trees under edge contraction
• The average order of a subtree of a tree
• Trees with the mos subtrees - an algorithmic approach

zbMATH Keywords

treesubtreecaterpillarmean subtree order

Mathematics Subject Classification ID

Trees (05C05)

Cited In (24)

• On the Mean Connected Induced Subgraph Order of Cographs
• On the mean subtree order of trees under edge contraction
• The number and average size of connected sets in graphs with degree constraints
• A lower bound on the average size of a connected vertex set of a graph
• On the eccentric subtree number in trees
• The average size of independent sets of graphs
• On the Mean Order of Connected Induced Subgraphs of Block Graphs
• Decreasing the mean subtree order by adding k edges
• The average order of a subtree of a tree
• On the probability that a random subtree is spanning
• The average size of a connected vertex set of a \(k\)-connected graph
• The average size of a connected vertex set of a graph—Explicit formulas and open problems
• On the maximum mean subtree order of trees
• On the average order of a dominating set of a forest
• On the maximum local mean order of sub-\(k\)-trees of a \(k\)-tree
• On computing the number of (BC-)subtrees, eccentric subtree number, and global and local means of trees
• Solution to a conjecture on the mean subtree order of graphs under edge addition
• Random subtrees and unimodal sequences in graphs
• On the difference of mean subtree orders under edge contraction
• A tight upper bound on the average order of dominating sets of a graph
• On the mean subtree order of graphs under edge addition
• On the local and global mean orders of sub-\(k\)-trees of \(k\)-trees
• On the roots of the subtree polynomial
• The average size of matchings in graphs

This page was built for publication: Maximizing the mean subtree order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229538)