Geodesic
Counting Maximal Distance-Independent Sets in Grid Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 531-557 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Previous work on counting maximal independent sets for paths and certain 2-dimensional grids is extended in two directions: 3-dimensional grid graphs are included and, for some/any 𝓁∈ℕ, maximal distance-𝓁 independent (or simply: maximal 𝓁-independent) sets are counted for some grids. The transfer matrix method has been adapted and successfully applied
Keywords: independent set, grid graph, Fibonacci, Padovan numbers, transfer matrix method 
@article{DMGT_2013_33_3_a4,
     author = {Euler, Reinhardt and Oleksik, Pawe{\l} and Skupie\'n, Zdzis{\l}aw},
     title = {Counting {Maximal} {Distance-Independent} {Sets} in {Grid} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {531--557},
     year = {2013},
     volume = {33},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a4/}
}
TY  - JOUR
AU  - Euler, Reinhardt
AU  - Oleksik, Paweł
AU  - Skupień, Zdzisław
TI  - Counting Maximal Distance-Independent Sets in Grid Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 531
EP  - 557
VL  - 33
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a4/
LA  - en
ID  - DMGT_2013_33_3_a4
ER  - 
%0 Journal Article
%A Euler, Reinhardt
%A Oleksik, Paweł
%A Skupień, Zdzisław
%T Counting Maximal Distance-Independent Sets in Grid Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 531-557
%V 33
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a4/
%G en
%F DMGT_2013_33_3_a4
Euler, Reinhardt; Oleksik, Paweł; Skupień, Zdzisław. Counting Maximal Distance-Independent Sets in Grid Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 531-557. http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a4/

[1] R. Euler, The Fibonacci number of a grid graph and a new class of integer sequences, J. Integer Seq. 8 (2005) Article 05.2.6.

[2] Z. Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987) 463-470.

[3] Z. Skupień, Independence or domination. Positioning method in recursive counting on paths or cycles, a manuscript (2012).

[4] N.J.A. Sloane, The On-line Encyclopedia of Integer Sequences, (2007). www.research.att.com/~njas/sequences/

[5] R.P. Stanley, Enumerative Combinatorics (Cambridge Univ. Press, vol. 1, 1997). doi:10.1017/CBO9780511805967