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:

M.A. Henning

Michael A. Henning

University of Johannesburg

email: mahenning@uj.ac.za

0000-0001-8185-067X

S. Pal

Saikat Pal

Department of Applied Mathematics.
Indian Institute of Technology(ISM), Dhanbad
Dhanbad, Jharkhand-826004

email: palsaikat67@gmail.com

D. Pradhan

D. Pradhan

email: dina@iitism.ac.in

Title:

The semitotal domination problem in block graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 231-248

Received: 2019-04-19 , Revised: 2019-09-18 , Accepted: 2019-09-24 , Available online: 2019-11-18 , https://doi.org/10.7151/dmgt.2254

Abstract:

A set $D$ of vertices in a graph $G$ is a dominating set of $G$ if every vertex outside $D$ is adjacent in $G$ to some vertex in $D$. A set $D$ of vertices in $G$ is a semitotal dominating set of $G$ if $D$ is a dominating set of $G$ and every vertex in $D$ is within distance $2$ from another vertex of $D$. Given a graph $G$ and a positive integer $k$, the semitotal domination problem is to decide whether $G$ has a semitotal dominating set of cardinality at most $k$. The semitotal domination problem is known to be NP-complete for chordal graphs and bipartite graphs as shown in [M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57]. In this paper, we present a linear time algorithm to compute a minimum semitotal dominating set in block graphs. On the other hand, we show that the semitotal domination problem remains NP-complete for undirected path graphs.

Keywords:

domination, semitotal domination, block graphs, undirected path graphs, NP-complete

References:

  1. A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Boston, 1974).
  2. K.S. Booth and J.H. Johnson, Dominating sets in chordal graphs, SIAM J. Comput. 11 (1982) 191–199.
    https://doi.org/10.1137/0211015
  3. W. Goddard, M.A. Henning and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014) 67–81.
  4. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).
  5. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).
  6. 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
  7. M.A. Henning, Edge weighting functions on semitotal dominating sets, Graphs Combin. 33 (2017) 403–417.
    https://doi.org/10.1007/s00373-017-1769-4
  8. M.A. Henning and A.J. Marcon, On matching and semitotal domination in graphs, Discrete Math. 324 (2014) 13–18.
    https://doi.org/10.1016/j.disc.2014.01.021
  9. M.A. Henning and A.J. Marcon, Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory 36 (2016) 71–93.
    https://doi.org/10.7151/dmgt.1844
  10. M.A. Henning and A.J. Marcon, Semitotal domination in claw-free cubic graphs, Ann. Comb. 20 (2016)) 799–813.
    https://doi.org/10.1007/s00026-016-0331-z
  11. M.A. Henning and A.J. Marcon, Semitotal domination in graphs: Partition and algorithmic results, Util. Math. 106 (2018) 165–184.
  12. M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57.
    https://doi.org/10.1016/j.tcs.2018.09.019
  13. M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013).
    https://doi.org/10.1007/978-1-4614-6525-6
  14. Z. Shao and P. Wu, Complexity and approximation ratio of semitotal domination in graphs, Commun. Comb. Optim. 3 (2018) 143–150.
    https://doi.org/10.22049/CCO.2018.25987.1065
  15. W. Zhuang and G. Hao, Semitotal domination in trees, Discrete Math. Theoret. Comput. Sci. 20(2) (2018) #5.
    https://doi.org/10.23638/DMTCS-20-2-5

Close