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.
Type de document :
Article dans une revue
Combinatorica, Springer Verlag, 2007, 27, pp.473-487
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250084
Contributeur : Stephan Thomasse <>
Soumis le : samedi 9 février 2008 - 16:19:20
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 17 mai 2010 - 20:02:51

Fichier

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

171

Téléchargements de fichiers

971