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

DOI10.1016/J.AAM.2023.102668arXiv2210.03864OpenAlexW4391067188MaRDI QIDQ6153616FDOQ6153616

Authors:

Publication date: 14 February 2024

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: 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 bipartite graphs, independently chosen from $mathcalG(K_{n,n},p)$, and we obtain a tight bound, up to a factor of $n^{o(1)}$, for the threshold probability at which such graphs attain maximal connectivity. This resolves a conjecture of Alon, Defant, and Kravitz up to lower-order terms. 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.

Full work available at URL: https://arxiv.org/abs/2210.03864

Recommendations

• Connectivity of friends-and-strangers graphs on random pairs
• Typical and extremal aspects of friends-and-strangers graphs
• Friends and strangers walking on graphs
• Connectedness of friends-and-strangers graphs of complete bipartite graphs and others
• On the asymmetric generalizations of two extremal questions on friends-and-strangers graphs

zbMATH Keywords

connectivityrandom graphsfriends-and-strangers graphspebble motion

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Connectivity (05C40) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Packing random graphs and hypergraphs
• Graph puzzles, homotopy, and the alternating group
• Acyclic orientations of random graphs
• Toric partial orders
• On the asymmetric generalizations of two extremal questions on friends-and-strangers graphs
• An equivalence relation on the symmetric group and multiplicity-free flag \(h\)-vectors
• Friends and strangers walking on graphs
• Reversible computation using swap reactions on a surface

Cited In (1)

• On the diameters of friends-and-strangers graphs

This page was built for publication: Connectivity of old and new models of friends-and-strangers graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153616)