{
  "id": "2312.15519",
  "version": "v1",
  "published": "2023-12-24T16:04:11.000Z",
  "updated": "2023-12-24T16:04:11.000Z",
  "title": "Quasi-kernels in split graphs",
  "authors": [
    "Hélène Langlois",
    "Frédéric Meunier",
    "Romeo Rizzi",
    "Stéphane Vialette"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In a digraph, a quasi-kernel is a subset of vertices that is independent and such that the shortest path from every vertex to this subset is of length at most two. The \"small quasi-kernel conjecture,\" proposed by Erd\\H{o}s and Sz\\'ekely in 1976, postulates that every sink-free digraph has a quasi-kernel whose size is within a fraction of the total number of vertices. The conjecture is even more precise with a $1/2$ ratio, but even with larger ratio, this property is known to hold only for few classes of graphs. The focus here is on small quasi-kernels in split graphs. This family of graphs has played a special role in the study of the conjecture since it was used to disprove a strengthening that postulated the existence of two disjoint quasi-kernels. The paper proves that every sink-free split digraph $D$ has a quasi-kernel of size at most $\\frac{3}{4}|V(D)|$, and even of size at most two when the graph is an orientation of a complete split graph. It is also shown that computing a quasi-kernel of minimal size in a split digraph is W[2]-hard.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-24T16:04:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "G.2.2"
    ],
    "keywords": [
      "small quasi-kernel conjecture",
      "complete split graph",
      "sink-free split digraph",
      "larger ratio",
      "special role"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}