On the Treewidth of Token and Johnson Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910913697677312 |
|---|---|
| author | Fabila-Monroy, Ruy Gómez-Galicia, Sergio Gerardo Hernández-Cruz, César Trujillo-Negrete, Ana Laura |
| author_facet | Fabila-Monroy, Ruy Gómez-Galicia, Sergio Gerardo Hernández-Cruz, César Trujillo-Negrete, Ana Laura |
| contents | Let $G$ be a graph on $n$ vertices and $1 \le k \le n$ a fixed integer. The \textit{$k$-token graph} of $G$ is the graph $F_k(G)$ whose vertex set consists of all $k$-subsets of the vertex set of $G$, where two vertices $A$ and $B$ are adjacent in $F_k(G)$ whenever their symmetric difference $A\triangle B$ is an edge of $G$. In this paper we study the treewidth of $F_k(G)$ when $G$ is a star, path, or a complete graph. We show that in the first two cases, the treewidth is of order $Θ(n^{k-1})$, and of order $Θ(n^k)$ in the third case. We conjecture that our upper bound for the treewidth of $F_k(K_n)$ is tight. This is particularly relevant since $F_k(K_n)$ is isomorphic to the well known Johnson graph $J(n,k)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_17962 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Treewidth of Token and Johnson Graphs Fabila-Monroy, Ruy Gómez-Galicia, Sergio Gerardo Hernández-Cruz, César Trujillo-Negrete, Ana Laura Combinatorics 05C05, 05C75, 05C76 Let $G$ be a graph on $n$ vertices and $1 \le k \le n$ a fixed integer. The \textit{$k$-token graph} of $G$ is the graph $F_k(G)$ whose vertex set consists of all $k$-subsets of the vertex set of $G$, where two vertices $A$ and $B$ are adjacent in $F_k(G)$ whenever their symmetric difference $A\triangle B$ is an edge of $G$. In this paper we study the treewidth of $F_k(G)$ when $G$ is a star, path, or a complete graph. We show that in the first two cases, the treewidth is of order $Θ(n^{k-1})$, and of order $Θ(n^k)$ in the third case. We conjecture that our upper bound for the treewidth of $F_k(K_n)$ is tight. This is particularly relevant since $F_k(K_n)$ is isomorphic to the well known Johnson graph $J(n,k)$. |
| title | On the Treewidth of Token and Johnson Graphs |
| topic | Combinatorics 05C05, 05C75, 05C76 |
| url | https://arxiv.org/abs/2402.17962 |