pith. sign in

arxiv: 2604.04845 · v1 · submitted 2026-04-06 · 🧮 math.CO

On Generalized Token Graphs

Xiaodi Song , Cristina Dalf\'o , Miquel \`Angel Fiol , Merc\`e Mora , Shenggui Zhang This is my paper

Pith reviewed 2026-05-10 19:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords supertoken graphstoken graphsCartesian powersgraph connectivitygraph ordergraph sizegraph products
0
0 comments X

The pith

Varying rules for token distinguishability and vertex capacities produces supertoken graphs that recover Cartesian powers with explicit formulas for order, size, and connectivity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces supertoken graphs as a generalization of token graphs on a base graph G. The generalization arises by allowing tokens to be either indistinguishable or distinguishable and by changing how many tokens may occupy each vertex. Specific choices of these rules recover known constructions such as the Cartesian k-th power of G. The authors then give explicit expressions for the number of vertices, the number of edges, and the vertex-connectivity of the resulting graphs.

Core claim

By changing conditions on the nature of the tokens and the number of tokens allowed in each vertex of G, we define a generalization of token graphs, which we call generalized token graphs or simply supertoken graphs. Depending on the above conditions, different families of graphs (such as the Cartesian k-th power of G by itself) are obtained, and we present some of their properties, including order, size, and connectivity.

What carries the argument

The supertoken graph construction, which takes a base graph G together with rules on token distinguishability and per-vertex capacities and produces a new graph whose vertices are the allowed token configurations.

Load-bearing premise

The assumption that the resulting graphs possess distinct applications beyond those of ordinary token graphs and known products, without supplying concrete examples.

What would settle it

A concrete choice of token rules for which the stated connectivity formula fails to match the actual connectivity of the constructed graph, or a parameter setting claimed to yield the Cartesian power that does not.

Figures

Figures reproduced from arXiv: 2604.04845 by Cristina Dalf\'o, Merc\`e Mora, Miquel \`Angel Fiol, Shenggui Zhang, Xiaodi Song.

Figure 1
Figure 1. Figure 1: (a) The graph C4; (b) The supertoken graph F 1 2 (C4) = F2(C4) ∼= K2,4 ⊂ F 2 2 (C4); (c) The supertoken graph F 2 2 (C4); (d) The supertoken graph F 1 2×1 (C4) ⊂ F 2 2×1 (C4); (e) The supertoken graph F 2 2×1 (C4) ∼= C4✷C4. The tokens are white or gray, and the rhombuses in (b)–(e) represent the vertices of the supertoken graphs. Let G = (V, E) be a graph on n vertices. Let k and s be positive integers suc… view at source ↗
Figure 2
Figure 2. Figure 2: A connected graph G with maximum degree ∆(G) = 5. 3 The token graphs F 1 k (G) = Fk(G) In this case, the k tokens are indistinguishable, and the maximum number of tokens per vertex is one. The token graph F 1 k (G) = F 1 k (G) has order n k  and size n−2 k−1  m. Fk(G) is the known k-th symmetric power of G (see Audenaert, Godsil, Royle, and Rudolph [1]), later renamed k-token graph of G by Fabila-Monroy,… view at source ↗
Figure 3
Figure 3. Figure 3: The graphs F 1 2 (P7) (left) and F 5 5 (P3) (right). This gives a vector (β1, . . . , βn) with n − k 0’s and k 1’s, which corresponds to a vertex of αi 0’s. (As shown in the example, the positions of the 1’s indicate the vertices of Pn having a token). Then, in terms of the α ′ i s, a vertex of F 1 k (Pn) is a vector of k components (β ′ 1 , . . . , β′ k ) (representing the vertices of Pn having a token) c… view at source ↗
Figure 4
Figure 4. Figure 4: The graph F 2 3 (C4). For example, for s = 2 and n = 0, 1, 2, . . ., the trinomial coefficients turn out to be 1 1, 1 1, 2, 3, 2, 1 1, 3, 6, 7, 6, 3, 1 1, 4, 10, 16, 19, 16, 10, 4, 1 . . . Let G have vertices indexed by the integers 1, 2, . . . , n. Then, each vertex of the su￾pertoken graph F s k (G) can be represented by a vector (α1, . . . , αn), where αi ∈ [0, s] is the number of tokens of the only col… view at source ↗
Figure 5
Figure 5. Figure 5: The supertoken graph F 1 3×1 (P4). Proposition 6.1. Let G = Pn be a path with order n. Then, F 1 k×1 (G) contains at least one cycle for k ≤ n − 2, and does not contain any cycle for k = n − 1, n. Moreover, for k = n, F 1 k×1 (G) is the graph with n! isolated vertices, and F 1 k×1 (G) = Pn ∪ · · · ∪ Pn | {z } (n−1)! for k = n − 1. Proof. Define V (Pn) = {1, 2, . . . , n}. Let (α1, α2, . . . , αk) be one ve… view at source ↗
Figure 6
Figure 6. Figure 6: The supertoken graph F 1 3×1 (C4). that {α1, α2, . . . , αk} is a permutation on {2, 3, . . . , n} with αj = n, there is no ver￾tex being on its right from the definition shown in (12). Then, we define the relation (α ′ 1 , . . . , α′ k ) ⪰ (α1, . . . , αk) if α ′ j = 1 and α ′ l = αl for l ∈ [k]\{j}, which implies that (α1, . . . , σ(αj ), . . . , αk) ⪰ (α1, . . . , αj , . . . , αk). Then, for any vertex … view at source ↗
read the original abstract

