Bounding the edge cover of a hypergraph

arXiv2108.07984MaRDI QIDQ6375484FDOQ6375484

Farhad Shahrokhi

Publication date: 18 August 2021

Abstract: Let $H=(V,E)$ be a hypergraph. Let $CsubseteqE$, then $C$ is an {it edge cover}, or a {it set cover}, if $cu{p}_{einC}v|vine=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)lehatm(h)c(H)$, where $hatm(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 page was built for publication: Bounding the edge cover of a hypergraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6375484)