The domination number of the 2-token graph of the complete bipartite graph
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\ge5$ 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}$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.31557
curl -X POST /api/v1/records/arxiv/2610.31557/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.31557/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'