On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex

arXiv:2611.06275 · math.CO · Submitted 2026-11-04 · Read on arXiv

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