Bounds on Sweep-Covers by Functional Compositions of Ordered Integer Partitions and Raney Numbers

A sweep-cover is a vertex separator in trees that covers all the nodes by some ancestor-descendent relationship. This work provides an algorithm for finding all sweep-covers of a given size in any tree. The algorithm's complexity is proven on a class of infinite $\Delta$-ary trees with constant path lengths between the $\Delta$-star internal nodes. I prove the enumeration expression on these infinite trees is a recurrence relation of functional compositions on ordered integer partitions. The upper bound on the enumeration is analyzed with respect to the size of sweep cover $n$, maximum out-degree $\Delta$ of the tree, and path length $\gamma$, $O(n^n)$, $O(\Delta^c c^\Delta)$, and $O(\gamma ^n)$ respectively. I prove that the Raney numbers are a strict lower bound for enumerating sweep-covers on infinite $\Delta$-ary trees, $\Omega(\frac{(\Delta n)^n}{n!})$.