- Tytuł:
- Connectedness and cycle spaces of friends-and-strangers graphs
- Autorzy:
-
Defant, Colin
Dong, David
Lee, Alan
Wei, Michelle - Tematy:
-
friends-and-strangers graph
spider
dandelion
cycle space
Coxeter move - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/59898621.pdf Link otwiera się w nowym oknie
- Opis:
- 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł