Some Properties of Generalized Token Graphs

Abstract

The generalized k-token graph GF_k(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 GF_k(G), including its connectivity, duality, and monotonicity. We provide exact formulas for the vertex degrees and the total size of GF₂(G), along with combinatorial bounds for k > 2. Furthermore, we characterize the girth and clique numbers, proving that GF_k(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.