On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex
math.CO
Submitted: 2026-11-04
Updated: 2026-11-04
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: Supertoken graphs F s k times1(G), also known as generalized token graphs, model configurations of k distinguishable tokens on a graph G, with at most s tokens at each vertex.
Terminology
Abstract
Supertoken graphs F s k times1(G), also known as generalized token graphs, model configurations of k distinguishable tokens on a graph G, with at most s tokens at each vertex. We study structural and metric properties of these graphs in terms of the base graph. For regular G, we characterize when F s k times1(G) is regular. We show that bipartiteness is inherited from G and characterize it for complete base graphs. For s at least2, we characterize connectedness and show that t-vertex-connectivity of G implies t-vertex-connectivity of the supertoken graph. We obtain exact diameter formulas in several regimes, including complete graphs and stars, and derive lower bounds and a conjectured formula for odd cycles. We also determine the clique number, give bounds and equality conditions for the chromatic number, and characterize planarity for complete base graphs.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality