Paper Info
Title
The algorithmic complexity of k-domatic partition of graphs
Abstract
Let G=(V,E) be a simple undirected graph, and k be a positive integer. A k-dominating set of G is a set of vertices S⊆V satisfying that every vertex in V∖S is adjacent to at least k vertices in S. A k-domatic partition of G is a partition of V into k-dominating sets. The k-domatic number of G is the maximum number of k-dominating sets contained in a k-domatic partition of G. In this paper we study the k-domatic number from both algorithmic complexity and graph theoretic points of view. We prove that it is $\mathcal{NP}$-complete to decide whether the k-domatic number of a bipartite graph is at least 3, and present a polynomial time algorithm that approximates the k-domatic number of a graph of order n within a factor of $(\frac{1}{k}+o(1))\ln n$, generalizing the (1+o(1))ln n approximation for the 1-domatic number given in [5]. In addition, we determine the exact values of the k-domatic number of some particular classes of graphs.
Year
DOI
Venue
2012
10.1007/978-3-642-33475-7_17
IFIP TCS
Keywords
Field
DocType
graph theoretic point,ln n approximation,k-dominating set,bipartite graph,k-domatic number,simple undirected graph,ln n,1-domatic number,algorithmic complexity,maximum number,k-domatic partition
Discrete mathematics,Combinatorics,Graph toughness,Graph power,Bipartite graph,Cycle graph,Independent set,Frequency partition of a graph,Graph partition,Mathematics,Domatic number
Conference
Citations 
PageRank 
References 
0
0.34
10
Authors
1
Name
Order
Citations
PageRank
Hongyu Liang18416.39