Total domination of graphs and small transversals of hypergraphs |
| |
Authors: | Stéphan Thomassé Anders Yeo |
| |
Institution: | (1) LIRMM, 161, rue Ada, 34392 Montpellier Cedex 5, France;(2) Department of Computer Science Royal Holloway, University of London, Egham Surrey, TW20 0EX, UK |
| |
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 5] 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. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 05C65 05C69 |
本文献已被 SpringerLink 等数据库收录! |
|