Every grid has an independent \([1, 2]\)-set. (English) Zbl 1414.05215
Summary: It is well known that the Cartesian product of two paths, the grid \(P_m \square P_n\), \(m \leq n\), has an independent dominating set such that every vertex not in the set has exactly one neighbor in it, if and only if \(m = n = 4\) or \(m = 2\), \(n = 2 k + 1\). In this paper we prove that every grid \(P_m \square P_n\) has an independent dominating set such that every vertex not in the set has at most two neighbors in it, and we also calculate the minimum cardinality of such sets.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C76 | Graph operations (line graphs, products, etc.) |
References:
| [1] | D.W. Bange, A.E. Barkauskas, P.J. Slater, Efficient dominating sets in graphs. Applications of Discrete Mathematics, in: Proceedings of the Third SIAM Conference on Discrete Mathematics (1986) 189-199.; D.W. Bange, A.E. Barkauskas, P.J. Slater, Efficient dominating sets in graphs. Applications of Discrete Mathematics, in: Proceedings of the Third SIAM Conference on Discrete Mathematics (1986) 189-199. · Zbl 0664.05027 |
| [2] | Biggs, N., Perfect codes in graphs, J. Combin. Theory Ser. B, 15, 288-296 (1973) · Zbl 0256.94009 |
| [3] | Carreño, J. J.; Martínez, J. A.; Puertas, M. L., Efficient location of resources in cylindrical networks, Symmetry, 10, 1, 24 (2018) · Zbl 1391.90367 |
| [4] | Chartrand, G.; Lesniak, L.; Zhang, P., Graphs and Digraphs (2011), CRC Press: CRC Press Boca Raton, Florida · Zbl 1211.05001 |
| [5] | Chellali, M.; Favaron, O.; Haynes, T.; Hedetniemi, S.; McRae, A., Independent \([1, k]\)-sets in graphs, Australas. J. Combin., 59, 1, 144-156 (2014) · Zbl 1296.05148 |
| [6] | Crevals, S.; Östergård, P. R.J., Independent domination of grids, Discrete Math., 338, 1379-1384 (2015) · Zbl 1310.05158 |
| [7] | (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Foundamentals of Domination in Graphs (1998), Marcel Dekker, Inc.: Marcel Dekker, Inc. New York) · Zbl 0890.05002 |
| [8] | Livingston, M.; Stout, Q. F., Perfect dominating sets, Congr. Numer., 79, 187-203 (1990) · Zbl 0862.05064 |
| [9] | Pin, J.-E., (Tropical Semirings, Idempotency (Bristol, 1994). Tropical Semirings, Idempotency (Bristol, 1994), Publ. Newton Inst., vol. 11 (1998), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 50-69 · Zbl 0909.16028 |
| [10] | Spalding, A., Min-Plus algebra and graph domination, ((1998), Dept. of Applied Mathematics: Dept. of Applied Mathematics University of Colorado), (Ph.D thesis) |
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.
