34
Views
0
CrossRef citations to date
0
Altmetric
Articles

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

Pages 134-147 | Received 22 Nov 2019, Accepted 01 May 2020, Published online: 04 Jun 2020
 

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.

2010 Mathematics Subject Classifications:

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 [Citation12].

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.