A Linear Algorithm for Computing γ[1,2]-set in Generalized Series-Parallel Graphs

For a graph G=(V,E), a set S⊆V is a [1,2]-set if it is a dominating set for G and each vertex v∈V∖S is dominated by at most two vertices of S, i.e. 1≤|N(v)∩S|≤2. Moreover a set S⊆V is a total [1,2]-set if for each vertex of V, it is the case that 1≤|N(v)∩S|≤2. The [1,2]-domination number of G, denoted γ[1,2](G), is the minimum number of vertices in a [1,2]-set. Every [1,2]-set with cardinality of γ[1,2](G) is called a γ[1,2]-set. Total [1,2]-domination number and γt[1,2]-sets of G are defined in a similar way. This paper presents a linear time algorithm to find a γ[1,2]-set and a γt[1,2]-set in generalized series-parallel graphs.