A Linear Algorithm for Computing $\gamma_{_{[۱,۲]}}$-set in Generalized Series-Parallel Graphs

For a graph $G=(V,E)$, a set $S \subseteq V$ is a $[۱,۲]$-set if it is a dominating set for $G$ and each vertex $v \in V \setminus S$ is dominated by at most two vertices of $S$, i.e. $۱ \leq \vert N(v) \cap S \vert \leq ۲$. Moreover a set $S \subseteq V$ is a total $[۱,۲]$-set if for each vertex of $V$, it is the case that $۱ \leq \vert N(v) \cap S \vert \leq ۲$. The $[۱,۲]$-domination number of $G$, denoted $\gamma_{[۱,۲]}(G)$, is the minimum number of vertices in a $[۱,۲]$-set. Every $[۱,۲]$-set with cardinality of $\gamma_{[۱,۲]}(G)$ is called a $\gamma_{[۱,۲]}$-set. Total $[۱,۲]$-domination number and $\gamma_{t[۱,۲]}$-sets of $G$ are defined in a similar way. This paper presents a linear time algorithm to find a $\gamma_{[۱,۲]}$-set and a $\gamma_{t[۱,۲]}$-set in generalized series-parallel graphs.

Keywords:

domination , Total domination , [۱ , Total [۱ , ۲]-set , Series-parallel graphs , Generalized series-parallel graph