Token Graphs |
| |
Authors: | Ruy Fabila-Monroy David Flores-Peñaloza Clemens Huemer Ferran Hurtado Jorge Urrutia David R. Wood |
| |
Affiliation: | (1) Department of Mathematics, Mittweida University of Applied Sciences, Technikumplatz 17, 09648 Mittweida, Germany |
| |
Abstract: | For a graph G and integer k ≥ 1, we define the token graph F k (G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F k (G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of F k (G) 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 one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|