Metraipolis › archive › dc_3a43ef0f199d

On generalized $k$-token graphs with distinguishable tokens and a maximum capacity of $s$ tokens per vertex — arXiv:2611.06275

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.06275
License (as archived)
CC0-1.0
Archived
2026-11-05T18:28:29.851Z
SHA-256 of the archived text
01402502819f7fce36f5ccb5e42a44ba3c45ac6630694d470c7d11719cf279a0
Stable URL of this page
https://metraipolis.com/documento/dc_3a43ef0f199d

How to cite

On generalized $k$-token graphs with distinguishable tokens and a maximum capacity of $s$ tokens per vertex — arXiv:2611.06275 — arXiv (en), https://arxiv.org/abs/2611.06275 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3a43ef0f199d (Metraipolis archive dc_3a43ef0f199d, sha256 01402502819f7fce36f5ccb5e42a44ba3c45ac6630694d470c7d11719cf279a0)
BibTeX
@misc{dc3a43ef0f199d,
  title = {On generalized $k$-token graphs with distinguishable tokens and a maximum capacity of $s$ tokens per vertex — arXiv:2611.06275},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06275},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3a43ef0f199d; sha256 01402502819f7fce36f5ccb5e42a44ba3c45ac6630694d470c7d11719cf279a0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06275. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\ge2\), 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.06275 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:18:33.998Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).