Bounding mean orders of sub-$k$-trees of $k$-trees

Abstract

For a $k$-tree $T$, we prove that the maximum local mean order is attained in a $k$-clique of degree $1$ and that it is not more than twice the global mean order. We also bound the global mean order if $T$ has no $k$-cliques of degree $2$ and prove that for large order, the $k$-star attains the minimum global mean order. These results solve the remaining problems of Stephens and Oellermann [J. Graph Theory 88 (2018), 61-79] concerning the mean order of sub-$k$-trees of $k$-trees.

20 Pages, 6 Figures

References in corpus (6)

• The number and average size of connected sets in graphs with degree constraints
• The path minimises the average size of a connected induced subgraph
• Extrema of local mean and local density in a tree
• Decreasing the mean subtree order by adding $k$ edges
• On the maximum local mean order of sub-k-trees of a k-tree
• On the Mean Subtree Order of Graphs Under Edge Addition