Geodesic
On generating functions and limit theorems connected with maximal independent sets in grid graphs
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 19 (2017) no. 2, pp. 105-116.

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

In this paper we study some quantitative characteristics of maximal independent sets in grid graphs using methods of combinatorial analysis, enumerative combinatorics, mathematical analysis and linear algebra. We obtain the explicit generating functions for the number of maximal independent sets in cylindrical and toroidal lattices of width 4, 5, 6. We prove that the limits of $mn$-th root of the number of (maximal) independent sets in rectangular, cylindrical and toroidal $m\times n$-lattices exist and that they are equal. Nobody studied the quantitative characteristics of maximal independent sets in grid graphs with respect to cylindrical and toroidal lattices before. Also nobody proved the existence of the limits of $mn$-th root of the number of maximal independent sets in grid graphs. Thus, our paper is a further development of enumerative combinatorics.
Keywords: independent set, grid graph, generating function, limit theorem. 
@article{SVMO_2017_19_2_a9,
     author = {D. S. Taletskii},
     title = {On generating functions and limit theorems connected with maximal independent sets in grid graphs},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {105--116},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a9/}
}
TY  - JOUR
AU  - D. S. Taletskii
TI  - On generating functions and limit theorems connected with maximal independent sets in grid graphs
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2017
SP  - 105
EP  - 116
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a9/
LA  - ru
ID  - SVMO_2017_19_2_a9
ER  - 
%0 Journal Article
%A D. S. Taletskii
%T On generating functions and limit theorems connected with maximal independent sets in grid graphs
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2017
%P 105-116
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a9/
%G ru
%F SVMO_2017_19_2_a9
D. S. Taletskii. On generating functions and limit theorems connected with maximal independent sets in grid graphs. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 19 (2017) no. 2, pp. 105-116. http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a9/

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

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

[3] 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

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

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

[6] 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

[7] 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