# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## 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