Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree

Abstract

Given graphs $X,Y$ on $n$ vertices, Defant and Kravitz defined the friends and strangers graph, denoted $\mathrm{FS}(X,Y)$. The vertices of $\mathrm{FS}(X,Y)$ are bijections $\sigma :V(X)\to V(Y)$, and two bijections $\sigma$ and ${\sigma }^{\prime }$ are adjacent in $\mathrm{FS}(X,Y)$ if they differ by a transposition $(ab)$ such that $a$ and $b$ are adjacent in $X$ and $\sigma (a)$ and $\sigma (b)$ are adjacent in $Y$. Our main result resolves a conjecture of Bangachev that if $X,Y$ are connected graphs and $2\min \{\delta (X),\delta (Y)\}+3\max \{\delta (X),\delta (Y)\}\ge 3n$, then $\mathrm{FS}(X,Y)$ is connected. The main step in the proof is showing that there exists an absolute constant $C$ such that for any adjacent vertices $a,b\in V(X)$ and any vertex $\sigma \in V(\mathrm{FS}(X,Y))$, $a$ and $b$ can swap positions in at most $C$ moves. Furthermore, we prove that if $X,Y$ are connected graphs satisfying the above minimum degree condition, then the diameter of $\mathrm{FS}(X,Y)$ is $O(n^2/\min \{\delta (X),\delta (Y)\})$, and that this is sharp as a bound on the maximum diameter of $\mathrm{FS}(X,Y)$ in this regime. This work improves the diameter results of Akella and Li, and resolves many of their questions. Moreover, we show that even for disconnected graphs $X$ and $Y$, the same minimum degree condition implies that the diameter of any connected component of $\mathrm{FS}(X,Y)$ is $O(n^2)$.

arXiv comment54 pages, 36 figures