Geodesic
On the number of maximal independent sets in complete $q$-ary trees
Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 139-149.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2016_28_4_a10,
     author = {D. S. Taletskii and D. S. Malyshev},
     title = {On the number of maximal independent sets in complete $q$-ary trees},
     journal = {Diskretnaya Matematika},
     pages = {139--149},
     publisher = {mathdoc},
     volume = {28},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_4_a10/}
}
TY  - JOUR
AU  - D. S. Taletskii
AU  - D. S. Malyshev
TI  - On the number of maximal independent sets in complete $q$-ary trees
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 139
EP  - 149
VL  - 28
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_4_a10/
LA  - ru
ID  - DM_2016_28_4_a10
ER  - 
%0 Journal Article
%A D. S. Taletskii
%A D. S. Malyshev
%T On the number of maximal independent sets in complete $q$-ary trees
%J Diskretnaya Matematika
%D 2016
%P 139-149
%V 28
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_4_a10/
%G ru
%F DM_2016_28_4_a10
D. S. Taletskii; D. S. Malyshev. On the number of maximal independent sets in complete $q$-ary trees. Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 139-149. http://geodesic.mathdoc.fr/item/DM_2016_28_4_a10/

[1] Voronin V. P., Demakova E. V., “O chisle nezavisimykh mnozhestv dlya nekotorykh semeistv grafov”, Trudy IV Mezhdunar. konf. «Diskretnye modeli v teorii upravlyayuschikh sistem» (Krasnovidovo, 19–25 iyunya 2000 g.), Izd-vo MAKS Press, M., 2000, 145–149 | MR

[2] Dainyak A. B., “O chisle nezavisimykh mnozhestv v polnykh $q$-arnykh derevyakh”, Uchënye zapiski Kazanskogo gos. un-ta. Seriya Fiz.-matem. nauki, 151, no. 2, Izd-vo Kazanskogo un-ta, Kazan, 2009, 59–64

[3] Korshunov A. D., Sapozhenko A. A., “O chisle dvoichnykh kodov s rasstoyaniem 2”, Problemy kibernetiki, 40 (1983), 111–130 | MR | Zbl

[4] Kalkin N. J., Wilf H. S., “The number of independent sets in a grid graph”, SIAM J. Discr. Math., 11:1 (1997), 54–60 | DOI | MR

[5] Kirschenhofer P., Prodinger H., Tichy R., “Fibonacci numbers of graphs: II”, The Fibonacci Quarterly, 21:3 (1983), 219–229 | MR | Zbl