article

Algorithmic aspects of k-tuple total domination in graphs

Author:

D. PradhanAuthors Info & Claims

Information Processing Letters, Volume 112, Issue 21

Pages 816 - 822

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

Published: 01 November 2012 Publication History

Abstract

For a fixed positive integer k, a k-tuple total dominating set of a graph G=(V,E) is a subset TD"k of V such that every vertex in V is adjacent to at least k vertices of TD"k. In minimum k-tuple total dominating set problem (Mink-Tuple Total Dom Set), it is required to find a k-tuple total dominating set of minimum cardinality and Decide Mink-Tuple Total Dom Set is the decision version of Mink-Tuple Total Dom Set problem. In this paper, we show that Decide Mink-Tuple Total Dom Set is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that Mink-Tuple Total Dom Set can be solved in polynomial time. We also propose some hardness results and approximation algorithms for Mink-Tuple Total Dom Set problem.

References

[1]

Alimonti, P. and Kann, V., Hardness of approximating problems on cubic graphs. In: Lecture Notes in Comput. Sci., vol. 1203. pp. 288-298.

Digital Library

[2]

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A. and Protasi, M., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. 1999. Springer-Verlag, Berlin.

Digital Library

[3]

Brandstädt, A., Classes of bipartite graphs related to chordal graphs. Discrete Appl. Math. v32 i1. 51-60.

Digital Library

[4]

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

Digital Library

[5]

Chang, G.J. and Nemhauser, G., The k-domination and k-stability problems on sun-free chordal graphs. SIAM J. Algebraic Discrete Methods. v6 i4. 721-730.

[6]

Chlebí***k, M. and Chlebí***ková, J., Approximation hardness of dominating set problems in bounded degree graphs. Inform. and Comput. v206 i11. 1264-1275.

Digital Library

[7]

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., Introduction to Algorithms. 2002. Prentice Hall, India.

Digital Library

[8]

Farber, M., Characterizations of strongly chordal graphs. Discrete Math. v43 i2-3. 173-189.

[9]

Feige, U., A threshold of lnn for approximating set cover. J. ACM. v45 i4. 634-652.

Digital Library

[10]

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

[11]

. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (Eds.), Monogr. Textb. Pure Appl. Math., vol. 209. Marcel Dekker Inc., New York.

[12]

Haynes, T.W., Hedetniemi, S.T. and Slater, P.J., Fundamentals of Domination in Graphs. 1998. Monogr. Textb. Pure Appl. Math., 1998.Marcel Dekker Inc., New York.

[13]

Henning, M.A. and Kazemi, A.P., k-tuple total domination in graphs. Discrete Appl. Math. v158. 1006-1011.

Digital Library

[14]

M.A. Henning, A.P. Kazemi, k-tuple total domination in cross products of graphs, J. Comb. Optim., http://dx.doi.org/10.1007/s10878-011-9389-z.

[15]

Karp, R.M., Reducibility among combinatorial problems. In: Complexity of Computer Computations, Proc. Sympos., Plenum Press, New York. pp. 85-103.

[16]

Klasing, R. and Laforest, C., Hardness results and approximation algorithms of k-tuple domination in graphs. Inform. Process. Lett. v89. 75-83.

Digital Library

[17]

Laskar, R., Pfaff, J., Hedetniemi, S.M. and Hedetniemi, S.T., On the algorithmic complexity of total domination. SIAM J. Alg. Disc. Math. v5 i3. 420-425.

[18]

Liao, C.S. and Chang, G.J., k-tuple domination in graphs. Inform. Process. Lett. v87. 45-50.

Digital Library

[19]

Papadimitriou, C.H. and Yannakakis, M., Optimization, approximation and complexity classes. J. Comput. System Sci. v43. 425-440.

Cited By

Li PWang AShang J(2023)A simple optimal algorithm for k-tuple dominating problem in interval graphsJournal of Combinatorial Optimization10.1007/s10878-022-00932-445:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s10878-022-00932-4
Soulignac F(2021)Total 2-domination of proper interval graphsDiscrete Applied Mathematics10.1016/j.dam.2021.07.015302:C(256-262)Online publication date: 30-Oct-2021
https://dl.acm.org/doi/10.1016/j.dam.2021.07.015
Arapoglu ODagdeviren O(2020)Distributed Self-Stabilizing Capacitated Maximal Independent Set Construction in Wireless Sensor NetworksWireless Personal Communications: An International Journal10.1007/s11277-020-07528-3114:4(3271-3293)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s11277-020-07528-3
Show More Cited By

Algorithmic aspects of k-tuple total domination in graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
  2. Mathematical analysis
    1. Numerical analysis
2. Theory of computation

Recommendations

Algorithmic aspects of semitotal domination in graphs
Abstract
For 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 ...
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-...
k-tuple total domination in graphs

A set S of vertices in a graph G is a k-tuple total dominating set, abbreviated kTDS, of G if every vertex of G is adjacent to least k vertices in S. The minimum cardinality of a kTDS of G is the k-tuple total domination number of G. For a graph to have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Processing Letters

Information Processing Letters Volume 112, Issue 21

November, 2012

44 pages

ISSN:0020-0190

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2012.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 November 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li PWang AShang J(2023)A simple optimal algorithm for k-tuple dominating problem in interval graphsJournal of Combinatorial Optimization10.1007/s10878-022-00932-445:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s10878-022-00932-4
Soulignac F(2021)Total 2-domination of proper interval graphsDiscrete Applied Mathematics10.1016/j.dam.2021.07.015302:C(256-262)Online publication date: 30-Oct-2021
https://dl.acm.org/doi/10.1016/j.dam.2021.07.015
Arapoglu ODagdeviren O(2020)Distributed Self-Stabilizing Capacitated Maximal Independent Set Construction in Wireless Sensor NetworksWireless Personal Communications: An International Journal10.1007/s11277-020-07528-3114:4(3271-3293)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s11277-020-07528-3
Panda BGoyal P(2020)Hardness Results of Global Total k-Domination Problem in GraphsAlgorithms and Discrete Applied Mathematics10.1007/978-3-030-39219-2_8(92-101)Online publication date: 13-Feb-2020
https://dl.acm.org/doi/10.1007/978-3-030-39219-2_8
(2018)Domination parameters with number 2Discrete Applied Mathematics10.1016/j.dam.2017.08.017235:C(23-50)Online publication date: 30-Jan-2018
https://dl.acm.org/doi/10.1016/j.dam.2017.08.017
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
Zhao YShan E(2016)An efficient algorithm for distance total domination in block graphsJournal of Combinatorial Optimization10.1007/s10878-014-9758-531:1(372-381)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s10878-014-9758-5
Belhoul YYahiaoui SKheddouci H(2014)Efficient self-stabilizing algorithms for minimal total k-dominating sets in graphsInformation Processing Letters10.1016/j.ipl.2014.02.002114:7(339-343)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1016/j.ipl.2014.02.002
Mark Keil JPradhan D(2013)Computing a minimum outer-connected dominating set for the class of chordal graphsInformation Processing Letters10.1016/j.ipl.2013.05.001113:14-16(552-561)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1016/j.ipl.2013.05.001

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