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 -