Complexity of total outer-connected domination problem in graphs
Authors: 
B.S. Panda, Arti PandeyAuthors Info & Claims
Pages 110 - 122
Abstract
A set D V is called a total dominating set of a graph G = ( V, E ), if for all v V, | N G ( v ) D | 1 . A total dominating set D of G = ( V, E ) is called a total outer-connected dominating set if G V D is connected. The Minimum Total Outer-connected Domination problem for a graph G = ( V, E ) is to find a total outer-connected dominating set of minimum cardinality. The Total Outer-connected Domination Decision problem, the decision version of the Minimum Total Outer-connected Domination problem, is known to be NP-complete for general graphs. In this paper, we strengthen this NP-completeness result by showing that the Total Outer-connected Domination Decision problem remains NP-complete for chordal graphs, split graphs, and doubly chordal graphs. We prove that the Total Outer-connected Domination Decision problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for computing the total outer-connected domination number, the cardinality of a minimum total outer-connected dominating set, of a tree. We prove that the Minimum Total Outer-connected Domination problem cannot be approximated within a factor of ( 1 - ε ) ln | V | for any ε 0, unless NP DTIME ( | V | O ( log log | V | ) ) . Finally, we show that the Minimum Total Outer-connected Domination problem is APX-complete for bounded degree graphs.
References
[1]
M.H. Akhbari, R. Hasni, O. Favaron, H. Karami, S.M. Sheikholeslami, On the outer-connected domination in graphs, J. Comb. Optim., 26 (2013) 10-18.
[2]
P. Alimonti, V. Kann, Hardness of approximating problems on cubic graphs, Theoret. Comput. Sci., 237 (2000) 123-134.
[3]
A. Brandstädt, F.F. Dragan, V. Chepoi, V. Voloshin, Dually chordal graphs, SIAM J. Discrete Math., 11 (1998) 437-455.
[4]
M. Chlebík, J. Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs, Inform. and Comput., 206 (2008) 1264-1275.
[5]
B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput., 85 (1990) 12-75.
[6]
J. Cyman, The outer-connected domination number of a graph, Australas. J. Combin., 38 (2007) 35-46.
[7]
J. Cyman, Total outer-connected domination numbers in trees, Discuss. Math. Graph Theory, 30 (2010) 377-383.
[8]
J. Cyman, J. Raczek, Total outer-connected domination numbers of trees, Discrete Appl. Math., 157 (2009) 3198-3202.
[9]
R. Diestel, Graph Theory, Vol. 173, in: Graduate Texts in Mathematics, Springer, Berlin, 2010.
[10]
O. Favaron, H. Karami, S.M. Sheikholeslami, On the total outer-connected domination in graphs, J. Comb. Optim., 27 (2014) 451-461.
[11]
D.R. Fulkerson, O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math., 15 (1965) 835-855.
[12]
M.R. Garey, D.S. Johnson, Computers and Interactability: A Guide to the Theory of NP-completeness, W.H. Freeman and Co., San Francisco, New York, 1979.
[13]
J.H. Hattingh, E.J. Joubert, A note on the total outer-connected domination number of a tree, AKCE J. Graphs. Comb., 7 (2010) 223-227.
[14]
T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, Vol. 209, Marcel Dekker Inc., New York, 1998.
[15]
T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Marcel Dekker Inc., New York, 1998.
[16]
M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math., 309 (2009) 32-63.
[17]
M.A. Henning, A. Yeo, Total Domination in Graphs, Springer, 2013.
[18]
H.X. Jiang, L.Y. Kang, Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs, Acta Math. Sin. (Engl. Ser.), 27 (2011) 607-616.
[19]
H.X. Jiang, E. Shan, Outer-connected domination number in graph, Util. Math., 81 (2010) 265-274.
[20]
J.M. Keil, D. Pradhan, Computing a minimum outer-connected dominating set for the class of chordal graphs, Inform. Process. Lett., 113 (2013) 552-561.
[21]
B.S. Panda, A. Pandey, Algorithm and hardness results for outer-connected dominating set in graphs, Lecture Notes in Comput. Sci., 8344 (2014) 151-162.
[22]
C.H. Papadimitriou, M. Yannakakis, Optimization, approximation and complexity classes, J. Comput. System Sci., 43 (1991) 425-440.
[23]
D. Pradhan, Algorithmic aspects of k -tuple total domination in graphs, Inform. Process Lett., 112 (2012) 816-822.
[24]
D. Pradhan, On the complexity of the minimum outer-connected dominating set problem in graphs, J. Comb. Optim. (2013).
Index Terms
- Complexity of total outer-connected domination problem in graphs
Index terms have been assigned to the content through auto-classification.
Recommendations
Algorithmic aspect of stratified domination in graphs
Chartrand, Haynes, Henning and Zhang introduced a variation of domination called stratified domination in graphs. This paper studies stratified domination from an algorithmic point of view. A 2-stratified (or black-white) graph is a graph in which every ...
b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results
CALDAM 2016: Proceedings of the Second International Conference on Algorithms and Discrete Applied Mathematics - Volume 9602Let $$G=V,E$$ be a connected graph with at least two vertices. For a fixed positive integer $$b>1$$, a set $$D\subseteq V$$ is called a b-disjunctive total dominating set of G if for every vertex $$v\in V$$, v is either adjacent to a vertex of D or has ...
Algorithmic aspects of semitotal domination in graphs
AbstractFor a graph G = ( V , E ), a set D ⊆ V is called a semitotal dominating set of G if D is a dominating set of G, and every vertex in D is within distance 2 of another vertex of D. The Minimum Semitotal Domination problem is to find a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 30 January 2016
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in