شماره ركورد كنفرانس :
4079
عنوان مقاله :
Total [1,2]-set in graphs with bounded tree-width
پديدآورندگان :
Sharifani P pouyeh.sharifani@gmail.com Yazd University , Hooshmandasl M hooshmandasl@yazd.ac.ir Yazd University
كليدواژه :
total [1,2] , set , total [1,2] , domination number , Tree decomposition , Bounded tree , width graphs
عنوان كنفرانس :
چهل و هفتمين كنفرانس رياضي ايران
چكيده فارسي :
A subset S ⊆ V in a graph G = (V,E) is a total [1,2]-set, if for every vertex v of graph, 1 ≤ |N_G (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(9^{tw(G)}n)
