Counting maximal distance-independent sets in grid graphs
type: Item
instance of: scholarly article
title: Counting maximal distance-independent sets in grid graphs
zbMATH Open document ID: 1322.05109
author: Paweł Oleksik
author: Zdzisław Skupień
author: Reinhardt Euler
publication date: 2013-10-31T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 11B39
Mathematics Subject Classification ID: 11B83
zbMATH DE Number: 6221384
zbMATH Keywords: independent set
zbMATH Keywords: grid graph
zbMATH Keywords: Fibonacci
zbMATH Keywords: Padovan numbers
zbMATH Keywords: transfer matrix method
Wikidata QID: Q60692824
MaRDI profile type: Publication
full work available at URL: dmgt.1707
OpenAlex ID: W2015610404
DOI: 10.7151/DMGT.1707
published in: Discussiones Mathematicae. Graph Theory
review text: \(G_{p,q,r} = (V, E)\) is called 3-dimensional grid graph of size \(p \times q \times r\) (or \((p,q,r)\)-grid graph) with vertex set NEWLINE\[NEWLINEV = \{ (i,j,k) : 1 \leq i \leq p, 1 \leq j \leq q, 1 \leq k \leq n \}NEWLINE\]NEWLINE and edge set NEWLINE\[NEWLINEE = \{ (i,j,k), (i',j',k') : |i - i'| + |j - j'| + |k - k'| = 1 \},NEWLINE\]NEWLINE where \(p\), \(q\), \(r\) are natural numbers. Some properties of the \((p,q,r)\)-grid graphs are discussed. Matrix representations of them are shown.
reviewed by: Krassimir Atanassov
description: scientific article; zbMATH DE number 6221384