{
  "id": "1912.00060",
  "version": "v1",
  "published": "2019-11-29T20:10:58.000Z",
  "updated": "2019-11-29T20:10:58.000Z",
  "title": "Uniformly vertex-transitive graphs",
  "authors": [
    "Simon Schmidt",
    "Chase Vogeli",
    "Moritz Weber"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We introduce uniformly vertex-transitive graphs as vertex-transitive graphs satisfying a stronger condition on their automorphism groups, motivated by a problem which arises from a Sinkhorn-type algorithm. We use the derangement graph $D(\\Gamma)$ of a given graph $\\Gamma$ to show that the uniform vertex-transitivity of $\\Gamma$ is equivalent to the existence of cliques of sufficient size in $D(\\Gamma)$. Using this method, we find examples of graphs that are vertex-transitive but not uniformly vertex-transitive, settling a previously open question. Furthermore, we develop sufficient criteria for uniform vertex-transitivity in the situation of a graph with an imprimitive automorphism group. We classify the non-Cayley uniformly vertex-transitive graphs on less than 30 vertices outside of two complementary pairs of graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-29T20:10:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20B25",
      "05C99"
    ],
    "keywords": [
      "uniform vertex-transitivity",
      "complementary pairs",
      "stronger condition",
      "sinkhorn-type algorithm",
      "open question"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}