The vertices of a $k$-token graph of a graph $G$ correspond to $k$ indistinguishable tokens placed on $k$ different vertices of $G$. Changing some conditions on both the nature of the tokens and the number of tokens allowed in each vertex of $G$, we define a generalization of token graphs, which we call generalized token graphs or simply supertoken graphs, which have different applications. Depending on the above conditions, different families of graphs (such as the Cartesian $k$-th power of $G$ by itself) are obtained, and we present some of their properties, including order, size, and connectivity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript defines a generalization of k-token graphs, termed supertoken graphs or generalized token graphs, obtained by varying the distinguishability of tokens and the permitted multiplicity of tokens per vertex of the base graph G. Specific parameter choices recover the standard token graph (indistinguishable tokens, at most one per vertex) and the Cartesian k-th power of G (distinguishable tokens, multiples allowed). The authors compute the order, size, and connectivity of the resulting graphs under these conditions via direct counting arguments.

Significance. The central contribution is a parameterized definitional framework that unifies token graphs and Cartesian powers through a common token-placement model. The listed invariants follow immediately from the vertex set (multisets or tuples) and the single-token-move edge rule, using standard multinomial and product-graph counting; these derivations contain no apparent gaps or circularity. The work is primarily expository, offering a clean taxonomy rather than deep new theorems. Its value would increase with concrete application examples, which are asserted but not supplied.

minor comments (3)
  1. Abstract and §1: the claim that the new graphs 'have different applications' is stated without any concrete example, comparison to existing models, or reference to literature on token-graph applications; this is a local motivation issue rather than a mathematical error.
  2. The manuscript should include a small illustrative example (e.g., G = K_3 or P_4 with k=2) showing the vertex/edge sets under each regime to make the definitions more accessible.
  3. Notation for the various regimes (distinguishable vs. indistinguishable, multiplicity bounds) should be introduced with a compact table or explicit parameter list early in the text for clarity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We appreciate the recognition that the derivations of order, size, and connectivity contain no gaps. Below we address the suggestion to include concrete application examples.

