Metraipolis › archive › dc_12a50bc87a8a
Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree — arXiv:2610.20648
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.20648
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:33:14.230Z
- SHA-256 of the archived text
b0375d58bfdebe9a1d6dc3f72c43295379077382ea5afde27607aaec8ff9f803- Stable URL of this page
https://metraipolis.com/documento/dc_12a50bc87a8a
How to cite
Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree — arXiv:2610.20648 — arXiv (en), https://arxiv.org/abs/2610.20648 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_12a50bc87a8a (Metraipolis archive dc_12a50bc87a8a, sha256 b0375d58bfdebe9a1d6dc3f72c43295379077382ea5afde27607aaec8ff9f803)
BibTeX
@misc{dc12a50bc87a8a,
title = {Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree — arXiv:2610.20648},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.20648},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_12a50bc87a8a; sha256 b0375d58bfdebe9a1d6dc3f72c43295379077382ea5afde27607aaec8ff9f803},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20648. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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'$ 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)$.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.20648 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:50:47.561Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).