Premium
Hypergraphs with large transversal number and with edge sizes at least 3
Author(s) -
Henning Michael A.,
Yeo Anders
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20340
Subject(s) - hypergraph , combinatorics , mathematics , transversal (combinatorics) , graph , upper and lower bounds , discrete mathematics , order (exchange) , degree (music) , enhanced data rates for gsm evolution , computer science , physics , mathematical analysis , telecommunications , finance , acoustics , economics
It is shown in several manuscripts [Discrete Math 86 (1990), 117–126; Combinatorica 12 (1992), 19–26] that every hypergraph of order n and size m with edge sizes at least 3 has a transversal of size at most ( n + m )/4. In this article, we characterize the connected such hypergraphs that achieve equality in this bound. As a direct consequence of this bound, the total domination of a graph with minimum degree at least 3 is at most one‐half its order. An elegant graph theoretic proof of this result is presented in Archdeacon et al. [J Graph Theory 46 (2004), 207–210]. Using our hypergraph result, we characterize the connected graphs with minimum degree at least 3 and with total domination number exactly one‐half their order. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 326–348, 2008