Schaudt, Oliver
(2010).
On efficient total domination.
Working Paper.
|
PDF
zaik2010-597.pdf Download (109kB) | Preview |
Abstract
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.
| Item Type: | Preprints, Working Papers or Reports (Working Paper) | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-549921 | ||||||||
| Journal or Publication Title: | Information Processing Letters | ||||||||
| Date: | 2010 | ||||||||
| Language: | English | ||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||
| Subjects: | Data processing Computer science | ||||||||
| Refereed: | No | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54992 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |