{
  "id": "2108.10801",
  "version": "v1",
  "published": "2021-08-24T15:43:07.000Z",
  "updated": "2021-08-24T15:43:07.000Z",
  "title": "On the dissociation number of Kneser graphs",
  "authors": [
    "Boštjan Brešar",
    "Tanja Dravec"
  ],
  "comment": "9 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "A set $D$ of vertices of a graph $G$ is a dissociation set if each vertex of $D$ has at most one neighbor in $D$. The dissociation number of $G$, $diss(G)$, is the cardinality of a maximum dissociation set in a graph $G$. In this paper we study dissociation in the well-known class of Kneser graphs $K_{n,k}$. In particular, we establish that the dissociation number of Kneser graphs $K_{n,2}$ equals $\\max{\\{n-1,6\\}}$. We show that for any $k \\geq 2$, there exists $n_0 \\in \\mathbb{N}$ such that $diss(K_{n,k})=\\alpha(K_{n,k})$ for any $n \\geq n_0$. We consider the case $k=3$ in more details and prove that $n_0=8$ in this case. Then we improve a trivial upper bound $2\\alpha(K_{n,k})$ for the dissociation number of Kneser graphs $K_{n,k}$ by using Katona's cyclic arrangement of integers from $\\{1,\\ldots , n\\}$. Finally we investigate the odd graphs, that is, the Kneser graphs with $n=2k+1$. We prove that $diss(K_{2k+1,k})={2k \\choose k}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-24T15:43:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "kneser graphs",
      "dissociation number",
      "katonas cyclic arrangement",
      "maximum dissociation set",
      "trivial upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}