On efficient total domination
On efficient total domination.
Technical Report , 8 p.
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 dominatable graph (G is etd). We show that the corresponding etd decision problem is NP-complete on (1,2)-colorable chordal graphs and on planar bipartite graphs of maximum degree 3 and obtain polynomial solvability on T_3-free chordal graphs, implying polynomial solvability on interval graphs and circular arc graphs.
|Depositing User:||Oliver Schaudt|
|Date Deposited:||08 Jun 2011 00:00|
|Last Modified:||09 Jan 2012 14:17|