a linear algorithm for computing γ[1,2] γ[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.