Friends and strangers walking on graphs
Friends and strangers walking on graphs
Given graphs \(X\) and \(Y\) with vertex sets \(V(X)\) and \(V(Y)\) of the same cardinality, we define a graph \(\mathsf{FS}(X,Y)\) whose vertex set consists of all bijections \(\sigma\colon V(X)\to V(Y)\), where two bijections \(\sigma\) and \(\sigma'\) are adjacent if they agree everywhere except for two adjacent vertices \(a,b \in V(X)\) …