{
  "id": "2212.12764",
  "version": "v1",
  "published": "2022-12-24T16:19:36.000Z",
  "updated": "2022-12-24T16:19:36.000Z",
  "title": "A Result on the Small Quasi-Kernel Conjecture",
  "authors": [
    "Allan van Hulst"
  ],
  "comment": "9 pages, a link to the Coq code is mentioned in the paper, submitted to Electronic Journal of Combinatorics",
  "categories": [
    "math.CO"
  ],
  "abstract": "Any directed graph $D=(V(D),A(D))$ in this work is assumed to be finite and without self-loops. A source in a directed graph is a vertex having at least one ingoing arc. A quasi-kernel $Q\\subseteq V(D)$ is an independent set in $D$ such that every vertex in $V(D)$ can be reached in at most two steps from a vertex in $Q$. It is an open problem whether every source-free directed graph has a quasi-kernel of size at most $|V(D)|/2$, a problem known as the small quasi-kernel conjecture (SQKC). The aim of this paper is to prove the SQKC under the assumption of a structural property of directed graphs. This relates the SQKC to the existence of a vertex $u\\in V(D)$ and a bound on the number of new sources emerging when $u$ and its out-neighborhood are removed from $D$. The results in this work are of technical nature and therefore additionally verified by means of the Coq proof-assistant.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-24T16:19:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C69"
    ],
    "keywords": [
      "small quasi-kernel conjecture",
      "structural property",
      "open problem",
      "source-free directed graph",
      "independent set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}