TY - GEN
T1 - Domatic partition on several classes of graphs
AU - Poon, Sheung Hung
AU - Yen, William Chung Kung
AU - Ung, Chin Ting
N1 - Funding Information:
This research was supported by National Science Council, Taiwan, under the grant numbers NSC99-2221-E-128-003 and NSC100-2628-E-007-020-MY3.
PY - 2012
Y1 - 2012
N2 - The domatic number of a graph G, denoted by DN(G), is the maximum number k such that V can be partitioned into k disjoint dominating sets. The domatic partition problem is to find a partition of the vertices of G into DN(G) dominating sets. The k-domatic partition problem with fixed k is to find a partition of the vertices of G into k dominating sets. In this paper, we show that 3-domatic partition problem is NP-complete on planar bipartite graphs, and the domatic partition problem is NP-complete on co-bipartite graphs. We further show that the unique 3-domatic partition problem is NP-hard on general graphs. Moreover, we propose an O(n)-time algorithm on the 3-domatic partition problem for maximal planar graphs, and O(n 3)-time algorithms on the domatic partition problem for P 4-sparse graphs and tree-cographs, respectively.
AB - The domatic number of a graph G, denoted by DN(G), is the maximum number k such that V can be partitioned into k disjoint dominating sets. The domatic partition problem is to find a partition of the vertices of G into DN(G) dominating sets. The k-domatic partition problem with fixed k is to find a partition of the vertices of G into k dominating sets. In this paper, we show that 3-domatic partition problem is NP-complete on planar bipartite graphs, and the domatic partition problem is NP-complete on co-bipartite graphs. We further show that the unique 3-domatic partition problem is NP-hard on general graphs. Moreover, we propose an O(n)-time algorithm on the 3-domatic partition problem for maximal planar graphs, and O(n 3)-time algorithms on the domatic partition problem for P 4-sparse graphs and tree-cographs, respectively.
UR - http://www.scopus.com/inward/record.url?scp=84865032818&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31770-5_22
DO - 10.1007/978-3-642-31770-5_22
M3 - Conference contribution
AN - SCOPUS:84865032818
SN - 9783642317699
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 245
EP - 256
BT - Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings
T2 - 6th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2012
Y2 - 5 August 2012 through 9 August 2012
ER -