Skip to content
DraconiticResearch
Search Sources API
194,164 studies31 sourcesUpdated 54 min ago
PreprintCC BY-NC-ND 4.0arXiv

On generalized token graphs with tokens of different colors

  • Cristina Dalfó
  • Blas Fernández
  • Miquel Àngel Fiol
  • Mónica A. Reyes
Open at sourcePDFDOICite

Abstract

We generalize the concept of token graphs, and we call them supertoken graphs. In this work, we consider the variant in which tokens are distinguishable (for instance, by color) and at most one token is allowed on each vertex. We formally define this kind of supertoken graphs and present their basic properties. We study their diameter, in which cases they are Cayley graphs, and their spectra. Moreover, we provide bounds or exact values for the independence, the vertex cover, the clique, and the chromatic numbers of these graphs. Finally, we characterize the cases in which the supertoken graphs of complete graphs are planar.

Related

  1. On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex
    Yiting Cai, Cristina Dalfó, Blas Fernández +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Automorphisms of Token Graphs That Send $4$-Cycles Generated by Two Edges to Cycles Generated by a $4$-Cycle and Two Tokens
    Ruy Fabila-Monroy, Sergio Gerardo Gómez-Galicia, Ana Laura Trujillo-Negrete
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. On the Spectra of Generalized Token Graphs of Stars
    Cristina Dalfó, Miquel Àngel Fiol, Berenice Martínez-Barona +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Thinking in Tokens, Talking in Bits: A Practical Interface for Token Communication
    Chanho Park, Bumsu Park, Soonhee Kwon +2
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. Coloring t-perfect graphs with fewer colors
    Matija Novaković, Stefan Weltge
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{dalfo2026generalized,
  title = {{On generalized token graphs with tokens of different colors}},
  author = {Cristina Dalfó and Blas Fernández and Miquel Àngel Fiol and Mónica A. Reyes},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.08186},
  eprint = {2611.08186},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08186},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - On generalized token graphs with tokens of different colors
AU  - Cristina Dalfó
AU  - Blas Fernández
AU  - Miquel Àngel Fiol
AU  - Mónica A. Reyes
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.08186
UR  - https://arxiv.org/abs/2611.08186
AB  - We generalize the concept of token graphs, and we call them supertoken graphs. In this work, we consider the variant in which tokens are distinguishable (for instance, by color) and at most one token is allowed on each vertex. We formally define this kind of supertoken graphs and present their basic properties. We study their diameter, in which cases they are Cayley graphs, and their spectra. Moreover, we provide bounds or exact values for the independence, the vertex cover, the clique, and the chromatic numbers of these graphs. Finally, we characterize the cases in which the supertoken graphs of complete graphs are planar.
ER  -