The connectedness of the friends-and-strangers graph of lollipop graphs and others

Lanchao Wang, Yaojun Chen

Let $X$ and $Y$ be any two graphs of order $n$. The friends-and-strangers graph $\mathsf{FS}(X,Y)$ of $X$ and $Y$ is a graph with vertex set consisting of all bijections $σ:V(X) \m…