Geodesic
Unique minimum semipaired dominating sets in trees
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 35-53 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let G be a graph with vertex set V. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V ∖ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number is the minimum cardinality of a semipaired dominating set of G. We characterize the trees having a unique minimum semipaired dominating set. We also determine an upper bound on the semipaired domination number of these trees and characterize the trees attaining this bound.
Keywords: paired-domination, semipaired domination number 
@article{DMGT_2023_43_1_a2,
     author = {Haynes, Teresa W. and Henning, Michael A.},
     title = {Unique minimum semipaired dominating sets in trees},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {35--53},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a2/}
}
TY  - JOUR
AU  - Haynes, Teresa W.
AU  - Henning, Michael A.
TI  - Unique minimum semipaired dominating sets in trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 35
EP  - 53
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a2/
LA  - en
ID  - DMGT_2023_43_1_a2
ER  - 
%0 Journal Article
%A Haynes, Teresa W.
%A Henning, Michael A.
%T Unique minimum semipaired dominating sets in trees
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 35-53
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a2/
%G en
%F DMGT_2023_43_1_a2
Haynes, Teresa W.; Henning, Michael A. Unique minimum semipaired dominating sets in trees. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 35-53. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a2/

[1] M. Blidia, M. Chellali, R. Lounes and F. Maffray, Characterizations of trees with unique minimum locating-dominating sets, J. Combin. Math. Combin. Comput. 76 (2011) 225–232.

[2] M. Chellali and T.W. Haynes, Trees with unique minimum paired dominating sets, Ars Combin. 73 (2004) 3–12.

[3] M. Chellali and T.W. Haynes, A characterization of trees with unique minimum double dominating sets, Util. Math. 83 (2010) 233–242.

[4] L. Chen, C. Lu and Z. Zeng, Graphs with unique minimum paired-dominating set, Ars Combin. 119 (2015) 177–192.

[5] W.J. Desormeaux and M.A. Henning, Paired domination in graphs: A survey and recent results, Util. Math. 94 (2014) 101–166.

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

[7] M. Fischermann, Unique total domination graphs, Ars Combin. 3 (2004) 289–297.

[8] G. Gunther, B. Hartnell, L.R. Markus and D. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994) 55–63.

[9] J.H. Hattingh and M.A. Henning, Characterizations of trees with equal domination parameters, J. Graph Theory 34 (2000) 142–153. https://doi.org/10.1002/1097-0118(200006)34:23.0.CO;2-V

[10] T.W. Haynes and M.A. Henning, Trees with unique minimum total dominating sets, Discuss. Math. Graph Theory 22 (2002) 233–246. https://doi.org/10.7151/dmgt.1172

[11] T.W. Haynes and M.A. Henning, Semipaired domination in graphs, J. Combin. Math. Combin. Comput. 104 (2018) 93–109.

[12] T.W. Haynes and M.A. Henning, Perfect graphs involving semitotal and semipaired domination, J. Comb. Optim. 36 (2018) 416–433. https://doi.org/10.1007/s10878-018-0303-9

[13] T.W. Haynes and M.A. Henning, Graphs with large semipaired domination number, Discuss. Math. Graph Theory 39 (2019) 659–671. https://doi.org/10.7151/dmgt.2143

[14] T.W. Haynes and P.J. Slater, Paired-domination and the paired-domatic-number, Congr. Numer. 109 (1995) 65–72.

[15] T.W. Haynes and P.J. Slater, Paired domination in graphs, Networks 32 (1998) 199–206. https://doi.org/10.1002/(SICI)1097-0037(199810)32:33.0.CO;2-F

[16] J.T. Hedetniemi, On unique minimum dominating sets in some Cartesian product graphs, Discuss. Math. Graph Theory 35 (2015) 615–628. https://doi.org/10.7151/dmgt.1822

[17] J.T. Hedetniemi, On unique minimum dominating sets in some repeated Cartesian product graphs, Australas. J. Combin. 62 (2015) 91–99.

[18] J.T. Hedetniemi, On graphs having a unique minimum independent dominating set, Australas. J. Combin. 68 (2017) 357–370.

[19] M.A. Henning and P. Kaemawichanurat, Semipaired domination in claw-free cubic graphs, Graphs Combin. 34 (2018) 819–844. https://doi.org/10.1007/s00373-018-1916-6

[20] M.A. Henning and P. Kaemawichanurat, Semipaired domination in maximal outerplanar graphs, J. Comb. Optim. 38 (2019) 911–926. https://doi.org/10.1007/s10878-019-00427-9

[21] M.A. Henning, A. Pandey and V. Tripathi, Complexity and algorithms for semipaired domination in graphs, in: Combinatorial Algorithms. IWOCA 2019, C. Colbourn, R. Grossi and N. Pisanti Ed(s), Lecture Notes in Comput. Sci. 11638 (2019) 278–289. https://doi.org/10.1007/978-3-030-25005-8_23

[22] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). https://doi.org/10.1007/978-1-4614-6525-6

[23] C.M. Mynhardt, Vertices contained in every minimum domination set of a tree, J. Graph Theory 31 (1999) 163–177. https://doi.org/10.1002/(SICI)1097-0118(199907)31:33.0.CO;2-T

[24] W. Siemes, J. Topp and L. Volkmann, On unique independent sets in graphs, Discrete Math. 131 (1994) 279–285. https://doi.org/10.1016/0012-365X(94)90389-1

[25] J. Topp, Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices, Discrete Math. 121 (1993) 199–210. https://doi.org/10.1016/0012-365X(93)90553-6

[26] W. Zhao, F. Wang and H. Zhang, Construction for trees with unique minimum dominating sets, Int. J. Comput. Math. Comput. Syst. Theory 3 (2018) 204–213. https://doi.org/10.1080/23799927.2018.1531930