×

The mean order of sub-\(k\)-trees of \(k\)-trees. (English) Zbl 1391.05082

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.

MSC:

05C05 Trees
05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
PDFBibTeX XMLCite
Full Text: DOI