Connectedness and Cycle Spaces of Friends-and-Strangers Graphs

MaRDI QIDQ6409716zbMATH OpenFDO

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

Publication date 4 September 2022

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: If $X=(V(X),E(X))$ and $Y=(V(Y),E(Y))$ are $n$-vertex graphs, then their friends-and-strangers graph $mathsfFS(X,Y)$ is the graph whose vertices are the bijections from $V(X)$ to $V(Y)$ in which two bijections $sigma$ and $sigm{a}^{\prime }$ are adjacent if and only if there is an edge $a,binE(X)$ such that $sigma(a),sigma(b)inE(Y)$ and $sigm{a}^{\prime }=sigmacirc(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 $mathsfFS(X,Y)$ to be connected. As a corollary, we obtain a complete characterization of the graphs $Y$ such that $mathsfFS(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 $mathsfFS(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 $mathsfFS(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 $mathsfFS(X,Y)$ behave under certain Coxeter moves.

This page was built for publication: Connectedness and Cycle Spaces of Friends-and-Strangers Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409716)