article

Computing a minimum outer-connected dominating set for the class of chordal graphs

Authors:

D. PradhanAuthors Info & Claims

Information Processing Letters, Volume 113, Issue 14-16

Pages 552 - 561

https://doi.org/10.1016/j.ipl.2013.05.001

Published: 01 July 2013 Publication History

Abstract

For a graph G=(V,E), a dominating set is a set D@?V such that every vertex v@?V@?D has a neighbor in D. Given a graph G=(V,E) and a positive integer k, the minimum outer-connected dominating set problem for G is to decide whether G has a dominating set D of cardinality at most k such that G[V@?D], the induced subgraph by G on V@?D, is connected. In this paper, we consider the complexity of the minimum outer-connected dominating set problem for the class of chordal graphs. In particular, we show that the minimum outer-connected dominating set problem is NP-complete for doubly chordal graphs and undirected path graphs, two well studied subclasses of chordal graphs. We also give a linear time algorithm for computing a minimum outer-connected dominating set in proper interval graphs. Notice that proper interval graphs form a subclass of undirected path graphs as well as doubly chordal graphs.

References

[1]

Akhbari, M.H., Hasni, R., Favaron, O., Karami, H. and Sheikholeslami, S.M., On the outer-connected domination in graphs. J. Comb. Optim.

[2]

Bertossi, A.A., Dominating sets for split and bipartite graphs. Inform. Process. Lett. v19. 37-40.

Digital Library

[3]

Booth, K.S. and Johnson, J.H., Dominating sets in chordal graphs. SIAM J. Comput. v11. 191-199.

[4]

Booth, K.S. and Lueker, G.S., Testing for consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. System Sci. v13. 335-379.

Digital Library

[5]

Brandstädt, A., Le, V.B. and Spinrad, J.P., Graph Classes: A Survey. 1999. SIAM, Philadelphia.

[6]

Brandstädt, A., Dragan, F.F., Chepoi, V. and Voloshin, V., Dually chordal graphs. SIAM J. Discrete Math. v11 i3. 437-455.

[7]

Buneman, P., A characterisation of rigid circuit graphs. Discrete Math. v9. 205-212.

[8]

Cyman, J., The outer-connected domination number of a graph. Australas. J. Combin. v38. 35-46.

[9]

Fulkerson, D.R. and Gross, O.A., Incidence matrices and interval graphs. Pacific J. Math. v15. 835-855.

[10]

Garey, M.R. and Johnson, D.S., Computers and Intractability, A Guide to the Theory of NP-Completeness. 1979. W.H. Freeman and Company, San Francisco.

[11]

Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin. Theory Ser. B. v16. 47-56.

[12]

Gavril, F., A recognition algorithm for the intersection graphs of paths in trees. Discrete Math. v23 i3. 211-227.

[13]

. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (Eds.), Monographs and Textbooks in Pure and Applied Mathematics, vol. 209. Marcel Dekker Inc., New York.

[14]

Haynes, T.W., Hedetniemi, S.T. and Slater, P.J., Fundamentals of Domination in Graphs. 1998. Monographs and Textbooks in Pure and Applied Mathematics, 1998.Marcel Dekker Inc., New York.

[15]

Jamison, R.E. and Laskar, R., Elimination orderings of chordal graphs. In: Combinatorics and Applications, ISI, Calcutta. pp. 192-200.

[16]

Jiang, H. and Shan, E., Outer-connected domination number in graphs. Util. Math. v81. 265-274.

[17]

Lee, C.M., Variations of maximum-clique transversal sets on graphs. Ann. Oper. Res. v181. 21-66.

[18]

On the complexity of signed and minus total domination in graphs. Inform. Process. Lett. v109. 1177-1181.

Digital Library

[19]

Lee, C.M. and Chang, M.S., Variations of Y-dominating functions on graphs. Discrete Math. v308. 4185-4204.

[20]

Moscarini, M., Doubly chordal graphs, steiner trees, and connected domination. Networks. v23. 59-69.

