{
  "id": "2210.04768",
  "version": "v2",
  "published": "2022-10-05T06:43:43.000Z",
  "updated": "2022-11-22T08:41:48.000Z",
  "title": "Connectedness in Friends-and-Strangers Graphs of Spiders and Complements",
  "authors": [
    "Alan Lee"
  ],
  "comment": "9 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $X$ and $Y$ be two graphs with vertex set $[n]$. Their friends-and-strangers graph $\\mathsf{FS}(X,Y)$ is a graph with vertices corresponding to elements of the group $S_n$, and two permutations $\\sigma$ and $\\sigma'$ are adjacent if they are separated by a transposition $\\{a,b\\}$ such that $a$ and $b$ are adjacent in $X$ and $\\sigma(a)$ and $\\sigma(b)$ are adjacent in $Y$. Specific friends-and-strangers graphs such as $\\mathsf{FS}(\\mathsf{Path}_n,Y)$ and $\\mathsf{FS}(\\mathsf{Cycle}_n,Y)$ have been researched, and their connected components have been enumerated using various equivalence relations such as double-flip equivalence. A spider graph is a collection of path graphs that are all connected to a single center point. In this paper, we delve deeper into the question of when $\\mathsf{FS}(X,Y)$ is connected when $X$ is a spider and $Y$ is the complement of a spider or a tadpole.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-11-22T08:41:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C40"
    ],
    "keywords": [
      "complement",
      "connectedness",
      "specific friends-and-strangers graphs",
      "single center point",
      "path graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}