The connectedness of friends-and-strangers graphs about graph parameters and others

Abstract

Let $X$ and $Y$ be two graphs of order $n$. The friends-and-strangers graph $\text{FS}(X,Y)$ of $X$ and $Y$ is a graph whose vertex set consists of all bijections $\sigma :V(X)\to V(Y)$, in which two bijections $\sigma$ and ${\sigma }^{\prime }$ are adjacent if and only if they agree on all but two adjacent vertices of $X$ such that the corresponding images are adjacent in $Y$. The most fundamental question about these friends-and-strangers graphs is whether they are connected. In this paper, we provide a sufficient condition regarding the maximum degree $\Delta (X)$ and vertex connectivity $\kappa (Y)$ that ensures the graph $\text{FS}(X,Y)$ is $s$-connected. As a corollary, we improve upon a result by Bangachev and partially confirm a conjecture he proposed. Furthermore, we completely characterize the connectedness of $\text{FS}(X,Y)$, where $X\in {\text{DL}}_{n-k,k}$.

24 pages, 1 figure