Article in volume
Authors:
Title:
Connectedness and cycle spaces of friends-and-strangers graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 1143-1168
Received: 2022-10-15 , Revised: 2023-02-11 , Accepted: 2023-02-17 , Available online: 2023-04-04 , https://doi.org/10.7151/dmgt.2492
Abstract:
If $X=(V(X),E(X))$ and $Y=(V(Y),E(Y))$ are $n$-vertex graphs, then their
friends-and-strangers graph $\mathsf{FS}(X,Y)$ is the graph whose
vertices are the bijections from $V(X)$ to $V(Y)$ in which two bijections
$\sigma$ and $\sigma'$ are adjacent if and only if there is an edge
$\{a,b\}\in E(X)$ such that $\{\sigma(a),\sigma(b)\}\in E(Y)$ and
$\sigma'=\sigma\circ (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 $\mathsf{FS}(X,Y)$ to be connected. As a corollary,
we obtain a complete characterization of the graphs $Y$ such that
$\mathsf{FS}(\mathsf{Dand}_{k,n},Y)$ is connected, where $\mathsf{Dand}_{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 $\mathsf{FS}(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
$\mathsf{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 $\mathsf{FS}(X,Y)$ behave under certain
Coxeter moves.
Keywords:
friends-and-strangers graph, spider, dandelion, cycle space, Coxeter move
References:
- 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 - A. Balitskiy and J. Wellman, Flip cycles in plabic graphs, Selecta Math. 26 (2020) 15.
https://doi.org/10.1007/s00029-020-0544-1 - 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 - C. Defant, Toric promotion, Proc. Amer. Math. Soc. 151 (2023) 45–57.
https://doi.org/10.1090/proc/16079 - C. Defant and N. Kravitz, Friends and strangers walking on graphs, Comb. Theory 1 (2021).
https://doi.org/10.5070/C61055363 - 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 - R. Jeong, Diameters of connected components of friends-and-strangers graphs are not polynomially bounded (2022).
arXiv: 2201.00665 - R. Jeong, On structural aspects of friends-and-strangers graphs (2022).
arXiv: 2203.10337 - M. Naatz, The graph of linear extensions revisited, SIAM J. Discrete Math. 13 (2000) 354–369.
https://doi.org/10.1137/S0895480199352609 - 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 - 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 - 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
Close