On supertoken graphs

Cristina Dalf\'o; Miquel \`Angel Fiol; M\'onica A. Reyes

arxiv: 2604.06164 · v1 · submitted 2026-04-07 · 🧮 math.CO

On supertoken graphs

M\'onica A. Reyes , Cristina Dalf\'o , Miquel \`Angel Fiol This is my paper

Pith reviewed 2026-05-10 18:55 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C6905C5005C15

keywords supertoken graphstoken graphsindependence numberclique numberchromatic numberspectral radiusgraphs on cyclesaugmented graphs

0 comments

The pith

Supertoken graphs allow multiple tokens per vertex and yield bounds on independence, clique, and chromatic numbers.

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

This paper generalizes token graphs to supertoken graphs by permitting any number of tokens to occupy the same vertex instead of restricting to one per vertex. It supplies a formal definition together with the basic adjacency and degree properties of the resulting graphs. Bounds and exact values are then derived for the independence number, clique number, and chromatic number of supertoken graphs. The work also introduces the p-augmented 2-token graphs of cycles as a concrete infinite family and computes their spectral radius.

Core claim

Supertoken graphs arise when the token placement on a base graph is allowed to put more than one token on any vertex. The resulting graphs have vertex sets corresponding to multisets of tokens and edges reflecting admissible placements; their independence number, clique number, and chromatic number admit explicit upper and lower bounds or exact determinations in terms of the base graph and token multiplicity. The p-augmented 2-token graphs of cycles form a new infinite family whose largest adjacency eigenvalue is determined or bounded as part of the construction.

What carries the argument

The supertoken graph construction, obtained by replacing single-token placements with multisets of tokens on the vertices of a base graph.

If this is right

The chromatic number of any supertoken graph is at most the chromatic number of the base graph times the maximum token multiplicity.
Exact clique numbers can be obtained when the base graph is vertex-transitive.
The spectral radius of the p-augmented 2-token graphs of cycles is a continuous function of p and approaches a limit determined by the cycle's eigenvalues.
Independence numbers of supertoken graphs on cycles equal the floor of half the number of distinct placements.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same multiset construction could be applied to directed graphs or hypergraphs to obtain analogous parameter bounds.
These graphs offer a combinatorial model for resource allocation where vertices represent servers with positive integer capacities.
Spectral results on the cycle family suggest that closed-form eigenvalues may exist for other regular base graphs such as paths or complete graphs.

Load-bearing premise

The allowance of multiple tokens per vertex must produce a non-degenerate graph on which the independence, clique, and chromatic numbers admit bounds that are neither trivial nor collapse to the size of the full placement set.

What would settle it

Take the 2-token supertoken graph on a 5-cycle with augmentation parameter p=1 and compute its independence number by hand; if the value lies strictly outside the interval predicted by the paper's bound formulas, the claimed bounds are incorrect.

Figures

Figures reproduced from arXiv: 2604.06164 by Cristina Dalf\'o, Miquel \`Angel Fiol, M\'onica A. Reyes.

