Connectedness and cycle spaces of friends-and-strangers graphs

Defant, Colin  ; Dong, David ; Lee, Alan ; Wei, Michelle

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1143-1168

Résumé

If X=(V(X),E(X)) and Y=(V(Y),E(Y)) are n-vertex graphs, then their friends-and-strangers graph 𝖥𝖲(X,Y) is the graph whose vertices are the bijections from V(X) to V(Y) in which two bijections σ and σ^' are adjacent if and only if there is an edge {a,b}∈ E(X) such that {σ(a),σ(b)}∈ E(Y) and σ^'=σ∘ (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 𝖥𝖲(X,Y) to be connected. As a corollary, we obtain a complete characterization of the graphs Y such that 𝖥𝖲(𝖣𝖺𝗇𝖽_k,n,Y) is connected, where 𝖣𝖺𝗇𝖽_k,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 𝖥𝖲(X,Y) is connected. In a different vein, we study the cycle spaces of friends-and-strangers graphs. Naatz proved that if X is a path graph, then the cycle space of 𝖥𝖲(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 𝖥𝖲(X,Y) behave under certain Coxeter moves.

Détail

Keywords: friends-and-strangers graph, spider, dandelion, cycle space, Coxeter move