On the Local and Global Mean Orders of Sub-$k$-Trees of $k$-Trees

Abstract

In this paper we show that for a given $k$-tree $T$ with a $k$-clique $C$, the local mean order of all sub-$k$-trees of $T$ containing $C$ is not less than the global mean order of all sub-$k$-trees of $T$, and the path-type $k$-trees have the smallest global mean sub-$k$-tree order among all $k$-trees of a given order. These two results give solutions to two problems of Stephens and Oellermann [J. Graph Theory 88 (2018), 61-79] concerning the mean order of sub-$k$-trees of $k$-trees. Furthermore, the mean sub-$k$-tree order as a function on $k$-trees is shown to be monotone with respect to inclusion. This generalizes Jamison's result for the case $k=1$ [J. Combin. Theory Ser. B 35 (1983), 207-223].