On Structural Aspects of Friends-And-Strangers Graphs

MaRDI QIDQ6394128zbMATH OpenFDO

Authors Ryan Jeong

Publication date 19 March 2022

Abstract: Given two graphs $X$ and $Y$ with the same number of vertices, the friends-and-strangers graph $mathsfFS(X,Y)$ has as its vertices all $n!$ bijections from $V(X)$ to $V(Y)$, with bijections $sigma,au$ adjacent if and only if they differ on two elements of $V(X)$, whose mappings are adjacent in $Y$. In this article, we study necessary and sufficient conditions for $mathsfFS(X,Y)$ to be connected for all graphs $X$ from some set. In the setting that we take $X$ to be drawn from the set of all biconnected graphs, we prove that $mathsfFS(X,Y)$ is connected for all biconnected $X$ if and only if $overlineY$ is a forest with trees of jointly coprime size; this resolves a conjecture of Defant and Kravitz. We also initiate and make significant progress toward determining the girth of $mathsfFS(X,ext{Star}_n)$ for connected graphs $X$, and in particular focus on the necessary trajectories that the central vertex of $ext{Star}_n$ takes around all such graphs $X$ to achieve the girth.

This page was built for publication: On Structural Aspects of Friends-And-Strangers Graphs

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