Regularity and Planarity of Token Graphs
| Autor: | Carballosa, Walter, Fabila-Monroy, Ruy, Leaños, Jesús, Rivera, Luis Manuel |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Discussiones Mathematicae Graph Theory, 37(3) (2017), 573-586 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.7151/dmgt.1959 |
| Popis: | Let $G=(V,E)$ be a graph of order $n$ and let $1\leq k< n$ be an integer. The $k$-token graph of $G$ is the graph whose vertices are all the $k$-subsets of $V$, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper we characterize precisely, for each value of $k$, which graphs have a regular $k$-token graph and which connected graphs have a planar $k$-token graph. Comment: 13 pages, 5 figures. Referee suggestions and corrections incorporated (in particular, a mistake in the proof of Theorem 2.9 was fixed). One reference added. Accepted for publication in "Discussiones Mathematicae Graph Theory" |
| Databáze: | arXiv |
| Externí odkaz: |
|