A transition from total domination in graphs to transversals in hypergraphs

Abstract

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 paper we survey bounds on the total domination of a graph in terms of the order of the graph, and provide a transition from total domination in graphs to transversals in hypergraphs.

Quaestiones Mathematicae 30(2007), 417–436