Some Properties of Generalized Token Graphs - Muna, Naelufa Syifna Wifaqotul; Raventino; Utami, Rintang; Lia, Febby Desy; Huda, Muhammad Nurul; Susanti, Yeni (Research Center of Inorganic Materials and Coordination Complexes, FMIPA Universitas Sriwijaya, 2026)
The generalized k-token graph GFk(G) is a graph with the k-subsets of V(G) as the vertices, and two different vertices are adjacent if and only if the symmetric difference contains at least one edge of G. This model extends the classical k-token graph by relaxing the adjacency condition, leading to increased edge density and altered topological properties. In this paper, we establish the fundamental properties of GFk(G), including its connectivity, duality, and monotonicity. We provide exact formulas for the vertex degrees and the total size of GF2(G), along with combinatorial bounds for k > 2. Furthermore, we characterize the girth and clique numbers, proving that GFk(G) is highly prone to containing triangles even when the base graph is triangle-free. We also explore the inheritance of Hamiltonicity and bipartiteness, demonstrating that while connectivity is preserved, bipartiteness is lost for almost all bipartite graphs with at least four vertices. Our results provide a comprehensive structural characterization of this generalization, bridging the gap between classical token graphs and broader set-theoretic graph constructions.