Title of article :
A linear-time algorithm to compute total [1, 2]-domination number of block graphs
Author/Authors :
Sharifani, Pouyeh Institute for Research in Fundamental Sciences (IPM), Tehran, Iran , Hooshmandasl, Mohammadreza Department of Computer Science - University of Mohaghegh Ardabili, Ardabil, Iran , Alikhani, Saeid Department of Mathematics - Yazd University, Yazd, Iran
Abstract :
Let G = (V, E) be a simple graph without isolated vertices. A set D ⊂ V is a total [1, 2]-dominating set if for every vertex v ∈ V , 1 ≤ |N(v) ∩ D| ≤ 2. The total [1, 2]-domination problem is to determine the total [1, 2]-domination number γt[1,2](G), which is the minimum cardinality of a total [1, 2]-dominating set for a graph G. In this paper, we present a linear-time algorithm to compute γt[1,2](G) for a block graph G.
Keywords :
Total [1, 2]-set , Dominating set , Block graph
Journal title :
AUT Journal of Mathematics and Computing
