کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430594 | 688056 | 2012 | 9 صفحه PDF | دانلود رایگان |
An efficiently total dominating set of a graph G is a subset of its vertices such that each vertex of G is adjacent to exactly one vertex of the subset. If there is such a subset, then G is an efficiently total dominable graph (G is etd).In this paper, we prove NP-completeness of the etd decision problem on the class of planar bipartite graphs of maximum degree 3. Furthermore, we give an efficient decision algorithm for T3T3-free chordal graphs. A T3T3-free graph is a graph that does not contain as induced subgraph a claw, every edge of which is subdivided exactly twice. In the main part, we present three graph classes on which the weighted etd problem is polynomially solvable: claw-free graphs, odd-sun-free chordal graphs (including strongly chordal graphs) and graphs which only induce cycles of length divisible by four (including chordal bipartite graphs). In addition, claw-free etd graphs are shown to be perfect.
Journal: Journal of Discrete Algorithms - Volume 10, January 2012, Pages 61–69