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

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.

Keywords:

• Total domatic partition
• total domination
• weak elimination ordering
• distance-hereditary graph

2010 Mathematics Subject Classifications:

• 05C69
• 05C85
• 68R10
• 68W40

Acknowledgments

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.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 The graph is modified from [12].

Additional information

Funding

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; Taiwanese Ministry of Science and Technology.