On generalized token graphs

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. © 2026, University of Nis. All rights reserved.

2020 Mathematics Subject Classification. Primary 05C15; Secondary 05C10, 05C50. Keywords. Token graph, Cartesian product, connectivity. Received: 27 July 2025; Revised: 13 October 2025; Accepted: 19 November 2025 Communicated by Paola Bonacini The research of the first and last authors has been supported by National Natural Science Foundation of China (No. 12471334, No. 12131013), and Shaanxi Fundamental Science Research Project for Mathematics and Physics (No. 22JSZ009). The research of the second and third authors was funded by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The third author\u2019s research is also supported by a grant from the Universitat Polit\u00E8cnica de Catalunya, reference AGRUPS-2024. The fourth author\u2019s research is supported by grants PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033PID2023-150725NB-I00 and Gen. Cat. DGR 2017SGR1336. * Corresponding author: Cristina Dalf\u00F3 Email addresses: songxd@mail.nwpu.edu.cn (Xiaodi Song), cristina.dalfo@udl.cat (Cristina Dalf\u00F3), miguel.angel.fiol@upc.edu (Miquel \u00C0ngel Fiol), merce.mora@upc.edu (Merc\u00E8 Mora), sgzhang@nwpu.edu.cn (Shenggui Zhang) ORCID iDs: https://orcid.org/0000-0002-6859-7443 (Xiaodi Song), https://orcid.org/0000-0002-8438-9353 (Cristina Dalf\u00F3), https://orcid.org/0000-0003-1337-4952 (Miquel \u00C0ngel Fiol), https://orcid.org/0000-0001-6923-0320 (Merc\u00E8 Mora), https://orcid.org/0000-0002-9596-0826 (Shenggui Zhang)