{
  "id": "1111.3252",
  "version": "v1",
  "published": "2011-11-14T15:46:38.000Z",
  "updated": "2011-11-14T15:46:38.000Z",
  "title": "Hypergraphs for computing determining sets of Kneser graphs",
  "authors": [
    "J. Cáceres",
    "D. Garijo",
    "A. González",
    "A. Márquez",
    "M. L. Puertas"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A set of vertices $S$ is a \\emph{determining set} of a graph $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The \\emph{determining number} of $G$ is the minimum cardinality of a determining set of $G$. This paper studies determining sets of Kneser graphs from a hypergraph perspective. This new technique lets us compute the determining number of a wide range of Kneser graphs, concretely $K_{n:k}$ with $n\\geq \\frac{k(k+1)}{2}+1$. We also show its usefulness by giving shorter proofs of the characterization of all Kneser graphs with fixed determining number 2, 3 or 4, going even further to fixed determining number 5. We finally establish for which Kneser graphs $K_{n:k}$ the determining number is equal to $n-k$, answering a question posed by Boutin.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-11-14T15:46:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "kneser graphs",
      "computing determining sets",
      "hypergraph",
      "fixed determining number",
      "paper studies determining sets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1111.3252C"
    }
  }
}