|
This article is cited in 3 scientific papers (total in 3 papers)
On the number of maximal independent sets in complete $q$-ary trees
D. S. Taletskiia, D. S. Malyshevb a Lobachevski State University of Nizhni Novgorod
b State University – Higher School of Economics in Nizhnii Novgorod
Abstract:
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$.
Keywords:
maximal independent set, complete $q$-ary tree.
Received: 16.06.2016
Citation:
D. S. Taletskii, D. S. Malyshev, “On the number of maximal independent sets in complete $q$-ary trees”, Diskr. Mat., 28:4 (2016), 139–149; Discrete Math. Appl., 27:5 (2017), 311–318
Linking options:
https://www.mathnet.ru/eng/dm1398https://doi.org/10.4213/dm1398 https://www.mathnet.ru/eng/dm/v28/i4/p139
|
Statistics & downloads: |
Abstract page: | 402 | Full-text PDF : | 48 | References: | 52 | First page: | 27 |
|