Generalized Token Graphs
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_ | 1866915474533515264 |
|---|---|
| author | Herrera-Ramirez, C. Amairani Hoekstra-Mendoza, Teresa I. |
| author_facet | Herrera-Ramirez, C. Amairani Hoekstra-Mendoza, Teresa I. |
| contents | In this paper we give a new generalization of token graphs. Given two integers $1\leq m \leq k$ and a graph $G$ we define the generalized token graph of the graph $G$, to be the graph $F_k^m(G)$ whose vertices correspond to configurations of $k$ indistinguishable tokens placed at distinct vertices of $G$, where two configurations are adjacent whenever one configuration can be reached from the other by moving $m$ tokens along $m$ edges of $G$. When $m=1$, the usual token graph $F_k(G)$ is recovered.
We give sufficient and necessary conditions on the graph $G$ for $F_2^2(G)$ to be connected and
we give sufficient and necessary conditions on the graph $G$ for $F_2^2(G)$ to be bipartite.
We also analyze some properties of generalized token graphs, such as clique number, chromatic number, independence number and domination number. Finally, we conclude with an analysis of the automorphism group of the generalized token graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01773 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generalized Token Graphs Herrera-Ramirez, C. Amairani Hoekstra-Mendoza, Teresa I. Combinatorics 05C76, 05C40, 05C15 In this paper we give a new generalization of token graphs. Given two integers $1\leq m \leq k$ and a graph $G$ we define the generalized token graph of the graph $G$, to be the graph $F_k^m(G)$ whose vertices correspond to configurations of $k$ indistinguishable tokens placed at distinct vertices of $G$, where two configurations are adjacent whenever one configuration can be reached from the other by moving $m$ tokens along $m$ edges of $G$. When $m=1$, the usual token graph $F_k(G)$ is recovered. We give sufficient and necessary conditions on the graph $G$ for $F_2^2(G)$ to be connected and we give sufficient and necessary conditions on the graph $G$ for $F_2^2(G)$ to be bipartite. We also analyze some properties of generalized token graphs, such as clique number, chromatic number, independence number and domination number. Finally, we conclude with an analysis of the automorphism group of the generalized token graph. |
| title | Generalized Token Graphs |
| topic | Combinatorics 05C76, 05C40, 05C15 |
| url | https://arxiv.org/abs/2509.01773 |