{
  "id": "2308.01685",
  "version": "v1",
  "published": "2023-08-03T10:53:30.000Z",
  "updated": "2023-08-03T10:53:30.000Z",
  "title": "Inequalities Connecting the Annihilation and Independence Numbers",
  "authors": [
    "Ohr Kadrawi",
    "Vadim E. Levit"
  ],
  "comment": "17 pages, 10 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Given a graph $G$, the number of its vertices is represented by $n(G)$, while the number of its edges is denoted as $m(G)$. An independent set in a graph is a set of vertices where no two vertices are adjacent to each other and the size of the maximum independent set is denoted by $\\alpha(G)$. A matching in a graph refers to a set of edges where no two edges share a common vertex and the maximum matching size is denoted by $\\mu(G)$. If $\\alpha(G) + \\mu(G) = n(G)$, then the graph $G$ is called a K\\\"{o}nig-Egerv\\'{a}ry graph. Considering a graph $G$ with a degree sequence $d_1 \\leq d_2 \\leq \\cdots \\leq d_n$, the annihilation number $a(G)$ is defined as the largest integer $k$ such that the sum of the first $k$ degrees in the sequence is less than or equal to $m(G)$ (Pepper, 2004). It is a known fact that $\\alpha(G)$ is less than or equal to $a(G)$ for any graph $G$. Our goal is to estimate the difference between these two parameters. Specifically, we prove a series of inequalities, including $a(G) - \\alpha(G) \\leq \\frac{\\mu(G) - 1}{2}$ for trees, $a(G) - \\alpha(G) \\leq 2 + \\mu(G) - 2\\sqrt{1 + \\mu(G)}$ for bipartite graphs and $a(G) - \\alpha(G) \\leq \\mu(G) - 2$ for K\\\"{o}nig-Egerv\\'{a}ry graphs. Furthermore, we demonstrate that these inequalities serve as tight upper bounds for the difference between the annihilation and independence numbers, regardless of the assigned value for $\\mu(G)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-03T10:53:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C07",
      "05C05",
      "G.2.2"
    ],
    "keywords": [
      "independence numbers",
      "inequalities connecting",
      "tight upper bounds",
      "maximum independent set",
      "graph refers"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}