Dominating sequences in grid-like and toroidal graphs. (English) Zbl 1353.05105
Summary: A longest sequence \(S\) of distinct vertices of a graph \(G\) such that each vertex of \(S\) dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of \(S\) is the Grundy domination number of \(G\). In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.
MSC:
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | G. Abay-Asmerom, R. H. Hammack, D. T. Taylor. Perfect r-codes in strong products of graphs. Bull. Inst. Combin. Appl. 55:66-72, 2009. · Zbl 1175.05048 |
| [2] | B. Bollob´as, I. Leader. Compressions and isoperimetric inequalities. J. Combin. Theory Ser. A 56:47-62, 1991. the electronic journal of combinatorics 23(4) (2016), #P4.34 18 · Zbl 0731.05043 |
| [3] | B. Breˇsar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klavˇzar, D. F.Rall. Vizing’s conjecture: a survey and recent results. J. Graph Theory 69:46-76, 2012. · Zbl 1234.05173 |
| [4] | B. Breˇsar, T. Gologranc, T. Kos. Dominating sequences under atomic changes with applications in Sierpi´nski and interval graphs. Appl. Anal. Discrete Math. 10:518-531, 2016. · Zbl 1461.05152 |
| [5] | B. Breˇsar, T. Gologranc, M. Milaniˇc, D. F. Rall, R. Rizzi. Dominating sequences in graphs. Discrete Math. 336:22-36, 2014. · Zbl 1300.05210 |
| [6] | B. Breˇsar, M. A. Henning, D. F. Rall. Total dominating sequences in graphs. Discrete Math. 339:1165-1676, 2016. · Zbl 1333.05214 |
| [7] | P. Erd˝os, A. W. Goodman, L. P´osa. The representation of a graph by set intersec tions. Canad. J. Math. 18:106-112, 1966. · Zbl 0137.43202 |
| [8] | D. Gon¸calves, A. Pinlou, M. Rao S. Thomass´e. The domination number of grids. SIAM J. Discrete Math. 25:1443-1453, 2011. · Zbl 1237.05150 |
| [9] | R. Hammack, W. Imrich, S. Klavˇzar. Handbook of Product Graphs, Second Edition. CRC Press, Boca Raton, FL, 2011. · Zbl 1283.05001 |
| [10] | T. W. Haynes, S. T. Hedetniemi, P. Slater. Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York, NY, 1998. · Zbl 0890.05002 |
| [11] | S. Klavˇzar, N. Seifter. Dominating Cartesian products of cycles. Discrete Appl. Math. 59:129-136, 1995. · Zbl 0824.05037 |
| [12] | S. Klavˇzar, S. ˇSpacapan, J. ˇZerovnik. An almost complete description of perfect codes in direct product of cycles. Adv. in Appl. Math. 37:2-18, 2006. · Zbl 1114.05073 |
| [13] | R. J. Nowakowski, D. F. Rall. Associative graph products and their independence, domination and coloring numbers. Discuss. Math. Graph Theory 16:53-79, 1996. · Zbl 0865.05071 |
| [14] | T. A. McKee, F. R. McMorris.Topics in Intersection Graphs Theory.SIAM, Philadelphia, 1999. · Zbl 0945.05003 |
| [15] | P. Pavliˇc, J. ˇZerovnik. A note on the domination number of the Cartesian products of paths and cycles. Kragujevac J. Math. 37:2017-285, 2013. · Zbl 1299.05255 |
| [16] | O. Riordan. An ordering on the even discrete torus. SIAM J. Discrete Math. 11:110- 127, 1998. · Zbl 0914.05038 |
| [17] | D. T. Taylor. Perfect r-codes in lexicographic products of graphs. Ars Combin. 93:2015-223, 2009. · Zbl 1224.05155 |
| [18] | V. G. Vizing. The cartesian product of graphs. Vyˇcisl. Sistemy 9:30-43, 1963. · Zbl 0194.25203 |
| [19] | J. ˇZerovnik. Perfect codes in direct products of cycles—a complete characterization Adv. in Appl. Math. 41:197-2015, 2008. · Zbl 1214.94084 |
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.
