Counting Maximal Distance-Independent Sets in Grid Graphs

• Autorzy: Reinhardt Euler , Paweł Oleksik , Zdzisław Skupień
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 3
• Strony: 531-557

Daty

wydano

2013-07-01

online

2013-07-30

Twórcy

autor

Reinhardt Euler

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

autor

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

autor

Zdzisław Skupień

• AGH Kraków al. Mickiewicza 30, 30–059 Kraków, Poland

Bibliografia

• [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´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/
• [5] R.P. Stanley, Enumerative Combinatorics (Cambridge Univ. Press, vol. 1, 1997). doi:10.1017/CBO9780511805967[Crossref]

Identyfikatory

DOI

10.7151/dmgt.1707