A linear time algorithm for minimum equitable dominating set in trees
DOI:
https://doi.org/10.22199/issn.0717-6279-4552Keywords:
Equitable domination, Linear time algorithm, TreesAbstract
Let G = (V, E) be a graph. A subset De of V is said to be an equitable dominating set if for every v ∈ V \ De there exists u ∈ De such that uv ∈ E and |deg(u) − deg(v)| ≤ 1, where, deg(u) and deg(v) denote the degree of the vertices u and v respectively. An equitable dominating set with minimum cardinality is called the minimum equitable dominating set and its cardinality is called the equitable domination number and it is denoted by γe. The problem of finding minimum equitable dominating set in general graphs is NP-complete. In this paper, we give a linear time algorithm to determine minimum equitable dominating set of a tree.
References
J. A. Bondy and U. S. R. Murty, Graph theory with applications. Amsterdam: North Holland, 1976.
V. Swaminathan and K. M. Dharmalingam, “Degree equitable domination on graphs”, Kragujevac journal of mathematics, vol. 35, no. 1, pp. 191–197, 2011 [On line]. Available: https://bit.ly/36gGHuZ
A. Sugumaran and E. Jayachandran, “Domination, equitable and end equitable domination numbers of some graphs”, Journal of computer and mathematical sciences, vol. 10, no. 3, pp. 399-409, 2019. [On line]. Available: https://bit.ly/2UWxkOv
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs. New York (NY): Marcel Dekker, 1998.
E. J. Cockayne, S. E. Goodman and S. T. Hedetniemi, “A linear algorithm for the domination number of a tree”, Information Processing Letters, vol. 4, no. 2, pp. 41-44, 1975. https://doi.org/10.1016/0020-0190(75)90011-3
Published
How to Cite
Issue
Section
Copyright (c) 2021 Sohel Rana, Sk. Md. Abu Nayeem
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
