شماره ركورد كنفرانس :
3503
عنوان مقاله :
Total [1, 2]-set in graphs with bounded tree-width
Author/Authors :
P. Sharifani Yazd University , M. Hooshmandasl Yazd University
كليدواژه :
Tree decomposition , Bounded treewidth graphs , total [1, 2]-domination number , total [1, 2]-set , [1, 2] -set
عنوان كنفرانس :
چهل و هفتمين كنفرانس رياضي ايران
چكيده لاتين :
A subset S ⊆ V in a graph G = (V,E) is a total [1, 2]-set, if for every vertex v of graph,1 ≤ |NG(v) ∩ S| ≤ 2. If the graph G has at least one total [1, 2]-set then the cardinality of
smallest such set is denoted by γ t[1,2](G). In this paper, we prove that the total [1, 2]-set problem is NP-complete for chordal graphs. In addition, we proposed an algorithm to solve the total [1, 2]-set problem for every graph G with bounded tree-width in time O(9tw(G)n).
