2021/08/18 by Shahrokhi, Farhad
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.07984
Let H=(V,E) be a hypergraph. Let C⊆ E, then C is an \it edge cover, or a \it set cover, if ∪e∈ C \v|v∈ e\=V. A subset of vertices X is \it independent in H, if no two vertices in X are in any edge. Let c(H) and α(H) denote the cardinalities of a smallest edge cover and largest independent set in H, respectively. We show that c(H)≤ m(h)c(H), where m(H) is a parameter called the \it mighty degeneracy of H. Furthermore, we show that the inequality is tight and demonstrate the applications in domination theory.