DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

T.W. Haynes

Teresa W Haynes

Department of Mathematics and Statistics, East Tenessee State University

email: haynes@etsu.edu

0000-0002-0865-0871

M.A. Henning

Michael A. Henning

University of Johannesburg

email: mahenning@uj.ac.za

0000-0001-8185-067X

Title:

Unique minimum semipaired dominating sets in trees

PDF

Source:

Discussiones Mathematicae Graph Theory 43(1) (2023) 35-53

Received: 2020-02-02 , Revised: 2020-07-07 , Accepted: 2020-07-08 , Available online: 2020-08-27 , https://doi.org/10.7151/dmgt.2349

Abstract:

Let $G$ be a graph with vertex set $V$. A subset $S \subseteq V$ is a semipaired dominating set of $G$ if every vertex in $V \setminus 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

References:

  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:2<142::AID-JGT3>3.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:3<199::AID-NET4>3.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:3<163::AID-JGT2>3.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
Close