On the number of maximal independent sets in complete $q$-ary trees

D. S. Taletskii ; D. S. Malyshev

Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 139-149

Résumé

The paper is concerned with the asymptotic behaviour of the number $\operatorname{mi}(T_{q,n})$ of maximal independent sets in a complete $q$-ary tree of height $n$. For some constants $\alpha_2$ and $\beta_2$ the asymptotic formula $\operatorname{mi}(T_{2,n})\thicksim \alpha_2\cdot (\beta_2)^{2^n}$ is shown to hold as $n\to\infty$. It is also proved that $\operatorname{mi}(T_{q,3k})\thicksim \alpha^{(1)}_q\cdot(\beta_q)^{q^{3k}},\operatorname{mi}(T_{q,3k+1})\thicksim \alpha^{(2)}_q\cdot(\beta_q)^{q^{3k+1}},\operatorname{mi}(T_{q,3k+2})\thicksim \alpha^{(3)}_q\cdot(\beta_q)^{q^{3k+2}}$ as $k\to \infty$ for any sufficiently large $q$, some three pairwise distinct constants $\alpha^{(1)}_q,\alpha^{(2)}_q,\alpha^{(3)}_q$ and a constant $b_q$.

Détail

Keywords: maximal independent set, complete $q$-ary tree.