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

Abstract

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 $\sigma :V(X)\mapsto V(Y)$, in which two bijections $\sigma$, ${\sigma }^{\prime }$ are adjacent if and only if they differ precisely on two adjacent vertices of $X$, and the corresponding mappings 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 ${\mathsf{Lollipop}}_{n-k,k}$ be a lollipop graph of order $n$ obtained by identifying one end of a path of order $n-k+1$ with a vertex of a complete graph of order $k$. Defant and Kravitz started to study the connectedness of $\mathsf{FS}({\mathsf{Lollipop}}_{n-k,k},Y)$. In this paper, we give a sufficient and necessary condition for $\mathsf{FS}({\mathsf{Lollipop}}_{n-k,k},Y)$ to be connected for all $2\le k\le n$.