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

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 }^{\prime }$ 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.

9 pages, 2 figures