Domination number of Token Graphs

2025/09/19 by Ruy Fabila‐Monroy, Fabila-Monroy, Ruy, Sergio Gerardo Gómez-Galicia +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2509.16448

Abstract

The k-token graph of G is the graph, F_k(G), whose vertices are all the k-subsets of V(G); with two of them adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we study the domination number of the token graphs of the star, S_n, and the complete graph, K_n.

Citations

• Domination in Graph Theory: A Bibliometric Analysis of Research Trends, Collaboration and Citation Networks
• Well-covered Token Graphs
• Symmetric Squares of Graphs
• Constructing physically intuitive graph invariants
• On a Packing and Covering Problem

Related

• Well-covered Token Graphs
• Generalized Token Graphs
• On the algebraic connectivity of token graphs
• On the Laplacian spectra of token graphs
• On the Automorphism Group of Token Graphs of Complete Bipartite Graphs