The Connectedness of the Friends-and-Strangers Graph of a Lollipop and Others.

Let X and Y be any two graphs of order n. The friends-and-strangers graph FS (X , Y) of X and Y is a graph with vertex set consisting of all bijections σ : V (X) → V (Y) , in which two bijections σ , σ ′ 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 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 FS (Lollipop n - k , k , Y) . In this paper, we give a sufficient and necessary condition for FS (Lollipop n - k , k , Y) to be connected for all 2 ≤ k ≤ n , which interpolates between two previous results on paths and complete graphs. [ABSTRACT FROM AUTHOR]