Article in volume
Authors:
Title:
The semitotal domination problem in block graphs
PDFSource:
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:
- A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Boston, 1974).
- 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 - W. Goddard, M.A. Henning and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014) 67–81.
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).
- 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 - 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 - 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 - 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 - 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 - M.A. Henning and A.J. Marcon, Semitotal domination in graphs: Partition and algorithmic results, Util. Math. 106 (2018) 165–184.
- 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 - M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - 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 - 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