Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree

@misc{mawhinney2026connectivity,
  title = {{Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree}},
  author = {Kai Mawhinney},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20648},
  eprint = {2610.20648},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20648},
}

TY  - UNPB
TI  - Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree
AU  - Kai Mawhinney
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.20648
UR  - https://arxiv.org/abs/2610.20648
AB  - Given graphs X,Y on n vertices, Defant and Kravitz defined the friends and strangers graph, denoted FS(X,Y). The vertices of FS(X,Y) are bijections σ:V(X)→ V(Y), and two bijections σ and σ' are adjacent in FS(X,Y) if they differ by a transposition (ab) such that a and b are adjacent in X and σ(a) and σ(b) are adjacent in Y. Our main result resolves a conjecture of Bangachev that if X,Y are connected graphs and 2min{δ(X),δ(Y)}+3max{δ(X),δ(Y)}≥ 3n, then 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∈ V(X) and any vertex σ∈ V(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 FS(X,Y) is O(n^2/min{δ(X),δ(Y)}), and that this is sharp as a bound on the maximum diameter of 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 FS(X,Y) is O(n^2).
ER  -