{
  "id": "1811.04722",
  "version": "v1",
  "published": "2018-11-12T13:40:45.000Z",
  "updated": "2018-11-12T13:40:45.000Z",
  "title": "On an Annihilation Number Conjecture",
  "authors": [
    "Vadim E. Levit",
    "Eugen Mandrescu"
  ],
  "comment": "17 pages, 11 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $\\alpha(G)$ denote the cardinality of a maximum independent set, while $\\mu(G)$ be the size of a maximum matching in the graph $G=\\left(V,E\\right) $. If $\\alpha(G)+\\mu(G)=\\left\\vert V\\right\\vert $, then $G$ is a K\\\"onig-Egerv\\'ary graph. If $d_{1}\\leq d_{2}\\leq\\cdots\\leq d_{n}$ is the degree sequence of $G$, then the annihilation number $h\\left(G\\right) $ of $G$ is the largest integer $k$ such that $\\sum\\limits_{i=1}^{k}d_{i}\\leq\\left\\vert E\\right\\vert $ (Pepper 2004, Pepper 2009). A set $A\\subseteq V$ satisfying $\\sum \\limits_{a\\in A} deg(a)\\leq\\left\\vert E\\right\\vert $ is an annihilation set, if, in addition, $ deg\\left(v\\right) +\\sum\\limits_{a\\in A} deg(a)>\\left\\vert E\\right\\vert $, for every vertex $v\\in V(G)-A$, then $A$ is a maximal annihilation set in $G$. In (Larson & Pepper 2011) it was conjectured that the following assertions are equivalent: (i) $\\alpha\\left(G\\right) =h\\left(G\\right) $; (ii) $G$ is a K\\\"onig-Egerv\\'ary graph and every maximum independent set is a maximal annihilating set. In this paper, we prove that the implication \"(i) $\\Longrightarrow$ (ii)\" is correct, while for the opposite direction we provide a series of generic counterexamples. Keywords: maximum independent set, matching, tree, bipartite graph, K\\\"onig-Egerv\\'ary graph, annihilation set, annihilation number.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-11-12T13:40:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C05",
      "05C70",
      "G.2.2"
    ],
    "keywords": [
      "annihilation number conjecture",
      "maximum independent set",
      "maximal annihilation set",
      "degree sequence",
      "generic counterexamples"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}