Irredundance in grids (Q1377729)

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.