2017/07/20 by Pouyeh Sharifani, Sharifani, P., M. R. Hooshmandasl +1
Computer Science · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1707.06443
openalex publication_date 2017/07/20 · openalex created_date 2017/07/31 · openalex updated_date 2026/07/28
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 ≤ \vert N(v) ∩ S \vert ≤ 2. Moreover a set S ⊆ V is a total [1,2]-set if for each vertex of V, it is the case that 1 ≤ \vert N(v) ∩ S \vert ≤ 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.