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

Abstract

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 two bijections $\sigma$ and ${\sigma }^{\prime }$ are adjacent if and only if they agree on all but two adjacent vertices $a,b\in V(X)$ such that $\sigma (a),\sigma (b)\in V(Y)$ are adjacent in $Y$. Resolving a conjecture of Wang, Lu, and Chen, we completely characterize the connectedness of $\mathsf{FS}(X,Y)$ when $Y$ is a complete bipartite graph. We further extend this result to when $Y$ is a complete multipartite graph. We also determine when $\mathsf{FS}(X,Y)$ has exactly two connected components where $X$ is bipartite and $Y$ is a complete bipartite graph.

22 pages, 23 figures