read point-by-point responses

  1. Referee: The work is primarily expository, offering a clean taxonomy rather than deep new theorems. Its value would increase with concrete application examples, which are asserted but not supplied.

    Authors: We agree that the manuscript would benefit from explicit examples to demonstrate the framework's utility. The abstract notes that different parameter choices yield graphs with distinct applications, but we did not supply concrete instances in the text. In the revised version we will add a dedicated subsection (likely in the introduction or a new applications section) with specific examples, such as modeling resource allocation in networks where tokens represent indistinguishable units with capacity limits (recovering token graphs) versus distinguishable agents (recovering Cartesian powers). revision: yes

Circularity Check

0 steps flagged

No significant circularity; purely definitional with elementary counting

full rationale

The manuscript defines supertoken graphs by relaxing distinguishability and multiplicity constraints on tokens placed on vertices of G. The vertex set is the corresponding collection of multisets or k-tuples, and edges correspond to moving one token along an edge of G. Order, size, and connectivity are then obtained by direct enumeration and standard product-graph arguments; these derivations contain no fitted parameters, no 'predictions' that reduce to the input definition, and no load-bearing self-citations. The construction is self-contained and recovers known families (Cartesian powers, ordinary token graphs) as special cases without circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on new definitions rather than prior theorems; only standard graph-theoretic background is presupposed.

axioms (1)
  • standard math Standard definitions of graphs, Cartesian products, and the original k-token graph construction
    The paper explicitly builds upon the existing notion of token graphs.
invented entities (1)
  • supertoken graph no independent evidence
    purpose: Generalized placement of tokens with variable distinguishability and vertex capacities
    New object introduced by relaxing two parameters of the token-graph definition.

pith-pipeline@v0.9.0 · 5406 in / 1170 out tokens · 47659 ms · 2026-05-10T19:43:53.428597+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    Audenaert, C

    K. Audenaert, C. Godsil, G. Royle, and T. Rudolph, Symmetric squares of graphs,J. Combin. Theory B97(2007) 74–90

    work page 2007

  2. [2]

    Barik and P

    S. Barik and P. Verma, Spectral properties of token graphs,Linear Algebra Appl.687 (2024) 181–206

    work page 2024

  3. [3]

    Bonnet, T

    É. Bonnet, T. Miltzow, and P. Rzążewski, Complexity of token swapping and its variants,Algorithmica80(2018) 2656–2682. 22

    work page 2018

  4. [4]

    Dalfó, F

    C. Dalfó, F. Duque, R. Fabila-Monroy, M. A. Fiol, C. Huemer, A. L. Trujillo-Negrete, andF.J.ZaragozaMartínez, OntheLaplacianspectraoftokengraphs,Linear Algebra Appl.625(2021) 322–348

    work page 2021

  5. [5]

    Fabila-Monroy, D

    R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood, Token graphs,Graphs Combin.28(3)(2012) 365–380

    work page 2012

  6. [6]

    C. D. Godsil,Algebraic Combinatorics, Chapman and Hall, New York, 1993

    work page 1993

  7. [7]

    R. H. Hammack and G. D. Smith, Cycle bases of reduced powers of graphs,Ars Math. Contemp.12(2017) 183–203

    work page 2017

  8. [8]

    Leaños and C

    J. Leaños and C. Ndjatchi, The edge-connectivity of token graphs,Graphs Combin. 37(2021) 1013–1023

    work page 2021

  9. [9]

    Leaños and A

    J. Leaños and A. L. Trujillo-Negrete, The connectivity of token graphs,Graphs Com- bin.34(2018) 777–790

    work page 2018

  10. [10]

    Yamanaka, E

    K. Yamanaka, E. D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa, and T. Uno, Swapping labeled tokens on graphs, Theoret. Comput. Sci.586(2015) 81–94

    work page 2015

  11. [11]

    Yamanaka, T

    K. Yamanaka, T. Horiyama, J. Mark Keil, D. Kirkpatrick, Y. Otachi, T. Saitoh, R. Uehara, and Y. Uno, Swapping colored tokens on graphs,Theoret. Comput. Sci.729 (2018) 1–10. 23

    work page 2018