شماره ركورد كنفرانس :
3503
عنوان مقاله :
Total [1, 2]-set in graphs with bounded tree-width
Author/Authors :
P. Sharifani Yazd University , M. Hooshmandasl Yazd University
كليدواژه :
[1, 2]-set , total [1, 2]-set , total [1, 2]-domination number , Tree decomposition , Bounded treewidth graphs
عنوان كنفرانس :
چهل و هفتمين كنفرانس رياضي ايران
چكيده لاتين :
A subset S⊆ V in a graph G = (V,E) is a total [1, 2]-set, if for every vertex ν of graph,1≤ |NG(ν) ⋂ 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).
