Total domination in graphs and transversals in hypergraphs

Michael Henning
School of Mathematical Sciences
University of KwaZulu-Natal
Pietermaritzburg, 3209 South Africa

Wednesday 5 July 2006

A set S of vertices in a graph G without isolated vertices is a total dominating set of G if every vertex of G is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set in G. The transversal number of a hypergraph is the minimum number of vertices meeting every edge. We observe that total domination in graphs can be translated to the problem of finding transversals in hypergraphs. In this talk, we survey recent results on total domination in graphs and present new results using transversals in hypergraphs.