Counting Maximal Distance-Independent Sets in Grid Graphs
Reinhardt Euler ; Paweł Oleksik ; Zdzisław Skupień
Discussiones Mathematicae Graph Theory, Tome 33 (2013), p. 531-557 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 ℓ ∈ N, maximal distance-ℓ independent (or simply: maximal ℓ-independent) sets are counted for some grids. The transfer matrix method has been adapted and successfully applied

Publié le : 2013-01-01
EUDML-ID : urn:eudml:doc:267798 
@article{bwmeta1.element.doi-10_7151_dmgt_1707,
     author = {Reinhardt Euler and Pawe\l\ Oleksik and Zdzis\l aw Skupie\'n},
     title = {Counting Maximal Distance-Independent Sets in Grid Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {33},
     year = {2013},
     pages = {531-557},
     zbl = {1322.05109},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1707}
}

Reinhardt Euler; Paweł Oleksik; Zdzisław Skupień. Counting Maximal Distance-Independent Sets in Grid Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 531-557. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1707/

[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. | Zbl 1068.11009

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

[3] Z. Skupie´n, 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/ | Zbl 1159.11327

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