Diameter Bounds for Friends-and-Strangers Graphs

Amogh Akella, Rupert Li

Consider two $n$-vertex graphs $X$ and $Y$, where we interpret $X$ as a social network with edges representing friendships and $Y$ as a movement graph with edges representing adjac…