The domination number of the 2-token graph of the complete bipartite graph

Abstract

For a graph $G$, the $2$-token graph $F_2(G)$ has as vertices all $2$-subsets of $V(G)$, with two such subsets adjacent whenever their symmetric difference is an edge of $G$. In this paper, we determine the domination number of the $2$-token graph of the complete bipartite graph $K_{m,n}$, for all integers $2\le m\le n$. We show that it equals $\lceil m/2\rceil +n-1$, except when $m=3$, or when $m\ge 5$ is odd and $n=m+1$; in these two exceptional situations it is one less. Our arguments rely on an explicit characterization of the dominating sets of the $2$-token graph of $K_{m,n}$.

arXiv comment14 pages, 3 Figures, 1 Table. Submitted for publication before the appearance of arXiv:2610.28936, whose results on F_2(K_{m,n}) were obtained independently. This version differs from the submitted one only by a footnote on arXiv:2610.28936 and three added references in the conclusions section