{"id":"arxiv/2610.20648","url":"https://arxiv.org/abs/2610.20648","tags":["math.CO"],"score":0,"title":"Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree","domain":"math.CO","source":"arxiv","authors":["Kai Mawhinney"],"reviews":0,"subject":"math.CO","summary":"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 $σ:V(X)\\to V(Y)$, and two bijections $σ$ and $σ'$ are adjacent in $\\mathrm{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 $2\\min\\{δ(X),δ(Y)\\}+3\\max\\{δ(X),δ(Y)\\}\\ge 3n$, then $\\mathrm{FS}(X,Y)$ is connected. The main step in the proof is showing…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}