TOPICS
Search

Token Graph

The k-token graph F_k(G) of a simple graph G has the k-element subsets of its vertex set as vertices. Two subsets are adjacent precisely when their symmetric difference consists of two vertices joined by an edge of G. Here 1<=k<|V(G)|. The graph F_1(G) is isomorphic to G, and taking complements of subsets gives F_k(G)=F_(n-k)(G) when n=|V(G)|.

Acosta Troncoso and Rivera (2026) proved that the domination number of the 2-token graph of the path graph P_n, for n>=13, is

gamma(F_2(P_n))=(n^2+5n+c_r)/(10),
(1)

where r=nmod5 and (c_0,c_1,c_2,c_3,c_4)=(-30,-36,-34,-34,-36). Acosta Troncoso and Rivera (2026) report using Claude for code and computer-assisted parts of the proof, with author auditing.

The reconstruction question asks whether a 2-token graph determines its root up to graph isomorphism. Luo and Hu (2026) proved that, for finite simple graphs G,H of order at least three, F_2(G)=F_2(H) iff G=H. Luo and Hu (2026) also classify the automorphism groups for connected graphs of order at least five.

Chinman et al. (2026) determined the domination number of the 2-token graph of a complete bipartite graph. For 2<=m<=n,

gamma(F_2(K_(m,n)))={m/2+n-1 if m is even;; (m-1)/2+n-1 if m=3 or m=n-1>=5 is odd;; (m-1)/2+n otherwise.
(2)

See also

Domination Number, Graph Isomorphism, Path Graph, Simple Graph, Symmetric Difference

Explore with Wolfram|Alpha

References

Acosta Troncoso, E. and Rivera, L. M. "The Domination Number of the 2-Token Graph of Path Graphs." 8 Oct 2026. https://arxiv.org/abs/2610.11265.Chinman, N.; Cortijo, A.; Pedroni, B.; Seong, I.; and Stenger, L. "The Domination Number of the k-Token Graph of the Complete Bipartite Graph K_(m,n)." 20 Oct 2026. https://arxiv.org/abs/2610.28936.Luo, Y. and Hu, H. "Reconstruction and Symmetry of Two-Token Graphs." 9 Oct 2026. https://arxiv.org/abs/2610.14135.

Cite this as:

Weisstein, Eric W. "Token Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TokenGraph.html

Subject classifications