max planck institut
MPI-INF or MPI-SWS or Local Campus Event Calendar
What and Who
|Title:||The structure of total dominating sets|
|coming from:||U Cologne|
|Event Type:||AG1 Mittagsseminar (own work)|
|Visibility:||D1, D3, D5, SWS, D4, RG1, MMCI|
We use this to send out email in the morning.
Date, Time and Location
|Date:||Friday, 14 January 2011|
|Building:||E1 4 - MPI-INF|
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.
|Video Broadcast:||No||To Location:|
Tags, Category, Keywords and additional notes
|Created by:||Benjamin Doerr/AG1/MPII/DE, 12/21/2010 02:26 PM||Last 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.