Bounds on Sweep-Covers by Raney Numbers

Abstract

In this work, we introduce a vertex separator in trees known as a sweep-cover that is defined by an ancestor-descendent relationship with all nodes in the tree. We prove the recurrence relation of sweep-covers with $n$ subcovers $P_{\Delta ,\gamma }(n)$ on a class of infinite $\Delta$-ary trees with constant path lengths $\gamma$ between the $\Delta$-star internal nodes. Then, we provide recurrence relations for Raney numbers over integer compositions and show that they provide a lower-bound for sweep-covers such that $P_{\Delta ,\gamma }(n)=\Omega \left(\frac{\sqrt{2\pi }{n}^{\Delta n+\Delta +\frac{3}{2}}}{e^n((\Delta -1)n+\Delta +1)!(n+1)!}\gamma \right)$.