The connectedness of friends-and-strangers graphs about graph parameters and others
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916668490383360 |
|---|---|
| author | Zhao, Xinghui You, Lihua Lin, Jifu Zhang, Xiaoxue |
| author_facet | Zhao, Xinghui You, Lihua Lin, Jifu Zhang, Xiaoxue |
| contents | Let $X$ and $Y$ be two graphs of order $n$. The friends-and-strangers graph $\textup{FS}(X,Y)$ of $X$ and $Y$ is a graph whose vertex set consists of all bijections $σ: V(X)\rightarrow V(Y)$, in which two bijections $σ$ and $ σ'$ are adjacent if and only if they agree on all but two adjacent vertices of $X$ such that the corresponding images are adjacent in $Y$. The most fundamental question about these friends-and-strangers graphs is whether they are connected. In this paper, we provide a sufficient condition regarding the maximum degree $Δ(X)$ and vertex connectivity $κ(Y)$ that ensures the graph $\textup{FS}(X,Y)$ is $s$-connected. As a corollary, we improve upon a result by Bangachev and partially confirm a conjecture he proposed. Furthermore, we completely characterize the connectedness of $\textup{FS}(X,Y)$, where $X\in\textup{DL}_{n-k,k}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_00373 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The connectedness of friends-and-strangers graphs about graph parameters and others Zhao, Xinghui You, Lihua Lin, Jifu Zhang, Xiaoxue Combinatorics 05C40, 05C76 Let $X$ and $Y$ be two graphs of order $n$. The friends-and-strangers graph $\textup{FS}(X,Y)$ of $X$ and $Y$ is a graph whose vertex set consists of all bijections $σ: V(X)\rightarrow V(Y)$, in which two bijections $σ$ and $ σ'$ are adjacent if and only if they agree on all but two adjacent vertices of $X$ such that the corresponding images are adjacent in $Y$. The most fundamental question about these friends-and-strangers graphs is whether they are connected. In this paper, we provide a sufficient condition regarding the maximum degree $Δ(X)$ and vertex connectivity $κ(Y)$ that ensures the graph $\textup{FS}(X,Y)$ is $s$-connected. As a corollary, we improve upon a result by Bangachev and partially confirm a conjecture he proposed. Furthermore, we completely characterize the connectedness of $\textup{FS}(X,Y)$, where $X\in\textup{DL}_{n-k,k}$. |
| title | The connectedness of friends-and-strangers graphs about graph parameters and others |
| topic | Combinatorics 05C40, 05C76 |
| url | https://arxiv.org/abs/2504.00373 |