Schaudt, Oliver
(2012).
On weighted efficient total domination.
Journal of Discrete Algorithms, 10 (1).
pp. 61-69.
Elsevier.
|
PDF
zaik2010-598.pdf - Submitted Version Download (148kB) | Preview |
Abstract
An efficiently total dominating set of a graph G is a subset of its vertices, such that every 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 present two graph classes on which the weighted etd problem is polynomially solvable: claw-free graphs and graphs which only induce cycles of length divisible by four. Furthermore, claw-free etd graphs are shown to be perfect.
| Item Type: | Journal Article | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-549936 | ||||||||
| Journal or Publication Title: | Journal of Discrete Algorithms | ||||||||
| Volume: | 10 | ||||||||
| Number: | 1 | ||||||||
| Page Range: | pp. 61-69 | ||||||||
| Date: | 2012 | ||||||||
| Publisher: | Elsevier | ||||||||
| 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/54993 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |