# Counting Maximal Distance-Independent Sets in Grid Graphs

Reinhardt Euler; Paweł Oleksik; Zdzisław Skupień

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 3, page 531-557
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topReinhardt Euler, Paweł Oleksik, and Zdzisław Skupień. "Counting Maximal Distance-Independent Sets in Grid Graphs." Discussiones Mathematicae Graph Theory 33.3 (2013): 531-557. <http://eudml.org/doc/267798>.

@article{ReinhardtEuler2013,

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

author = {Reinhardt Euler, Paweł Oleksik, Zdzisław Skupień},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {independent set; grid graph; Fibonacci; Padovan numbers; transfer matrix method},

language = {eng},

number = {3},

pages = {531-557},

title = {Counting Maximal Distance-Independent Sets in Grid Graphs},

url = {http://eudml.org/doc/267798},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Reinhardt Euler

AU - Paweł Oleksik

AU - Zdzisław Skupień

TI - Counting Maximal Distance-Independent Sets in Grid Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 3

SP - 531

EP - 557

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

LA - eng

KW - independent set; grid graph; Fibonacci; Padovan numbers; transfer matrix method

UR - http://eudml.org/doc/267798

ER -

## References

top- [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. Zbl1068.11009
- [2] Z. Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987) 463-470. Zbl0647.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/ Zbl1159.11327
- [5] R.P. Stanley, Enumerative Combinatorics (Cambridge Univ. Press, vol. 1, 1997). doi:10.1017/CBO9780511805967[Crossref]

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.