[21]

Panda, B.S. and Das, S.K., A linear time recognition algorithm for proper interval graphs. Inform. Process. Lett. v87. 153-161.

Digital Library

[22]

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs. Inform. Process. Lett. v110. 1067-1073.

Digital Library

[23]

Pradhan, D., Algorithmic aspects of k-tuple total domination in graphs. Inform. Process. Lett. v112. 816-822.

Digital Library

[24]

Walter, J.R., Representations of chordal graphs as subtrees of a tree. J. Graph Theory. v2 i3. 265-267.

Cited By

Chaplick S(2023)Intersection graphs of non-crossing pathsDiscrete Mathematics10.1016/j.disc.2023.113498346:8Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.disc.2023.113498
Mohanapriya ARenjith PSadagopan N(2023)Short Cycles Dictate Dichotomy Status of the Steiner Tree Problem on Bisplit GraphsAlgorithms and Discrete Applied Mathematics10.1007/978-3-031-25211-2_17(219-230)Online publication date: 9-Feb-2023
https://dl.acm.org/doi/10.1007/978-3-031-25211-2_17
Wang XLi XHou BLiu WWu LGao S(2021)A greedy algorithm for the fault-tolerant outer-connected dominating set problemJournal of Combinatorial Optimization10.1007/s10878-020-00668-z41:1(118-127)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s10878-020-00668-z
Show More Cited By

Index Terms

Computing a minimum outer-connected dominating set for the class of chordal graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields
2. Theory of computation
  1. Design and analysis of algorithms

Index terms have been assigned to the content through auto-classification.

Recommendations

Finding outer-connected dominating sets in interval graphs

The outer-connected domination problem is abbreviated as the OCD problem.The OCD problem was known to be linear-time solvable on proper interval graphs.We solve the OCD problem on interval graphs in linear-time.We do so by developing a chainless ...
Complexity of total outer-connected domination problem in graphs

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-...
Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs

A set D ⊆ V of a graph G =( V , E ) is a dominating set of G if every vertex in V D has at least one neighbor in D . A dominating set D of G is a paired-dominating set of G if the induced subgraph, G [ D ], has a perfect ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © © 2013.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 July 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chaplick S(2023)Intersection graphs of non-crossing pathsDiscrete Mathematics10.1016/j.disc.2023.113498346:8Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.disc.2023.113498
Mohanapriya ARenjith PSadagopan N(2023)Short Cycles Dictate Dichotomy Status of the Steiner Tree Problem on Bisplit GraphsAlgorithms and Discrete Applied Mathematics10.1007/978-3-031-25211-2_17(219-230)Online publication date: 9-Feb-2023
https://dl.acm.org/doi/10.1007/978-3-031-25211-2_17
Wang XLi XHou BLiu WWu LGao S(2021)A greedy algorithm for the fault-tolerant outer-connected dominating set problemJournal of Combinatorial Optimization10.1007/s10878-020-00668-z41:1(118-127)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s10878-020-00668-z
Panda BPandey A(2016)Complexity of total outer-connected domination problem in graphsDiscrete Applied Mathematics10.1016/j.dam.2015.05.009199:C(110-122)Online publication date: 30-Jan-2016
https://dl.acm.org/doi/10.1016/j.dam.2015.05.009
Pradhan D(2016)On the complexity of the minimum outer-connected dominating set problem in graphsJournal of Combinatorial Optimization10.1007/s10878-013-9703-z31:1(1-12)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s10878-013-9703-z
Chang SLiu JWang Y(2016)The Outer-connected Domination Number of Sierpiński-like GraphsTheory of Computing Systems10.1007/s00224-015-9621-958:2(345-356)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s00224-015-9621-9
Lin CLiu JWang Y(2015)Finding outer-connected dominating sets in interval graphsInformation Processing Letters10.1016/j.ipl.2015.07.008115:12(917-922)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.ipl.2015.07.008

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.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents