×

Irredundance in grids. (English) Zbl 0887.05026

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 E. J. Cockayne, E. O. Hare, S. T. Hedetniemi and 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.

MSC:

05C35 Extremal problems in graph theory

Citations:

Zbl 0622.05055
Full Text: DOI

References:

[1] Chang, T. Y.; Clark, W. E., The domination numbers of the 5 × \(n\) and 6 × \(n\) grid graphs, J. Graph Theory, 17, 1, 81-107 (1993) · Zbl 0780.05030
[2] Chang, T. Y.; Clark, W. E.; Hare, E. O., Domination numbers of complete grid graphs, I, Ars Combin., 38, 97-111 (1994) · Zbl 0818.05038
[3] Cockayne, E. J.; Hare, E. O.; Hedetniemi, S. T.; Wimer, T. V., Bounds for the domination number of grid graphs, (Congr. Numer., 47 (1985)), 217-228 · Zbl 0622.05055
[4] Cockayne, E. J.; Hedetniemi, S. T.; Miller, D. J., Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 21, 461-468 (1978) · Zbl 0393.05044
[5] Cockayne, E. J.; Favaron, O.; Payan, C.; Thomason, A. G., Contribution to the theory of domination, independence and irredundance in Graphs, Discrete Math., 33, 249-258 (1981) · Zbl 0471.05051
[6] E.J. Cockayne, C.M. Mynhardt, Irredundance and maximum degree in graphs, preprint.; E.J. Cockayne, C.M. Mynhardt, Irredundance and maximum degree in graphs, preprint. · Zbl 0881.05068
[7] G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, A.A. McRae, C.K. Wallis, M.S. Jacobson, H.W. Martin, W.D. Weakley, Combinatorial problems on chessboards: a survey, in: Proc. 7th Internat. Conf. in Graph Theory, Combinatorics, Algorithms and Applications (to appear).; G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, A.A. McRae, C.K. Wallis, M.S. Jacobson, H.W. Martin, W.D. Weakley, Combinatorial problems on chessboards: a survey, in: Proc. 7th Internat. Conf. in Graph Theory, Combinatorics, Algorithms and Applications (to appear). · Zbl 0843.05061
[8] Hare, E. O.; Hare, W. R., Domination in graphs similar to grid graphs, (Congr. Numer., 97 (1993)), 143-154 · Zbl 0802.05049
[9] Jacobson, M. S.; Kinch, L. F., On the domination number of products of graphs: I, Ars Combin., 18, 33-44 (1983) · Zbl 0566.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.