CONNECTEDNESS AND CYCLE SPACES OF FRIENDS-AND-STRANGERS...

If X = (V (X), E(X)) and Y = (V (Y), E(Y)) are n-vertex graphs, then their friends-and-strangers graph FS(X, Y) is the graph whose vertices are the bijections from V (X) to V (Y) in which two bijections σ and σ 0 are adjacent if and only if there is an edge {a, b} ∈ E(X) such that {σ(a), σ(b)} ∈ E(Y) and σ 0 = σ ' (a b), where (a b) is the permutation of V (X) that swaps a and b. We prove general theorems that provide necessary and/or sufficient conditions for FS(X, Y) to be connected. As a corollary, we obtain a complete characterization of the graphs Y such that FS(Dandk,n, Y) is connected, where Dandk,n is a dandelion graph; this substantially generalizes a theorem of the first author and Kravitz in the case k = 3. For specific choices of Y, we characterize the spider graphs X such that FS(X, Y) is connected. In a different vein, we study the cycle spaces of friends-andstrangers graphs. Naatz proved that if X is a path graph, then the cycle space of FS(X, Y) is spanned by 4-cycles and 6-cycles; we show that the same statement holds when X is a cycle and Y has domination number at least 3. When X is a cycle and Y has domination number at least 2, our proof sheds light on how walks in FS(X, Y) behave under certain Coxeter moves. [ABSTRACT FROM AUTHOR]