Regularity and planarity of token graphs

DOI10.7151/DMGT.1959zbMATH Open1366.05028arXiv1510.00424OpenAlexW2192627873MaRDI QIDQ2364080FDOQ2364080

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)

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.

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

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

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)

Cites Work

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

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
• On the 2-token graph of a graph
• The edge-connectivity of token graphs
• Token graphs
• Automorphism group of 2-token graph of the Hamming graph
• The packing number of the double vertex graph of the path 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

Uses Software

• nauty
• SageMath
• Traces

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)