Connectedness of friends-and-strangers graphs of complete bipartite graphs and others

Let Xand Ybe any two graphs of order n. The friends-and-strangers graph FS( X, Y) of Xand Yis a graph with vertex set consisting of all bijections sigma: V( X) ->. V(Y), in which two bijections sigma, sigma' are adjacent if and only if they differ precisely on two adjacent vertices of X, and the corresponding images are adjacent in Y. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let K-k,K- n-k be a complete bipartite graph of order n. In 1974, Wilson characterized the connectedness of FS( K-1, (n-1), Y) by using algebraic methods. In this paper, by using combinatorial methods, we investigate the connectedness of FS( K-k,K- n-k, Y) for any Yand all k >= 2, including Ybeing a random graph, as suggested by Defant and Kravitz, and pose some open problems.