BEGIN:VCALENDAR
VERSION:2.0
PRODID:"-//Durham University/Events"
METHOD:PUBLISH
BEGIN:VEVENT
UID:DUEVENT11783
SEQUENCE:0
DTSTAMP:20130619T095647Z
DTSTART:20120301T160000Z
DTEND:20120301T170000Z
STATUS:CONFIRMED
TRANSP:OPAQUE
LOCATION:E245
SUMMARY:Minimal Dominating Sets in Graphs: Enumeration, Combinatorial Boun
 ds and Graph Classes 
DESCRIPTION:In 2008 Fomin, Grandoni, Pyatkin and Stepanov provided an exac
 t exponential time algorithm to enumerate all minimal dominating sets of a
  graph. Its main consequence was the first non trivial upper bound on the 
 number of minimal dominating sets; the maximum number of minimal dominatin
 g sets that a graph on n vertices can have is at most 1.7159^n. This upper
  bound might not be tight, since no examples of graphs with 1.5705^n or mo
 re minimal dominating sets are known.  This talk considers exact exponenti
 al algorithms to enumerate minimal dominating sets when the input graphs a
 re restricted to certain graph classes, among them chordal graphs, cograph
 s and chain graphs.  The following types of results exploiting the structu
 re of the particular graph classes are presented:  (i) enumeration algorit
 hms based on branching algorithms and their analysis via upper bounding th
 e number of leaves in search trees,  (ii) upper bounds on the maximum numb
 er of minimal dominating sets in n-vertex graphs obtained via branching al
 gorithms or combinatorial proofs,  (iii) lower bounds on the maximum numbe
 r of minimal dominating sets.  In some cases, we provide examples of graph
 s whose number of minimal dominating sets exactly matches the proved upper
  bound for that class, thereby showing that these bounds are tight. 
END:VEVENT
END:VCALENDAR