Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D3
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The structure of total dominating sets
Speaker:Oliver Schaudt
coming from:U Cologne
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D3, D5, SWS, D4, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 14 January 2011
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4 - MPI-INF
Room:024
Abstract

Recently, Bacso and Tuza proved a theorem that gives a full characterization of the graphs that hereditarily have a connected dominating set satisfying prescribed hereditary properties. Their result is a 'high point' in the development of structural domination and completely solves a question which was (implicitely) stated 25 years ago.

Using their result, we derive a characterization of the graphs that hereditarily have a total dominating set whose connected components satisfy certain prescribed hereditary properties. This is the total domination equivalent to the theorem of Bacso and Tuza. In particular, our theory provides a characterization of the graphs that hereditarily have a total dominating set inducing the disjoint union of complete graphs. This inherits a characterization of the graphs whose any subgraph has a vertex-dominating induced matching. However, some cases do not permit a 'nice' characterization. We also discuss this phenomenon and give some partial characterizations.

Contact
Name(s):Benjamin Doerr
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Benjamin Doerr/AG1/MPII/DE, 12/21/2010 02:26 PMLast modified by:Uwe Brahm/MPII/DE, 01/14/2011 06:01 AM
  • Benjamin Doerr, 12/30/2010 02:07 PM
  • Benjamin Doerr, 12/21/2010 02:26 PM -- Created document.