On Unique Minimum Dominating Sets in Some Cartesian Product Graphs

Jason T. Hedetniemi

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 615-628
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Jason T. Hedetniemi. "On Unique Minimum Dominating Sets in Some Cartesian Product Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 615-628. <http://eudml.org/doc/275865>.

@article{JasonT2015,
abstract = {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.},
author = {Jason T. Hedetniemi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {vertex domination; graph products; trees},
language = {eng},
number = {4},
pages = {615-628},
title = {On Unique Minimum Dominating Sets in Some Cartesian Product Graphs},
url = {http://eudml.org/doc/275865},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Jason T. Hedetniemi
TI - On Unique Minimum Dominating Sets in Some Cartesian Product Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 615
EP - 628
AB - 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.
LA - eng
KW - vertex domination; graph products; trees
UR - http://eudml.org/doc/275865
ER -

References

top
  1. [1] M. Chellali and T. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004) 3-12. Zbl1082.05023
  2. [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] Zbl0311.68024
  3. [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] Zbl0982.05073
  4. [4] M. Fischermann, Unique total domination graphs, Ars Combin. 73 (2004) 289-297. Zbl1073.05048
  5. [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] Zbl1011.05042
  6. [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. Zbl1038.05043
  7. [7] M. Fischermann and L. Volkmann, Unique minimum domination in trees, Australas. J. Combin. 25 (2002) 117-124. Zbl1001.05088
  8. [8] M. Fischermann and L. Volkmann, Cactus graphs with unique minimum dominating sets, Util. Math. 63 (2003) 229-238. Zbl1035.05062
  9. [9] M. Fischermann and L. Volkmann, Unique independence, upper domination and upper irredundance in graphs, J. Combin. Math. Combin. Comput. 47 (2003) 237-249. Zbl1038.05044
  10. [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] Zbl1080.05066
  11. [11] M. Fraboni and N. Shank, Maximum graphs with unique minimum dominating set of size two, Australas. J. Combin. 46 (2010) 91-99. Zbl1196.05061
  12. [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. Zbl0836.05045
  13. [13] R. Hammack, W. Imrich and S. Klavˇzar, Handbook of Product Graphs (CRC Press, 2011). Zbl1283.05001
  14. [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] Zbl1031.05095
  15. [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] Zbl1022.05055
  16. [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] Zbl1024.05068
  17. [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] Zbl0784.05038

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.