{
  "id": "2108.07984",
  "version": "v1",
  "published": "2021-08-18T05:57:59.000Z",
  "updated": "2021-08-18T05:57:59.000Z",
  "title": "Bounding the edge cover of a hypergraph",
  "authors": [
    "Farhad Shahrokhi"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-18T05:57:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hypergraph",
      "smallest edge cover",
      "largest independent set",
      "set cover",
      "mighty degeneracy"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}