The connectivity of friends-and-strangers graphs on complete multipartite graphs

Honglin Zhu

For simple graphs $X$ and $Y$ on $n$ vertices, the friends-and-strangers graph $\mathsf{FS}(X,Y)$ is the graph whose vertex set consists of all bijections $\sigma :V(X)\to V(Y)$, where…