Total Domination of Graphs and Small Transversals of Hypergraphs
Abstract
The main result of this paper is that every 4-uniform hypergraph on $n$ vertices and $m$ edges has a transversal with no more than $(5n+4m)/21$ vertices. In the particular case $n=m$, the transversal has at most $3n/7$ vertices, and this bound is sharp in the complement of the Fano plane. Chvátal and McDiarmid~\cite{CM} proved that every 3-uniform hypergraph with $n$ vertices and edges has a transversal of size $n/2$. Two direct corollaries of these results are that every graph with minimal degree at least 3 has total domination number at most $n/2$ and every graph with minimal degree at least 4 has total domination number at most $3n/7$. These two bounds are sharp.
Domains
Discrete Mathematics [cs.DM]
Loading...