{
  "id": "2307.04112",
  "version": "v1",
  "published": "2023-07-09T07:45:02.000Z",
  "updated": "2023-07-09T07:45:02.000Z",
  "title": "On the Small Quasi-kernel conjecture",
  "authors": [
    "Péter L. Erdős",
    "Ervin Győri",
    "Tamás Róbert Mezei",
    "Nika Salia",
    "Mykhaylo Tyomkyn"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The Chv\\'atal-Lov\\'asz theorem from 1974 establishes in every finite digraph $G$ the existence of a quasi-kernel, i.e., an independent $2$-out-dominating vertex set. In the same spirit, the Small Quasi-kernel Conjecture, proposed by Erd\\H{o}s and Sz\\'ekely in 1976, asserts the existence of a quasi-kernel of order at most $|V(G)|/2$ if $G$ does not have sources. Despite repeated efforts, the conjecture remains wide open. This work contains a number of new results towards the conjecture. In our main contribution we resolve the conjecture for all directed graphs without sources containing a kernel in the second out-neighborhood of a quasi-kernel. Furthermore, we provide a novel strongly connected example demonstrating the asymptotic sharpness of the conjecture. Additionally, we resolve the conjecture in a strong form for all directed unicyclic graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-07-09T07:45:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C69"
    ],
    "keywords": [
      "small quasi-kernel conjecture",
      "strongly connected example demonstrating",
      "conjecture remains wide open",
      "directed unicyclic graphs",
      "out-dominating vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}