The domination number of the $k$-token graph of the complete bipartite graph $K_{m,n}$

Abstract

This paper is about token graphs and domination number. Let $G=(X,E)$ denote an undirected graph that is connected, with no loops or multiple edges, vertex set $X$, and edge set $E$. Pick a positive integer $k\le |X|$. The $k$-token graph of $G$, denoted by $F_k(G)$, is defined as follows. The vertex set $\mathcal{X}$ consists of all $k$-subsets of $X$. Two vertices $x,y\in \mathcal{X}$ are adjacent whenever the symmetric difference of $x$ and $y$ consists of two vertices that form an edge in $E$. In this paper, we compute the exact value for the domination number of $F_2(K_{m,n})$ where $K_{m,n}$ is the complete bipartite graph with parameters $m,n$. We present some bounds for the domination number of $F_k(K_{m,n})$ when $k\ge 3$.

arXiv comment14 pages, 5 figures