A linear time algorithm for minimum equitable dominating set in trees





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.

Author Biographies

Sohel Rana, Aliah University.

Dept. of Mathematics and Statistics.

Sk. Md. Abu Nayeem, Aliah University.

Dept. of Mathematics and Statistics.


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

S. Rana and S. M. A. Nayeem, “A linear time algorithm for minimum equitable dominating set in trees”, Proyecciones (Antofagasta, On line), vol. 40, no. 4, pp. 805-814, Jul. 2021.