Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.20648
curl -X POST /api/v1/records/arxiv/2610.20648/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.20648/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'