1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Unique Minimum Semipaired Dominating Sets in Trees

Published Online: 29 Sep 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 02 Feb 2020
Accepted: 08 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let G be a graph with vertex set V. A subset SV 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

MSC 2010

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

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

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

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

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

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

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

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

[9] J.H. Hattingh and M.A. Henning, Characterizations of trees with equal domination parameters, J. Graph Theory 34 (2000) 142–153. doi:10.1002/1097-0118(200006)34:2〈142::AID-JGT3〉3.0.CO;2-VSearch in Google Scholar

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

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

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

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

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

[15] T.W. Haynes and P.J. Slater, Paired domination in graphs, Networks 32 (1998) 199–206. doi:10.1002/(SICI)1097-0037(199810)32:3〈199::AID-NET4〉3.0.CO;2-FSearch in Google Scholar

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

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

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

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

[20] M.A. Henning and P. Kaemawichanurat, Semipaired domination in maximal outer-planar graphs, J. Comb. Optim. 38 (2019) 911–926. doi:10.1007/s10878-019-00427-910.1007/s10878-019-00427-9Search in Google Scholar

[21] M.A. Henning, A. Pandey and V. Tripathi, Complexity and algorithms for semi-paired domination in graphs, in: C. Colbourn, R. Grossi, N. Pisanti (Eds), Combinatorial Algorithms. IWOCA 2019, Lecture Notes in Comput. Sci. 11638 (2019) 278–289. doi:10.1007/978-3-030-25005-8_2310.1007/978-3-030-25005-8_23Search in Google Scholar

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

[23] C.M. Mynhardt, Vertices contained in every minimum domination set of a tree, J. Graph Theory 31 (1999) 163–177. doi:10.1002/(SICI)1097-0118(199907)31:3〈163::AID-JGT2〉3.0.CO;2-TSearch in Google Scholar

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

[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. doi:10.1016/0012-365X(93)90553-610.1016/0012-365X(93)90553-6Search in Google Scholar

[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. doi:10.1080/23799927.2018.153193010.1080/23799927.2018.1531930Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo