The complexity of total k-domatic partition and total R-domination on graphs with weak elimination orderings. Issue 3 (2nd July 2020)

• Record Type: Journal Article
• Authors: Lee, Chuan-Min
• Is Part Of: International journal of computer mathematics. Volume 5:Issue 3(2020)
• Page Start: 134
• Page End: 147
• Publication Date: 2020-07-02
• Subjects: Total domatic partition -- total domination -- weak elimination ordering -- distance-hereditary graph; 05C69 -- 05C85 -- 68R10 -- 68W40; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1771427
• Languages: English
• ISSNs: 2379-9927

Abstract

Abstract : In this paper, we propose two linear-time algorithms. One is for computing a weak elimination ordering of a bipartite distance-hereditary graph, and the other one is an alternative algorithm to solve the total R -domination problem for any chordal bipartite graph with a weak elimination ordering. Our two linear-time algorithms lead to a unified approach to several variations of total domination problems for bipartite distance-hereditary graphs. We also show that tthe total 3-domatic partition problem is NP-complete for planar graphs of maximum degree 9 and planar bipartite graphs of maximum degree 12, and show that the 4-domatic partition problem for planar graphs of maximum degree d is polynomial-time reducible to the total 4-domatic partition problem for planar graphs of maximum degree d + 1.