Premium
A lower bound on the independence number of arbitrary hypergraphs
Author(s) -
Thiele Torsten
Publication year - 1999
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/(sici)1097-0118(199903)30:3<213::aid-jgt6>3.0.co;2-q
Subject(s) - hypergraph , combinatorics , independence number , mathematics , upper and lower bounds , vertex (graph theory) , degree (music) , discrete mathematics , graph , function (biology) , independence (probability theory) , mathematical analysis , statistics , physics , evolutionary biology , acoustics , biology
We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d ( v ) = ( d 1 ( v ), d 2 ( v ), …) where d m ( v ) is the number of edges of size m containing v . We define a function f with the property that any hypergraph H = ( V , E ) satisfies α( H ) ≥ Σ v ∈ V f ( d ( v )). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 213–221, 1999