**Figure 1.** Figure 1: The strong product C3 ⊠ P3. Graph operation Distinguished tokens Max. no. of tokens Max. no. of tokens on each vertex moved at each step Fk(G) No 1 1 Fk(G) No k 1 G□k Yes k 1 G⊠k Yes k k [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** Figure 2: Left: A maximum independent set in C7 ⊠ C7 (white vertices). Middle: A maximum independent set in F2(C7) (white vertices). Right: The cycle C7 with three chords and no triangles. Lov´asz [12] showed that pk α(C⊠k n ) ≤ p2 α(C⊠2 5 ) for every k ≥ 2, where α is the independence number. This makes it interesting to study the behavior of α(C ⊠2 n ) for a cycle Cn with n > 5. With this aim in mind, let us cons… view at source ↗

**Figure 3.** Figure 3: The complete graph K4, its 2-supertoken, its 3-supertoken, and a regular partition of its 3-supertoken. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

**Figure 4.** Figure 4: Left: The hypercube Q3. Right: The 2-supertoken graph F2(Q3). The white vertices form a maximum independent set. Moreover, an interesting property of the supertoken of the path graph Pn is discussed in Baskoro, Dalf´o, Fiol, and Simanjuntak [2], where it is noted that the 2-supertoken graph F2(Pn) is isomorphic to the 2-token graph F2(Pn+1). In the same article, the authors also established several results… view at source ↗

**Figure 5.** Figure 5: The graph C 4 20 with α(C 4 20) = 4 (the white vertices). We have α(F3(C 4 20)) ≥ 104. confusability graph, the information rate is log2 α(Q3) = 2. Moreover, in F2(G), the information rate of strings of length k = 2 per symbol is at least log2 (α(F2(G))) 2 = log2 √ 20 ≈ 2.1609. In contrast, it can be shown that log2 (α(Fk(G))) k = log2 k s log2 2 k + 3 k < 2, that is, in this case, the minimum informat… view at source ↗

**Figure 6.** Figure 6: The base graph of the graphs F2(Cn) for n odd [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗

**Figure 7.** Figure 7: The function λ(r, k) giving the eigenvalues of F2(C11). 00 11 22 33 44 55 66 77 01 12 23 45 34 56 70 71 02 13 24 35 46 57 60 72 03 14 25 36 47 50 61 04 15 67 26 37 00 11 22 33 55 44 66 77 01 12 23 34 45 56 70 71 02 13 24 46 35 57 60 72 03 14 25 36 47 50 61 04 67 15 37 26 88 78 80 68 81 82 58 83 48 [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗

**Figure 8.** Figure 8: The graphs F2(C8) and F2(C9). The white vertices form independent sets. (positive or negative) sign, we have a total of (r + 1)n = 4r 2 + 2r + 3 = N/2 eigenvalues, as claimed. □ 11 [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗

**Figure 9.** Figure 9: The graphs F2(C6) and F2(C7). The white vertices form independent sets. ω = e i 2π 7 , z = ω r λr,1 λr,2 λr,3 λr,4 sp(B(ω 0 )) 3.759 2 −3.064 −0.6948 sp(B(ω 1 )) = sp(B(ω 6 )) 2.761 0.6258 −1.802 −3.387 sp(B(ω 2 )) = sp(B(ω 5 )) 2.344 1.247 −0.4331 −1.910 sp(B(ω 3 )) = sp(B(ω 4 )) 0.6818 0.1546 −0.4450 −0.8364 [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗

**Figure 10.** Figure 10: The supertoken graph F 3 3 (K4) of [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗

**Figure 11.** Figure 11: Left: The 4-augmented 2-token graph F 4 2 (C5) of the 5-cycle with independent number α(F 4 2 (C5)) = 15 (the white vertices). Right: The 4-augmented 2-token graph F 4 2 (C4) of the 4-cycle with independent number α(F 4 2 (C4)) = 12 (the white vertices). In a thick line, there are the edges of F2(C5) and F2(C4), respectively. n n n n n n n n {i, i + r} {i, i + r − 1}{i, i + r − 2} {i, i + 1} 0 {i, i} 1 {i… view at source ↗

**Figure 12.** Figure 12: The quotient graph of F p 2 (C2r+1). In particular, the spectral radius of Qr with positive eigenvector, or maximum root of ϕr(x), gives the spectral radius of F p 2 (Cn). For instance, in [PITH_FULL_IMAGE:figures/full_fig_p018_12.png] view at source ↗

read the original abstract

We generalize the concept of token graphs to obtain supertoken graphs. In the latter case, there can be more than one token in a vertex. We formally define supertoken graphs and establish their basic properties. Moreover, we provide some bounds and exact values on the independence number, clique number, and chromatic number of these graphs. Finally, we construct a new infinite family of graphs, which we call the $p$-augmented 2-token graphs of cycles, and study their properties, including the spectral radius or largest adjacency eigenvalue.

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.

Desk Editor's Note private letter to a colleague

This is a straightforward multiset generalization of token graphs with explicit bounds on three invariants and one new infinite family on cycles.

read the letter

Hi, the main thing to know is that the paper defines supertoken graphs by allowing multiple tokens on a single vertex, then gives bounds and exact values for independence number, clique number, and chromatic number, and builds a concrete infinite family called p-augmented 2-token graphs of cycles whose spectral radius they also examine. The generalization keeps the same edge rule based on moving one token, so the extension is direct and well-defined. They lay out the definitions cleanly and supply both upper and lower bounds plus some exact values, which is useful for anyone who wants to compute these parameters on the new objects. The new family is the clearest addition; it is not in the earlier token-graph papers they cite and gives something specific to study. The work is formally grounded with explicit constructions, so the claims are checkable. On the softer side, the core move is incremental rather than transformative, and the bounds appear to come from standard applications of known graph-theoretic facts rather than new machinery. Without the full proofs it is hard to judge how tight the bounds turn out to be, but nothing in the setup suggests degeneration into trivial graphs or hidden circularity. This is for combinatorial graph theorists who already follow token graphs or reconfiguration problems. A reader in that niche will get concrete new examples and numbers to work with. It deserves a serious referee because the constructions are reproducible and the invariants are standard ones that can be verified or improved upon.

Referee Report

0 major / 3 minor

Summary. The paper generalizes token graphs to supertoken graphs, allowing multiple tokens per vertex via multisets or distributions. It formally defines these graphs, establishes basic properties, provides bounds and exact values for the independence number, clique number, and chromatic number, and constructs the infinite family of p-augmented 2-token graphs of cycles, analyzing their properties including the spectral radius.

Significance. If the results hold, this provides a natural, well-defined extension of token graphs that preserves the movement-based edge condition while enabling non-trivial parameter bounds and a concrete new infinite family with spectral analysis. The explicit constructions and focus on standard invariants strengthen the contribution to combinatorial graph theory and reconfiguration problems.

minor comments (3)

Introduction: the motivation section would benefit from a short paragraph contrasting supertoken graphs with ordinary token graphs on a small example graph (e.g., C_4 with k=2) to highlight where multiplicity changes the structure.
Definition of p-augmented 2-token graphs (likely §4): include an explicit small diagram or adjacency list for p=1 on C_5 to make the augmentation construction immediately verifiable.
Chromatic-number bounds: the statement that certain exact values hold should specify the precise range of parameters (n,p,k) for which equality is attained, rather than leaving it implicit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work on supertoken graphs, their assessment of its significance, and the recommendation for minor revision. We will incorporate minor improvements to the manuscript as appropriate.

Circularity Check

0 steps flagged

No significant circularity; definitions and bounds are self-contained

full rationale

The paper defines supertoken graphs explicitly as a direct generalization of token graphs (allowing multiple tokens per vertex) and constructs the p-augmented 2-token graphs of cycles by explicit rules. It then derives bounds and exact values for independence, clique, and chromatic numbers, plus spectral radius, via standard graph-theoretic arguments on these objects. No equations reduce to fitted parameters renamed as predictions, no self-citations are load-bearing for core claims, and no ansatzes or uniqueness theorems are imported from prior author work to force results. The derivation chain is independent of its inputs beyond the initial definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claims rest on the standard axioms of undirected graph theory together with the newly introduced supertoken and p-augmented constructions; no free parameters or externally validated entities are visible.

axioms (1)

standard math Standard axioms of undirected simple graphs, including vertex/edge sets and adjacency relations.
Implicitly used when defining token placements and adjacency of configurations.

invented entities (2)

supertoken graph no independent evidence
purpose: Generalization of token graphs allowing multiple tokens per vertex
Newly defined in the paper; no independent existence proof or external validation supplied.
p-augmented 2-token graph of a cycle no independent evidence
purpose: New infinite family for spectral analysis
Constructed explicitly in the paper as an augmentation of the 2-token cycle graph.

pith-pipeline@v0.9.0 · 5381 in / 1374 out tokens · 53203 ms · 2026-05-10T18:55:04.677821+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[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]

E. T. Baskoro, C. Dalf´ o, M. A. Fiol, and R. Simanjuntak, On some metric properties of supertoken graphs,Util. Math.123(2024) 19–33

work page 2024
[3]

D. M. Cvetkovi´ c, Graphs and their spectra,Publ. Elektrotehn. Fak. Ser. Mat. Fiz.354-356(1971) 1–50

work page 1971
[4]

Dalf´ o, M

C. Dalf´ o, M. A. Fiol, M. Miller, J. Ryan, and J. ˇSir´ aˇ n, An algebraic approach to lifts of digraphs, Discrete Appl. Math.269(2019) 68–76

work page 2019
[5]

de Alba, W

H. de Alba, W. Carballosa, J. Lea˜ nos, and L. M. Rivera, Independence and matching numbers of some token graphs,Australas. J. Combin.76(3)(2020) 387–403

work page 2020
[6]

Fabila-Monroy, D

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

work page 2012
[7]

C. M. Da Fonseca and V. Kowalenko, Eigenpairs of a family of tridiagonal matrices: three decades later,Acta Math. Hungar.160(2020) 376–389

work page 2020
[8]

Ghrist,Configuration spaces of graphs in robotics

R. Ghrist,Configuration spaces of graphs in robotics. In: New Directions in Applied Mathematics, IMA Volumes in Mathematics and its Applications, Springer, 2002

work page 2002
[9]

Hall, On representatives of subsets,J

P. Hall, On representatives of subsets,J. London Math. Soc.10:1(1935) 26–30

work page 1935
[10]

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

work page 2017
[11]

Losonczi, Eigenvalues and eigenvectors of some tridiagonal matrices,Acta Math

L. Losonczi, Eigenvalues and eigenvectors of some tridiagonal matrices,Acta Math. Hung.60(1992) 309–332

work page 1992
[12]

Lov´ asz, On the Shannon capacity of a graph,IEEE Trans

L. Lov´ asz, On the Shannon capacity of a graph,IEEE Trans. Inform. Theory25(1)(1979) 1–7

work page 1979
[13]

(2024), The On-Line Encyclopedia of Integer Sequences, Published electron- ically athttps://oeis.org

OEIS Foundation Inc. (2024), The On-Line Encyclopedia of Integer Sequences, Published electron- ically athttps://oeis.org

work page 2024
[14]

M. A. Reyes, C. Dalf´ o, M. A. Fiol, and A. Messegu´ e, On the spectra of token graphs of cycles and other graphs,Linear Algebra Appl.679(2023) 38–66

work page 2023
[15]

X. Song, C. Dalf´ o, M. A. Fiol, M. Mora, and S. Zhang, On generalized token graphs,Filomat40:2 (2026) 721–738

work page 2026
[16]

J. J. Watkins,Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, 2007

work page 2007
[17]

J. L. A. Yebra, M. A. Fiol, P. Morillo, and I. Alegre, The diameter of undirected graphs associated to plane tessellations,Ars Combin.20B(1985) 159–171

work page 1985
[18]

Yueh, Eigenvalues of several tridiagonal matrices,Appl

W.-C. Yueh, Eigenvalues of several tridiagonal matrices,Appl. Math. E-Notes5(2005) 66–74. Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia Email address:monicaandrea.reyes@udl.cat Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia Email address:cristina.dalfo@udl.cat Departament de Matem `a...

work page 2005

[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]

E. T. Baskoro, C. Dalf´ o, M. A. Fiol, and R. Simanjuntak, On some metric properties of supertoken graphs,Util. Math.123(2024) 19–33

work page 2024

[3] [3]

D. M. Cvetkovi´ c, Graphs and their spectra,Publ. Elektrotehn. Fak. Ser. Mat. Fiz.354-356(1971) 1–50

work page 1971

[4] [4]

Dalf´ o, M

C. Dalf´ o, M. A. Fiol, M. Miller, J. Ryan, and J. ˇSir´ aˇ n, An algebraic approach to lifts of digraphs, Discrete Appl. Math.269(2019) 68–76

work page 2019

[5] [5]

de Alba, W

H. de Alba, W. Carballosa, J. Lea˜ nos, and L. M. Rivera, Independence and matching numbers of some token graphs,Australas. J. Combin.76(3)(2020) 387–403

work page 2020

[6] [6]

Fabila-Monroy, D

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

work page 2012

[7] [7]

C. M. Da Fonseca and V. Kowalenko, Eigenpairs of a family of tridiagonal matrices: three decades later,Acta Math. Hungar.160(2020) 376–389

work page 2020

[8] [8]

Ghrist,Configuration spaces of graphs in robotics

R. Ghrist,Configuration spaces of graphs in robotics. In: New Directions in Applied Mathematics, IMA Volumes in Mathematics and its Applications, Springer, 2002

work page 2002

[9] [9]

Hall, On representatives of subsets,J

P. Hall, On representatives of subsets,J. London Math. Soc.10:1(1935) 26–30

work page 1935

[10] [10]

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

work page 2017

[11] [11]

Losonczi, Eigenvalues and eigenvectors of some tridiagonal matrices,Acta Math

L. Losonczi, Eigenvalues and eigenvectors of some tridiagonal matrices,Acta Math. Hung.60(1992) 309–332

work page 1992

[12] [12]

Lov´ asz, On the Shannon capacity of a graph,IEEE Trans

L. Lov´ asz, On the Shannon capacity of a graph,IEEE Trans. Inform. Theory25(1)(1979) 1–7

work page 1979

[13] [13]

(2024), The On-Line Encyclopedia of Integer Sequences, Published electron- ically athttps://oeis.org

OEIS Foundation Inc. (2024), The On-Line Encyclopedia of Integer Sequences, Published electron- ically athttps://oeis.org

work page 2024

[14] [14]

M. A. Reyes, C. Dalf´ o, M. A. Fiol, and A. Messegu´ e, On the spectra of token graphs of cycles and other graphs,Linear Algebra Appl.679(2023) 38–66

work page 2023

[15] [15]

X. Song, C. Dalf´ o, M. A. Fiol, M. Mora, and S. Zhang, On generalized token graphs,Filomat40:2 (2026) 721–738

work page 2026

[16] [16]

J. J. Watkins,Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, 2007

work page 2007

[17] [17]

J. L. A. Yebra, M. A. Fiol, P. Morillo, and I. Alegre, The diameter of undirected graphs associated to plane tessellations,Ars Combin.20B(1985) 159–171

work page 1985

[18] [18]

Yueh, Eigenvalues of several tridiagonal matrices,Appl

W.-C. Yueh, Eigenvalues of several tridiagonal matrices,Appl. Math. E-Notes5(2005) 66–74. Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia Email address:monicaandrea.reyes@udl.cat Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia Email address:cristina.dalfo@udl.cat Departament de Matem `a...

work page 2005