Irredundance in grids
type: Item
instance of: scholarly article
title: Irredundance in grids
zbMATH Open document ID: 0887.05026
DOI: 10.1016/S0012-365X(97)00098-8
author: Odile Favaron
author: Joël Puech
published in: Discrete Mathematics
publication date: 1998-04-28T00:00:00Z
review text: The closed neighbourhood \(N[X]\) of a set \(X\) of vertices is the set of all vertices which are either in \(X\) or are adjacent to a vertex in \(X\). A vertex \(x\in X\) is redundant in \(X\) if \(N[X]=N[X-\{x\}]\); an irredundant set contains no redundant vertices. The lower irredundance number \(\text{ir}(G)\) of a graph \(G\) is the cardinality of the smallest maximal irredundant set. A grid is either a graph of vertices of a rectangle parallel to the axes in the square plane lattice; or of the cylinder obtained by identifying vertices along two opposite edges of this rectangle (the cylindrical grid); or by identifying vertices along two pairs of opposite sides (the toroidal grid); the symbol \(G_{m,n}\) is used to identify any one of these graphs if the numbers of equivalence classes of vertices in the two directions, after identifications, are respectively \(m\) and \(n\). Theorem 1. \(\text{ir}(G_{m,n})\geq\left\lceil\frac{mn}5\right\rceil\). The authors refer to methods of \textit{E. J. Cockayne, E. O. Hare, S. T. Hedetniemi} and \textit{T. V. Wimer} [Bounds for the domination number of grid graphs, Congr. Numerantium 47, 217-228 (1985; Zbl 0622.05055)] to infer that \(\text{ir}(G_{m,n})\leq\frac{(m+2)(n+2)}5\) and conclude that \(\text{ir}(G_{m,n})\) is asymptotic to \(\frac{mn}5\) as \(m\) and \(n\) both tend to infinity.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1110000
zbMATH Keywords: closed neighbourhood
zbMATH Keywords: lower irredundance number
zbMATH Keywords: cylindrical grid
zbMATH Keywords: toroidal grid
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: The domination numbers of the 5 × n and 6 × n grid graphs
cites work: Q4326192
cites work: Q3758883
cites work: Properties of Hereditary Hypergraphs and Middle Graphs
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Irredundance and Maximum Degree in Graphs
cites work: Q4871169
cites work: Q4304569
cites work: Q3680873
Recommended article: Q3139859
Recommended article: Irregularity strength of the toroidal grid
Recommended article: Q4457556
Recommended article: On the irregularity strength of them ×n grid
Recommended article: Distance irredundance in graphs: Complexity issues
Recommended article: Edge-isoperimetric inequalities in the grid
Recommended article: Q4856621
Recommended article: Q5492568
Recommended article: A note on the irredundance number after vertex deletion
Recommended article: Q4457557
description: scientific article; zbMATH DE number 1110000