Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.
@article{bwmeta1.element.doi-10_7151_dmgt_1822,
author = {Jason T. Hedetniemi},
title = {On Unique Minimum Dominating Sets in Some Cartesian Product Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {615-628},
zbl = {1327.05259},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1822}
}
Jason T. Hedetniemi. On Unique Minimum Dominating Sets in Some Cartesian Product Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 615-628. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1822/
[1] M. Chellali and T. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004) 3-12. | Zbl 1082.05023
[2] E. Cockayne, S. Goodman and S. Hedetniemi, A linear algorithm for the domination number of a tree, Inform. Process. Lett. 4 (1975) 41-44. doi:10.1016/0020-0190(75)90011-3[Crossref] | Zbl 0311.68024
[3] M. Fischermann, Block graphs with unique minimum dominating sets, Discrete Math. 240 (2001) 247-251. doi:10.1016/S0012-365X(01)00196-0[Crossref] | Zbl 0982.05073
[4] M. Fischermann, Unique total domination graphs, Ars Combin. 73 (2004) 289-297. | Zbl 1073.05048
[5] M. Fischermann, D. Rautenbach and L. Volkmann, Maximum graphs with a unique minimum dominating set , Discrete Math. 260 (2003) 197-203. doi:10.1016/S0012-365X(02)00670-2[Crossref] | Zbl 1011.05042
[6] M. Fischermann, D. Rautenbach and L. Volkmann, A note on the complexity of graph parameters and the uniqueness of their realizations, J. Combin. Math. Com- bin. Comput. 47 (2003) 183-188. | Zbl 1038.05043
[7] M. Fischermann and L. Volkmann, Unique minimum domination in trees, Australas. J. Combin. 25 (2002) 117-124. | Zbl 1001.05088
[8] M. Fischermann and L. Volkmann, Cactus graphs with unique minimum dominating sets, Util. Math. 63 (2003) 229-238. | Zbl 1035.05062
[9] M. Fischermann and L. Volkmann, Unique independence, upper domination and upper irredundance in graphs, J. Combin. Math. Combin. Comput. 47 (2003) 237-249. | Zbl 1038.05044
[10] M. Fischermann, L. Volkmann and I. Zverovich, Unique irredundance, domination, and independent domination in graphs, Discrete Math. 305 (2005) 190-200. doi:10.1016/j.disc.2005.08.005[Crossref] | Zbl 1080.05066
[11] M. Fraboni and N. Shank, Maximum graphs with unique minimum dominating set of size two, Australas. J. Combin. 46 (2010) 91-99. | Zbl 1196.05061
[12] G. Gunther, B. Hartnell, L. Markus and D. Rall, Graphs with unique minimum dom- inating sets, in: Proc. 25th S.E. Int. Conf. Combin., Graph Theory, and Computing, Congr. Numer. 101 (1994) 55-63. | Zbl 0836.05045
[13] R. Hammack, W. Imrich and S. Klavˇzar, Handbook of Product Graphs (CRC Press, 2011). | Zbl 1283.05001
[14] T. Haynes and M. Henning, Trees with unique minimum total dominating sets, Discuss. Math. Graph Theory 22 (2002) 233-246. doi:10.7151/dmgt.1172[Crossref] | Zbl 1031.05095
[15] M. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003) 101-115. doi:10.1016/S0012-365X(03)00040-2[Crossref] | Zbl 1022.05055
[16] M. Henning and S. Hedetniemi, Defending the Roman Empire-a new strategy, Discrete Math. 266 (2003) 239-251. doi:10.1016/S0012-365X(02)00811-7[Crossref] | Zbl 1024.05068
[17] J. Topp, Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices, Discrete Math. 121 (1993) 199-210. doi:10.1016/0012-365X(93)90553-6 [Crossref] | Zbl 0784.05038