A linear time algorithm for minimum equitable dominating set in trees
Keywords:Equitable domination, Linear time algorithm, Trees
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.
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
How to Cite
Copyright (c) 2021 Sohel Rana, Sk. Md. Abu Nayeem
This work is licensed under a Creative Commons Attribution 4.0 International License.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.