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

Cartesian productschromatic numbercliquesconnectivitydiameterHamiltonian pathsJohnson graphstoken graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) 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

• 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
• A Survey of Combinatorial Gray Codes
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Graph reconstruction—a survey
• 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?)
• 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

(50)

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

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)