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

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

  • Yiting Cai
  • Cristina Dalfó
  • Blas Fernández
  • Miquel Àngel Fiol
Open at sourcePDFDOICite

Abstract

Supertoken graphs Fsk×1(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 Fsk×1(G) is regular. We show that bipartiteness is inherited from G and characterize it for complete base graphs. For s≥2, 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

  1. On generalized token graphs with tokens of different colors
    Cristina Dalfó, Blas Fernández, Miquel Àngel Fiol +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. Restricted Maximum Likelihood Estimation in Generalized Linear Mixed Models
    Luca Maestrini, Francis K. C. Hui, A. H. Welsh
    Statistical SciencePeer-reviewedLicence not statedFull text21 citedStatisticsOpenAlex
  4. Bicyclic Graphs with Maximum Complementary Diminished Sombor Index
    Nicholas Smirnov
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeometry & topologyDOAJ
  5. Corrigendum to "On the Maximum Symmetric Division Deg Index of k-Cyclic Graphs [J. Math. 2022, (2022) \#7783128]"
    Abeer M. Albalahi, Akbar Ali
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{cai2026generalized,
  title = {{On generalized $k$-token graphs with distinguishable tokens and a maximum capacity of $s$ tokens per vertex}},
  author = {Yiting Cai and Cristina Dalfó and Blas Fernández and Miquel Àngel Fiol},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06275},
  eprint = {2611.06275},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06275},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex
AU  - Yiting Cai
AU  - Cristina Dalfó
AU  - Blas Fernández
AU  - Miquel Àngel Fiol
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06275
UR  - https://arxiv.org/abs/2611.06275
AB  - Supertoken graphs F^s_k×1(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×1(G) is regular. We show that bipartiteness is inherited from G and characterize it for complete base graphs. For s≥2, 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.
ER  -