Token Graphs

Abstract

For a graph $G$ and integer $k\ge 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.

References in corpus (1)

• Recent Progress in Graph Pebbling

Cited by in corpus (16)

• Regularity and Planarity of Token Graphs
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• Droplet states in quantum XXZ spin systems on general graphs
• Reconfiguration of Connected Graph Partitions
• Token Swapping on Trees
• Hamiltonicity of Token Graphs of some Join Graphs
• On Reconfiguration Graphs of Independent Sets under Token Sliding
• The automorphism groups of some token graphs
• Independence numbers of some double vertex graphs and pair graphs
• Hamiltonicity of the Double Vertex Graph and the Complete Double Vertex Graph of some Join Graphs
• The Edge-connectivity of Token Graphs
• On the Laplacian spectra of token graphs
• Well-covered Token Graphs
• Discrete homotopy of token configurations
• A study on token digraphs
• Exploring the 3-Token Graph of Particular Graphs