Total Domination of Graphs and Small Transversals of Hypergraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Combinatorica Year : 2007

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.
Fichier principal
Vignette du fichier
strondom.pdf (184.54 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00250084 , version 1 (09-02-2008)

Identifiers

Cite

Stéphan Thomassé, Anders Yeo. Total Domination of Graphs and Small Transversals of Hypergraphs. Combinatorica, 2007, 27, pp.473-487. ⟨10.1007/s00493-007-2020-3⟩. ⟨lirmm-00250084⟩
163 View
1178 Download

Altmetric

Share

More