# On efficient total domination

Schaudt, Oliver
(2010)
*On efficient total domination.*

Technical Report
, 8 p.

## 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.

Actions:

Download: |
Postscript
Download (577kB) | Preview |
---|---|

Download: |
PDF
Download (109kB) | Preview |

Editorial actions: |
View Item (Login required) |

Content information:

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 |