Details

Autor(en) / Beteiligte

• Milojević, Aleksa

Titel

Connectivity of old and new models of friends-and-strangers graphs

Ist Teil von

• Advances in applied mathematics, 2024-04, Vol.155, p.102668, Article 102668

Ort / Verlag

Elsevier Inc

Erscheinungsjahr

2024

Link zum Volltext

Quelle

Elsevier ScienceDirect Journals Complete

Beschreibungen/Notizen

• In this paper, we investigate the connectivity of friends-and-strangers graphs, which were introduced by Defant and Kravitz in 2020. We begin by considering friends-and-strangers graphs arising from two random graphs and consider the threshold probability at which such graphs attain maximal connectivity. We slightly improve the lower bounds on the threshold probabilities, thus disproving two conjectures of Alon, Defant and Kravitz. We also improve the upper bound on the threshold probability in the case of random bipartite graphs, and obtain a tight bound up to a factor of no(1). Further, we introduce a generalization of the notion of friends-and-strangers graphs in which vertices of the starting graphs are allowed to have multiplicities and obtain generalizations of previous results of Wilson and of Defant and Kravitz in this new setting.