Token graphs

DOI10.1007/S00373-011-1055-9MaRDI QIDQ1926040zbMATH OpenOpenAlexWikidataFDO

Authors R. Fabila-Monroy, D. Flores-Peñaloza, Clemens Huemer, J. Urrutia, David R. Wood, Ferran Hurtado

Publication date 27 December 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.4774

zbMATH Keywords

chromatic numberdiameterconnectivityJohnson graphscliquesCartesian productsHamiltonian pathstoken graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: For a graph $G$ and integer $kgeq1$, 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.

Recommendations

• On the 2-token graph of a graph
• Regularity and planarity of token graphs
• On the Connectivity of Token Graphs of Trees
• The connectivity of token graphs
• Independence and matching numbers of some token graphs

Cites work

• scientific article; zbMATH DE number 4132192 (Why is no real title available?)
• scientific article; zbMATH DE number 1439473 (Why is no real title available?)
• scientific article; zbMATH DE number 1439479 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3380631 (Why is no real title available?)
• A Survey of Combinatorial Gray Codes
• A completion of Lu's determination of the spectrum for large sets of disjoint Steiner triple systems
• A linear-time algorithm for the feasibility of pebble motion on trees
• A new existence proof for large sets of disjoint Steiner triple systems
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Graph reconstruction—a survey
• Number of Odd Binomial Coefficients
• On large sets of disjoint Steiner triple systems. I
• On the chromatic number, colorings, and codes of the Johnson graph
• On the number of odd binomial coefficients
• The chip-firing game
• The exact bound in the Erdős-Ko-Rado theorem

Cited in

(47)

• On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs
• Automorphism groups of 2-token graph of Cartesian product of two cycles
• Token sliding on split graphs
• On reconfiguration graphs of independent sets under token sliding
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• On the spectra of token graphs of cycles and other graphs
• Well-covered token graphs
• On the spectra and spectral radii of token graphs
• Some bounds on the Laplacian eigenvalues of token graphs
• On the Connectivity of Token Graphs of Trees
• Hamiltonicity of token graphs of fan graphs
• Complexity of token swapping and its variants
• On the algebraic connectivity of some token graphs
• Some results on the Laplacian spectra of token graphs
• Reconfiguration of connected graph partitions
• On the Laplacian spectra of token graphs
• Introduction to reconfiguration
• Graphs isomorphisms under edge-replacements and the family of amoebas
• Droplet states in quantum XXZ spin systems on general graphs
• Garland's method for token graphs
• Nonuniform subset graphs associated with any graph
• A study on token digraphs
• Automorphism groups of a class of 2-token graphs
• The edge-connectivity of token graphs
• On the 2-token graph of a graph
• Laplacian spectral radius and integrality of token graphs
• The packing number of the double vertex graph of the path graph
• Token graphs of Cayley graphs as lifts
• Automorphism group of 2-token graph of the Hamming graph
• Edge-transitive token graphs
• On the treewidth of token and Johnson graphs
• Independence and matching numbers of some token graphs
• A general method to find the spectrum and eigenspaces of the k-token graph of a cycle, and 2-token through continuous fractions
• On some metric properties of supertoken graphs
• Regularity and planarity of token graphs
• The connectivity of token graphs
• On token signed graphs
• Independence numbers of some double vertex graphs and pair graphs
• On the automorphism group of token graphs of complete bipartite graphs
• The automorphisms of 2-token graphs
• On the algebraic connectivity of token graphs and graphs under perturbations
• Token Swapping on Trees
• Cubical token systems
• The automorphism groups of some token graphs
• Spectral properties of token graphs
• On the 2-Token Graphs of Some Disjoint Union of Graphs
• Independence numbers of the 2-token graphs of some join graphs

This page was built for publication: Token graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1926040)