Journal article
A note on the Caro-Tuza bound on the independence number of uniform hypergraphs
AUSTRALASIAN JOURNAL OF COMBINATORICS, Vol.52, pp.235-242
01 Feb 2012
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We show some consequences of Caro and Tuza's [J. Graph Theory 15 (1991), 99-107] lower bound on the independence number of a K-uniform hypergraph H. This bound has the form C-K center dot Sigma(n)(i)(=1) (d(i) + 1)(-1/(K-1)), where C-K is a constant depending only on K, and d(1),...,d(n) are the degrees of the vertices in H. We improve on the best known bounds for C-K: in particular, we prove that C-3 >= root pi/2 and that C-K >= exp(-gamma/(K - 1)) for K >= 3, where gamma is the Euler-Mascheroni constant.
Metrics
3 Record Views
Details
- Title
- A note on the Caro-Tuza bound on the independence number of uniform hypergraphs
- Creators
- Bela Csaba - Western Kentucky Univ, Dept Math, 1906 Coll Hts Blvd, Bowling Green, KY 42101 USAThomas A. Plick - Drexel Univ, Dept Comp Sci, 3141 Chestnut St, Philadelphia, PA 19104 USAAli Shokoufandeh - Drexel Univ, Dept Comp Sci, 3141 Chestnut St, Philadelphia, PA 19104 USA
- Publication Details
- AUSTRALASIAN JOURNAL OF COMBINATORICS, Vol.52, pp.235-242
- Publisher
- Centre Discrete Mathematics & Computing
- Number of pages
- 8
- Grant note
- 0803670; ONRN000140410363 / United States NSF under the IIS Division and United States Office of Naval Research K76099 / Hungarian Scientific Research Fund (OTKA); Orszagos Tudomanyos Kutatasi Alapprogramok (OTKA) B15 2TT / School of Mathematics, University of Birmingham, U.K
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991019170145304721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics