Geodesic
Connectedness and cycle spaces of friends-and-strangers graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1143-1168 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: friends-and-strangers graph, spider, dandelion, cycle space, Coxeter move 
@article{DMGT_2024_44_3_a16,
     author = {Defant, Colin and Dong, David and Lee, Alan and Wei, Michelle},
     title = {Connectedness and cycle spaces of friends-and-strangers graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1143--1168},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a16/}
}
TY  - JOUR
AU  - Defant, Colin
AU  - Dong, David
AU  - Lee, Alan
AU  - Wei, Michelle
TI  - Connectedness and cycle spaces of friends-and-strangers graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1143
EP  - 1168
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a16/
LA  - en
ID  - DMGT_2024_44_3_a16
ER  - 
%0 Journal Article
%A Defant, Colin
%A Dong, David
%A Lee, Alan
%A Wei, Michelle
%T Connectedness and cycle spaces of friends-and-strangers graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1143-1168
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a16/
%G en
%F DMGT_2024_44_3_a16
Defant, Colin; Dong, David; Lee, Alan; Wei, Michelle. Connectedness and cycle spaces of friends-and-strangers graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1143-1168. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a16/

[1] N. Alon, C. Defant and N. Kravitz, Typical and extremal aspects of friends-and-strangers graphs, J. Combin. Theory Ser. B 158 (2023) 3–42. https://doi.org/10.1016/j.jctb.2022.03.001

[2] A. Balitskiy and J. Wellman, Flip cycles in plabic graphs, Selecta Math. 26 (2020) 15. https://doi.org/10.1007/s00029-020-0544-1

[3] K. Bangachev, On the asymmetric generalizations of two extremal questions on friends-and-strangers graphs, European J. Combin. 104 (2022) 103529. https://doi.org/10.1016/j.ejc.2022.103529

[4] C. Defant, Toric promotion, Proc. Amer. Math. Soc. 151 (2023) 45–57. https://doi.org/10.1090/proc/16079

[5] C. Defant and N. Kravitz, Friends and strangers walking on graphs, Comb. Theory 1 (2021). https://doi.org/10.5070/C61055363

[6] S. Felsner, L. Kleist, T. Mütze and L. Sering, Rainbow cycles in flip graphs, SIAM J. Discrete Math. 34 (2020) 1–39. https://doi.org/10.1137/18M1216456

[7] R. Jeong, Diameters of connected components of friends-and-strangers graphs are not polynomially bounded (2022). arXiv: 2201.00665

[8] R. Jeong, On structural aspects of friends-and-strangers graphs (2022). arXiv: 2203.10337

[9] M. Naatz, The graph of linear extensions revisited, SIAM J. Discrete Math. 13 (2000) 354–369. https://doi.org/10.1137/S0895480199352609

[10] R.P. Stanley, An equivalence relation on the symmetric group and multiplicity-free flag h -vectors, J. Comb. 3 (2012) 277–298. https://doi.org/10.4310/JOC.2012.v3.n3.a2

[11] L. Wang and Y. Chen, Connectivity of friends-and-strangers graphs on random pairs, Discrete Math. 346(3) (2023) 113266. https://doi.org/10.1016/j.disc.2022.113266

[12] R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combin. Theory Ser. B 16 (1974) 86–96. https://doi.org/10.1016/0095-8956(74)90098-7