Geodesic
On Unique Minimum Dominating Sets in Some Cartesian Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 615-628

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: vertex domination, graph products, trees 
Hedetniemi, Jason T. On Unique Minimum Dominating Sets in Some Cartesian Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 615-628. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a1/
@article{DMGT_2015_35_4_a1,
     author = {Hedetniemi, Jason T.},
     title = {On {Unique} {Minimum} {Dominating} {Sets} in {Some} {Cartesian} {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {615--628},
     year = {2015},
     volume = {35},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a1/}
}
TY  - JOUR
AU  - Hedetniemi, Jason T.
TI  - On Unique Minimum Dominating Sets in Some Cartesian Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 615
EP  - 628
VL  - 35
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a1/
LA  - en
ID  - DMGT_2015_35_4_a1
ER  - 
%0 Journal Article
%A Hedetniemi, Jason T.
%T On Unique Minimum Dominating Sets in Some Cartesian Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 615-628
%V 35
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a1/
%G en
%F DMGT_2015_35_4_a1

[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

[3] M. Fischermann, Block graphs with unique minimum dominating sets, Discrete Math. 240 (2001) 247-251. doi:10.1016/S0012-365X(01)00196-0

[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

[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

[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

[15] M. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003) 101-115. doi:10.1016/S0012-365X(03)00040-2

[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

[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