Regularity and planarity of token graphs

DOI10.7151/DMGT.1959MaRDI QIDQ2364080zbMATH OpenOpenAlexFDO

Authors Walter Carballosa, R. Fabila-Monroy, J. Leaños, Luis Manuel Rivera

Publication date 17 July 2017

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

zbMATH Keywords

regularityplanarityJohnson graphtoken graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: Let $G=(V,E)$ be a graph of order $n$ and let $1leqk<n$ be an integer. The $k$-token graph of $G$ is the graph whose vertices are all the $k$-subsets of $V$, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper we characterize precisely, for each value of $k$, which graphs have a regular $k$-token graph and which connected graphs have a planar $k$-token graph.

Recommendations

• Token graphs
• On the Connectivity of Token Graphs of Trees
• On the 2-token graph of a graph
• The connectivity of token graphs
• The edge-connectivity of token graphs

Cites work

• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Lower bounds for constant weight codes
• Metric dimension of some distance-regular graphs
• Neighbour-transitive codes in Johnson graphs
• On Topological Invariants of the Product of Graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• On the chromatic number, colorings, and codes of the Johnson graph
• Practical graph isomorphism. II.
• Sporadic neighbour-transitive codes in Johnson graphs
• Token graphs
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(20)

• Entanglement entropy bounds in the higher spin XXZ chain
• On the Connectivity of Token Graphs of Trees
• Hamiltonicity of token graphs of fan graphs
• Some results on the Laplacian spectra of token graphs
• On the Laplacian spectra of token graphs
• Droplet states in quantum XXZ spin systems on general graphs
• The edge-connectivity of token graphs
• On the 2-token graph of a graph
• Token graphs
• The packing number of the double vertex graph of the path graph
• Automorphism group of 2-token graph of the Hamming graph
• Edge-transitive token graphs
• Independence and matching numbers of some token graphs
• The connectivity of token graphs
• Independence numbers of some double vertex graphs and pair graphs
• The automorphisms of 2-token graphs
• A Schrödinger operator approach to higher spin XXZ systems on general graphs
• The automorphism groups of some token graphs
• Spectral properties of token graphs
• Entanglement entropy bounds for droplet states of the XXZ model on the strip

Describes a project that uses

Uses Software

• Traces
• SageMath
• nauty

This page was built for publication: Regularity and planarity of token graphs

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