On efficient total domination

Schaudt, Oliver (2010) 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.

Download: [img] Postscript
Download (577kB) | Preview
Download: [img] PDF
Download (109kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2010-597
Depositing User: Oliver Schaudt
Date Deposited: 08 Jun 2011 00:00
Last Modified: 09 Jan 2012 14:17
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/597