DMGT

Discussiones Mathematicae Graph Theory 33(3) (2013) 531-557
DOI: https://doi.org/10.7151/dmgt.1707

Counting Maximal Distance-independent Sets in Grid Graphs

Reinhardt Euler

Université Européenne de Bretagne and Lab-STICC, CNRS, UMR 6285
Université de Brest, B.P.809
20 Avenue Le Gorgeu, 29285 Brest Cedex, France

Paweł Oleksik

AGH University of Science and Technology
Faculty of Geology, Geophysics and Environment Protection
Department of Geoinformatics and Applied Computer Science
30-059 Cracow, Poland

Zdzisław Skupień

AGH Kraków
al. Mickiewicza 30, 30--059 Kraków, Poland

Abstract

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 l ∈ ℕ, maximal distance-l independent (or simply: maximal l-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

2010 Mathematics Subject Classification: 11B39, 11B83, 05A15, 05C69.

References

[1]	R. Euler, 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

Received 31 January 2012
Revised 11 October 2012
Accepted 5 November 2012