Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G=(V,E) is a subset TDk of V such that every vertex in V is adjacent to at least k vertices of TDk. In minimum k-tuple total dominating set problem (Mink-Tuple Total Dom Set), it is required to find a k-tuple total dominating...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2012-11, Vol.112 (21), p.816-822
Main Author: Pradhan, D.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
APX-complete
Codes
Data processing
Domination
Graph algorithms
Graphs
Hardness
Integers
k-Tuple total domination
Mathematical analysis
NP-complete
Optimization techniques
Set theory
Studies
Total domination
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a fixed positive integer k, a k-tuple total dominating set of a graph G=(V,E) is a subset TDk of V such that every vertex in V is adjacent to at least k vertices of TDk. 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. ► We study on algorithmic aspects of the problem of finding minimum k-tuple total dominating set. ► We prove that for any k>0, the problem of finding minimum k-tuple total dominating set is NP-hard for split graphs and bipartite graphs. ► We show that a minimum k-tuple total dominating set can be found for chordal bipartite graphs in polynomial time. ► We present some hardness and approximation results on the problem of finding minimum k-tuple total dominating set.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2012.07.010