A linear time algorithm for minimum equitable dominating set in trees
-
Rana, Sohel [1] ; Nayeem, Sk. Md. Abu [1]
-
[1] Aliah University
Aliah University
India
-
- Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 40, Nº. 4, 2021, págs. 805-814
- Idioma: inglés
- DOI: 10.22199/issn.0717-6279-4552
- Enlaces
-
Resumen
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.
-
Referencias bibliográficas
- 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,...
- A. Sugumaran and E. Jayachandran, “Domination, equitable and end equitable domination numbers of some graphs”, Journal of computer and mathematical...
- 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,...
