Geodesic
On properties of solution of a reccurent equation appearing in enumeration of maximal independent sets in complete trees
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 20 (2018) no. 1, pp. 46-54.

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

The article considers a second-order nonlinear recurrent equation arising in analysis of the independent sets' quantity in complete $q$-ary trees. We proved earlier that for $q=2$ its solution has a limit and for any sufficiently large $q$ the solution splits into three converging subsequences with indices corresponding to the residue classes modulo 3. Computational experiment allowed to assume that this effect holds for any $q\geq 11$. The present paper proves divergence of the solution for any $q\geq 3$. The necessary condition for simultaneous convergence of all subsequences of the solution, with indices corresponding to the residue classes modulo 3, is the existence of a special solution of some nonlinear equations' system. Numerical search for solutions of the system, conducted in the present paper, showed that there is no corresponding solution of the system for any $3\leq q\leq 9$. We numerically and analytically show that the non-disintegrability into three subsequences takes place also for $q=10$.
Keywords: recurrent equation, divergence theorem, computational experiment. 
@article{SVMO_2018_20_1_a4,
     author = {D. S. Taletskii},
     title = {On properties of solution of a reccurent equation appearing in enumeration of maximal independent sets in complete trees},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {46--54},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2018_20_1_a4/}
}
TY  - JOUR
AU  - D. S. Taletskii
TI  - On properties of solution of a reccurent equation appearing in enumeration of maximal independent sets in complete trees
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2018
SP  - 46
EP  - 54
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2018_20_1_a4/
LA  - ru
ID  - SVMO_2018_20_1_a4
ER  - 
%0 Journal Article
%A D. S. Taletskii
%T On properties of solution of a reccurent equation appearing in enumeration of maximal independent sets in complete trees
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2018
%P 46-54
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2018_20_1_a4/
%G ru
%F SVMO_2018_20_1_a4
D. S. Taletskii. On properties of solution of a reccurent equation appearing in enumeration of maximal independent sets in complete trees. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 20 (2018) no. 1, pp. 46-54. http://geodesic.mathdoc.fr/item/SVMO_2018_20_1_a4/

[1] A. D. Korshunov, A. A. Sapozhenko, “On the number of binary codes with distance two”, Problemy kibernetiki, 40 (1983), 111–130 (In Russ.) | Zbl

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

[3] P. Kirschenhofer, H. Prodinger, R. Tichy, “Fibonacci numbers of graphs: III”, Proceedings of the First International Conference on Fibonacci Numbers and Applications, 1986, 105–120 | DOI | MR | Zbl

[4] D. S. Taletskii, D. S. Malyshev, “On the number of maximal independent sets in complete $q$-ary trees”, Diskretnya Matematika, 28:4 (2016), 139–149 (In Russ.) | DOI | MR

[5] N. J. Calkin, H. S. Wilf, “The number of independent sets in a grid graph”, SIAM Journal of Discrete Mathematics, 11:1 (1997), 54–60 | DOI | MR

[6] S. Oh, S. Lee, “Enumerating independent vertex sets in grid graphs”, Linear Algebra and its Applications, 510 (2016), 192–204 | DOI | MR | Zbl

[7] R. Euler, “The Fibonacci number of a grid graph and a new class of integer sequences”, Journal of Integer Sequences, 8:07.2.6 (2005), 1–12 | MR

[8] R. Euler, P. Oleksik, Z. Skupien, “Counting maximal distance-independent sets in grid graphs”, Discussiones Mathematicae Graph Theory, 33:3 (2013), 531–557 | DOI | MR | Zbl