Skip to Main content Skip to Navigation
Journal articles

Total Domination of Graphs and Small Transversals of Hypergraphs

Stéphan Thomassé 1 Anders Yeo 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250084
Contributor : Stephan Thomasse <>
Submitted on : Saturday, February 9, 2008 - 4:19:20 PM
Last modification on : Thursday, February 7, 2019 - 5:14:27 PM
Long-term archiving on: : Monday, May 17, 2010 - 8:02:51 PM

Identifiers

  • HAL Id : lirmm-00250084, version 1

Collections

Citation

Stéphan Thomassé, Anders Yeo. Total Domination of Graphs and Small Transversals of Hypergraphs. Combinatorica, Springer Verlag, 2007, 27, pp.473-487. ⟨lirmm-00250084⟩

Share

Metrics

Record views

290

Files downloads

1748