On Unique Minimum Dominating Sets in Some Cartesian Product Graphs

• Autorzy: Jason T. Hedetniemi
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

vertex domination; graph products; trees

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 4
• Strony: 615-628

Daty

wydano

2015-11-01

otrzymano

2014-05-15

poprawiono

2014-12-23

zaakceptowano

2014-12-23

online

2015-11-10

Twórcy

autor

Jason T. Hedetniemi

• Department of Mathematical Sciences Clemson University Clemson, South Carolina 29634, USA

Bibliografia

• [1] M. Chellali and T. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004) 3-12.
• [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]
• [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]
• [4] M. Fischermann, Unique total domination graphs, Ars Combin. 73 (2004) 289-297.
• [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]
• [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.
• [7] M. Fischermann and L. Volkmann, Unique minimum domination in trees, Australas. J. Combin. 25 (2002) 117-124.
• [8] M. Fischermann and L. Volkmann, Cactus graphs with unique minimum dominating sets, Util. Math. 63 (2003) 229-238.
• [9] M. Fischermann and L. Volkmann, Unique independence, upper domination and upper irredundance in graphs, J. Combin. Math. Combin. Comput. 47 (2003) 237-249.
• [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]
• [11] M. Fraboni and N. Shank, Maximum graphs with unique minimum dominating set of size two, Australas. J. Combin. 46 (2010) 91-99.
• [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.
• [13] R. Hammack, W. Imrich and S. Klavˇzar, Handbook of Product Graphs (CRC Press, 2011).
• [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]
• [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]
• [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]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1822