Abstract
The total k-domatic partition problem is to partition the vertices of a graph into k pairwise disjoint total dominating sets. In this paper, we prove that the 4-domatic partition problem is NP-complete for planar graphs of bounded maximum degree. We use this NP-completeness result to show that the total 4-domatic partition problem is also NP-complete for planar graphs of bounded maximum degree. We also show that the total k-domatic partition problem is linear-time solvable for any bipartite distance-hereditary graph by showing how to compute a weak elimination ordering of the graph in linear time. The linear-time algorithm for computing a weak elimination ordering of a bipartite distance-hereditary graph can lead to improvement on the complexity of several graph problems or alternative solutions to the problems such as signed total domination, minus total domination, k-tuple total domination, and total \(\{k\}\)-domination problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The graph is modified from [6].
References
Bouchemakh, I., Ouatiki, S.: On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset. Discrete Math. 309, 3674–3679 (2009)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)
Chang, M.-S., Hsieh, S., Chen, G.-H.: Dynamic programming on distance-hereditary graphs. In: Leong, H.W., Imai, H., Jain, S. (eds.) ISAAC 1997. LNCS, vol. 1350, pp. 344–353. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63890-3_37
Chen, B., Kim, J.H., Tait, M., Verstraete, J.: On coupon colorings of graphs. Discrete Appl. Math. 193, 94–101 (2015)
Chen, H., Jin, Z.: Coupon coloring of cographs. Appl. Math. Comput. 308, 90–95 (2017)
Goddard, W., Henning, M.A.: Thoroughly distributed colorings. arXiv preprint arXiv:1609.09684 (2016)
Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nordic J. Comput. 5, 128–142 (1998)
Koivisto, M., Laakkonen, P., Lauri, J.: NP-completeness results for partitioning a graph into total dominating sets. In: Cao, Y., Chen, J. (eds.) COCOON 2017. LNCS, vol. 10392, pp. 333–345. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62389-4_28
Lee, C.M., Wu, S.L., Chen, H.L., Chang, C.W., Lee, T.: A note on the complexity of the total domatic partition problem in graphs. J. Comb. Math. Comb. Comput. 108 (2017)
Lee, C.M.: Total \(k\)-domatic problem on some classes of graphs. Utilitas Mathematica, 109 (2018)
Poon, S.-H., Yen, W.C.-K., Ung, C.-T.: Domatic partition on several classes of graphs. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 245–256. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31770-5_22
Pradhan, D.: Complexity of certain functional variants of total domination in chordal bipartite graphs. Discrete Math. Algorithms Appl. 4 (2012)
Shi, Y., Wei, M., Yue, J., Zhao, Y.: Coupon coloring of some special graphs. J. Comb. Optim. 33, 156–164 (2017)
Acknowledgment
The work is supported by an internal research project of Ming Chuan University (2018/11/1–2019/3/31) and partially supported by Research Grant: MOST-106-2221-E-130-006 in Taiwan. The author is grateful to the anonymous referees for their valuable comments and suggestions to improve the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Lee, CM. (2019). Total k-Domatic Partition and Weak Elimination Ordering. In: Chang, CY., Lin, CC., Lin, HH. (eds) New Trends in Computer Technologies and Applications. ICS 2018. Communications in Computer and Information Science, vol 1013. Springer, Singapore. https://doi.org/10.1007/978-981-13-9190-3_57
Download citation
DOI: https://doi.org/10.1007/978-981-13-9190-3_57
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-9189-7
Online ISBN: 978-981-13-9190-3
eBook Packages: Computer ScienceComputer Science (R0)