Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 24 min ago
PreprintarXiv licencearXiv

The Connectivity Threshold for Friends and Strangers graphs

  • Bruno Baldissera
  • Gabriel Dias do Couto
  • Simon Griffiths
  • Luiz Moreira
Open at sourcePDFDOICite

Abstract

The concept of the Friends and Strangers graph FS(G,H) associated with two graphs G and H was recently introduced by Defant and Kravitz and has generated significant interest. In a companion article, joint with Alon, they consider the behaviour of FS(G,H) in the case where G and H are Erdős-Rényi random graphs, and prove that the threshold for connectivity is of the form n−1/2+o(1). In this paper we prove that the threshold is n−1/2√(logn), up to a multiplicative constant, answering a question from Alon, Defant and Kravitz.

Related

  1. Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree
    Kai Mawhinney
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The Exact Degree Threshold for Complement Connectivity
    Arsen Berk Tekdaş
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
    Jia Wei, Muhuo Liu, Zhifu You +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Independence number, essential connectivity and the distance spectral radius of graphs
    Shuang Ding, Dan Li, Yuanyuan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A linear bound for a connectivity partition in graphs
    Jia Zhou, Jin Yan, Yunshu Gao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{baldissera2026connectivity,
  title = {{The Connectivity Threshold for Friends and Strangers graphs}},
  author = {Bruno Baldissera and Gabriel Dias do Couto and Simon Griffiths and Luiz Moreira},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05254},
  eprint = {2611.05254},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05254},
}
RIS
TY  - UNPB
TI  - The Connectivity Threshold for Friends and Strangers graphs
AU  - Bruno Baldissera
AU  - Gabriel Dias do Couto
AU  - Simon Griffiths
AU  - Luiz Moreira
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05254
UR  - https://arxiv.org/abs/2611.05254
AB  - The concept of the Friends and Strangers graph FS(G,H) associated with two graphs G and H was recently introduced by Defant and Kravitz and has generated significant interest. In a companion article, joint with Alon, they consider the behaviour of FS(G,H) in the case where G and H are Erdős-Rényi random graphs, and prove that the threshold for connectivity is of the form n^−1/2+o(1). In this paper we prove that the threshold is n^−1/2√(logn), up to a multiplicative constant, answering a question from Alon, Defant and Kravitz.
ER  -