Document Type : Research Paper

**Authors**

Department of Computer Science, Yazd University, Yazd, Iran

**Abstract**

For a graph $G=(V,E)$, a set $S \subseteq V$ is a $[1,2]$-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. $1 \leq \vert N(v) \cap S \vert \leq 2$. Moreover a set $S \subseteq V$ is a total $[1,2]$-set if for each vertex of $V$, it is the case that $1 \leq \vert N(v) \cap S \vert \leq 2$. The $[1,2]$-domination number of $G$, denoted $\gamma_{[1,2]}(G)$, is the minimum number of vertices in a $[1,2]$-set. Every $[1,2]$-set with cardinality of $\gamma_{[1,2]}(G)$ is called a $\gamma_{[1,2]}$-set. Total $[1,2]$-domination number and $\gamma_{t[1,2]}$-sets of $G$ are defined in a similar way. This paper presents a linear time algorithm to find a $\gamma_{[1,2]}$-set and a $\gamma_{t[1,2]}$-set in generalized series-parallel graphs.

**Keywords**

[1] A. V. Aho and J. E. Hopcroft, Design & Analysis of Computer Algorithms, Pearson Education India, 1974.

[2] S. C. Chang, J. J. Liu and Y. L. Wang, The weighted independent domination problem in series-parallel graphs,

Intelligent Systems and Applications, 274 (2015) 77–84.

Intelligent Systems and Applications, 274 (2015) 77–84.

[3] P. Chebolu, M. Cryan and R. Martin, Exact counting of euler tours for generalized series-parallel graphs, J. Discrete

Algorithms, 10 (2012) 110–122.

Algorithms, 10 (2012) 110–122.

[4] M. Chellali, T. W. Haynes, S. T. Hedetniemi and A. McRae, [1,2]-sets in graphs, Discrete Appl Math., 161 (2013)

2885–2893.

2885–2893.

[5] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks, 7 (1977) 247–261.

[6] C. J. Colbourn, P. J. Slater and L. K. Stewart, Locating dominating sets in series parallel networks, Congr. Numer,

56 (1987) 135–162.

56 (1987) 135–162.

[7] O. Etesami, N. Ghareghani, M. Habib, M.R. Hooshmandasl, R. Naserasr and P. Sharifani, When an optimal

dominating set with given constraints exists, Theor. Comput. Sci., 780 (2019) 54–65.

dominating set with given constraints exists, Theor. Comput. Sci., 780 (2019) 54–65.

[8] M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified np-complete graph problems, Theor. Comput. Sci.,

1 (1976) 237–267.

1 (1976) 237–267.

[9] A. Goharshadi and M. R. Hooshmandasl, M. Alambardar Meybodi, [1,2]-sets and [1,2]-total sets in trees with

algorithms, Discrete Appl. Math., 198 (2016) 136–146.

algorithms, Discrete Appl. Math., 198 (2016) 136–146.

[10] S. Guha and S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica, 20 (1998) 374–387.

[11] S. Guha and S. Khuller, Improved methods for approximating node weighted steiner trees and connected dominating sets, Inform Comput, 150 (1999) 57–74.

[12] E. O. Hare, S. T. Hedetniemi, R. C. Laskar, K. Peters and T. Wimer, Linear-time computability of combinatorial

problems on generalized-series-parallel graphs, Discrete Algorithms and Complexity, (1987) 437–457.

problems on generalized-series-parallel graphs, Discrete Algorithms and Complexity, (1987) 437–457.

[13] S. T. Hedetniemi, R. Laskar and J. Pfaff, A linear algorithm for finding a minimum dominating set in a cactus,

Discrete Appl Math., 13 (1986) 287–292.

Discrete Appl Math., 13 (1986) 287–292.

[14] J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput., 2 (1973)

135–158.

135–158.

[15] T. Kikuno, N. Yoshida and Y. Kakuda, A linear algorithm for the domination number of a series-parallel graph.

Discrete Appl. Math., 5 (1983) 299–311.

Discrete Appl. Math., 5 (1983) 299–311.

[16] M. B. Richey and R. G. Parker, Minimum-maximal matching in series-parallel graphs, European J. Oper. Res., 33

(1988) 98–105.

(1988) 98–105.

[17] K. Takamizawa, T. Nishizeki and N. Saito, Linear-time computability of combinatorial problems on series-parallel

graphs, J. Assoc. Comput. Mach., 29 (1982) 623–641.

graphs, J. Assoc. Comput. Mach., 29 (1982) 623–641.

[18] D. B. West, Introduction to graph theory, 2, Prentice hall Upper Saddle River, 2001.

[19] X. Yang and B. Wu, [1,2]-domination in graphs, Discrete Appl. Math., 175 (2014) 79–86.

[20] C.-C. Yen and R. Lee, A linear time algorithm to solve the weighted perfect domination problem in series-parallel

graphs, European J. Oper. Res., 73 (1994) 192–198.

graphs, European J. Oper. Res., 73 (1994) 192–198.

[21] F. Zou, Y. Wang, X. H. Xu, X. Li, H. Du, P. Wan and W. Wu, New approximations for minimum-weighted

dominating sets and minimum-weighted connected dominating sets on unit disk graphs, Theor. Comput. Sci., 412

(2011) 198–208.

dominating sets and minimum-weighted connected dominating sets on unit disk graphs, Theor. Comput. Sci., 412

(2011) 198–208.

March 2020

Pages 1-24

**Receive Date:**20 July 2017**Revise Date:**23 November 2019**Accept Date:**24 November 2019**Published Online:**01 March 2020