Stephens, Alexander M.; Oellermann, Ortrud R. The mean order of sub-\(k\)-trees of \(k\)-trees. (English) Zbl 1391.05082 J. Graph Theory 88, No. 1, 61-79 (2018). Summary: This article focuses on the problem of determining the mean orders of sub-\(k\)-trees of \(k\)-trees. It is shown that the problem of finding the mean order of all sub-\(k\)-trees containing a given \(k\)-clique \(C\), can be reduced to the previously studied problem of finding the mean order of subtrees of a tree that contain a given vertex. This problem is extended in two ways. The first of these extensions focuses on the mean order of sub-\(k\)-trees containing a given sub-\(k\)-tree. The second extension focuses on the expected number of \(r\)-cliques, \(1\leq r\leq k+1\), in a randomly chosen sub-\(k\)-tree containing a fixed sub-\(k\)-tree \(X\). Sharp lower bounds for both invariants are derived. The article concludes with a study of global mean orders of sub-\(k\)-trees of a \(k\)-tree. For a \(k\)-tree, from the class of simple-clique \(k\)-trees, it is shown that the mean order of its sub-\(k\)-trees is asymptotically equal to the mean subtree order of its dual. For general \(k\)-trees a recursive generating function for the number of sub-\(k\)-trees of a given \(k\)-tree \(T\) is derived. Cited in 1 ReviewCited in 6 Documents MSC: 05C05 Trees 05C30 Enumeration in graph theory 05A15 Exact enumeration problems, generating functions 05A16 Asymptotic enumeration Keywords:generating functions; global mean orders; \(k\)-tree; local mean orders; simple-clique \(k\)-trees; sub-\(k\)-trees of \(k\)-trees PDFBibTeX XMLCite \textit{A. M. Stephens} and \textit{O. R. Oellermann}, J. Graph Theory 88, No. 1, 61--79 (2018; Zbl 1391.05082) Full Text: DOI