Connectedness in Friends-and-Strangers Graphs of Spiders and Complements

Alan Lee

Published 2022-10-05, updated 2022-11-22Version 2

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.