Token Graphs

Details Token Graphs Token Graphs

2009-10-25

arxiv.org/abs/0910.4774v1

Mathematics

Combinatorics

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Token Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Token Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Token Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-561957