Bounding the edge cover of a hypergraph

Abstract

Let $H=(V,E)$ be a hypergraph. Let $C\subseteq E$, then $C$ is an {\it edge cover}, or a {\it set cover}, if ${\cup }_{e\in C}\{v|v\in 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 $\alpha (H)$ denote the cardinalities of a smallest edge cover and largest independent set in $H$, respectively. We show that $c(H)\le \hat{m}(h)c(H)$, where $\hat{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.

This is a revised version of the paper [Bounding the edge cover of a hypergraph] recently posted on arXiv