The complexity of total k-domatic partition and total R-domination on graphs with weak elimination orderings

References

• H. Aram, S.M. Sheikholeslami, and L. Volkmann, On the total number of regular graphs, Trans. Combin. 1 (2012), pp. 45–51.
   Google Scholar
• G. Argiroffo, V. Leoni, and P. Torres, On the complexity of k-tuple total and total {k}-dominations for some subclasses of bipartite graphs, Inform. Process. Lett. 138 (2018), pp. 75–80. doi: 10.1016/j.ipl.2018.06.007
   Google Scholar
• S. Arumugam and A. Thuraiswamy, Total domatic number of a graph, Indian J. Pure Appl. Math.29 (1998), pp. 513–515.
   Web of Science ®Google Scholar
• I. Bouchemakh and S. Ouatiki, 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 (2009), pp. 3674–3679. doi: 10.1016/j.disc.2008.01.034
   Web of Science ®Google Scholar
• A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, Society for Industrial and Applied Mathematics, 1999.
   Google Scholar
• M.-S. Chang, S.-Y. Hsieh, G.-H. Chen, Dynamic programming on distance-hereditary graphs, in Proceedings of the 7th International Symposium on Algorithms and Computation (ISAAC'97), Singapore, Lecture Notes in Computer Science: 1350, 1997, pp. 344–353, 1997.
   Google Scholar
• H. Chen and Z. Jin, Coupon coloring of cographs, Appl. Math. Comput. 308 (2017), pp. 90–95.
   Web of Science ®Google Scholar
• B. Chen, J.H. Kim, M. Tait, and J. Verstraete, On coupon colorings of graphs, Discrete Appl. Math.193 (2015), pp. 94–101. doi: 10.1016/j.dam.2015.04.026
   Web of Science ®Google Scholar
• E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), pp. 211–219. doi: 10.1002/net.3230100304
   Web of Science ®Google Scholar
• E. Dahlhaus, J. Kratochvíl, P.D. Manuel, and M. Miller, Transversal partitioning in balanced hypergraphs, Discrete Appl. Math. 79 (1997), pp. 75–89. doi: 10.1016/S0166-218X(97)00034-6
   Web of Science ®Google Scholar
• M.R. Garey, D.S. Johnson, and L. Stockmeyer, Sime simplified NP-complete graph problems, Theor. Comput. Sci. 1 (1976), pp. 237–267. doi: 10.1016/0304-3975(76)90059-1
   Google Scholar
• W. Goddard and M.A. Henning, Thoroughly distributed colorings, preprint (2016), Available at arXiv: 1609.09684.
   Google Scholar
• P. Heggernes and J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput.5 (1998), pp. 128–142.
   Google Scholar
• M. Koivisto, P. Laakkonen, and J. Lauri, NP-completeness results for partitioning a graph into total dominating sets, Theor. Comput. Sci. (2018). Available at https://doi.org/10.1016/j.tcs.2018.04.006.
   PubMed Web of Science ®Google Scholar
• C.-M. Lee, On the complexity of signed and minus total domination in graphs, Inform. Process. Lett.109 (2009), pp. 1177–1181. doi: 10.1016/j.ipl.2009.08.002
   Web of Science ®Google Scholar
• C.-M. Lee, Signed and minus total domination on subclasses of bipartite graphs, Ars Combin. 100 (2011), pp. 129–149.
   Web of Science ®Google Scholar
• C.-M. Lee, R-total domination on convex bipartite graphs, J. Combin. Math. Combin. Comput. 81 (2012), pp. 209–224.
   Google Scholar
• C.-M. Lee, Total k-domatic partition and weak eliminatin ordering, in Proceedings of 2018 International Computer Symposium (ICS2018), Yunlin, Taiwan, December 20–22, 2018.
   Google Scholar
• C.-M. Lee, Total k-domatic problem on some classes of graphs, Util. Math. 109 (2018), pp. 29–43.
   Web of Science ®Google Scholar
• C.-M. Lee and M.-S. Chang, Variations of Y-dominating functions on graphs, Discrete Math. 308 (2008), pp. 4185–4204. doi: 10.1016/j.disc.2007.08.080
   Web of Science ®Google Scholar
• C.-M. Lee, S.-L. Wu, H.-L. Chen, C.-W. Chang, and T. Lee, A note on the complexity of the total domatic partition problem in graphs, J. Combin. Math. Combin. Comput. 108 (2019), pp. 3–14.
   Google Scholar
• S.H. Poon, W.C.K. Yen, C.T. Ung, Domatic partition on several classes of graphs, in Proceedings of COCOA 2012, Banff, Canada, Lecture Notes in Computer Science: 7402, pp. 245–256, 2012.
   Google Scholar
• D. Pradhan, Complexity of certain functional variants of total domination in chordal bipartite graphs, Discrete Math. Algor. Appl. 4 (2012), pp. 1250045 (19 pages).
   Google Scholar
• Y. Shi, M. Wei, J. Yue, and Y. Zhao, Coupon coloring of some special graphs, J, Combin. Optim. 33 (2017), pp. 156–164. doi: 10.1007/s10878-015-9942-2
   Web of Science ®Google Scholar
• R. Uehara, Linear time algorithms on chordal bipartite and strongly chordal graphs, in Proceedings of the 29th International Colloquium on Automata, Language, and Programming, Malaga, Spain, Lecture Notes in Computer Science: 2380, pp. 993–1004, 2002.
   Google Scholar
• R. Uehara, Erratum: Efficient algorithms on chordal bipartite graphs and strongly chordal graphs. Available at https://www.jaist.ac.jp/uehara/ps/chordal-linear-full.ps.gz.
   Google Scholar
• B. Zelinka, Total domatic number of cacti, Math. Slovaca 38 (1988), pp. 207–214.
   Google Scholar
• B. Zelinka, Total domatic number and degrees of vertices of a graph, Math. Slovaca 39 (1989), pp. 7–11.
   Google Scholar
• B. Zelinka, Regular totally domatically full graphs, Discrete Math. 86 (1990), pp. 71–79. doi: 10.1016/0012-365X(90)90350-Q
   Web of Science ®Google Scholar
• B. Zelinka, Domination in generalized Petersen graphs, Czech. Math. J. 52 (2002), pp. 11–16. doi: 10.1023/A:1021759001873
   Web of Science ®Google Scholar