no. 17 · Wednesday 18 November 2026
Independent sets in the 2-token graph of a cycle and kings on the torus
Abstract
The 2-token graph of the cycle $C_n$ and the king graph on the $n\times n$ torus are known to have the same independence number. Answering a question of Reyes, Dalfó and Fiol, for every $n\ge4$ we give an explicit bijection between a maximum independent set of the king graph and a maximum independent set of the $2$-token graph: each pair of tokens is represented by a king placed in the row of one of its two tokens and in the column given by their sum. We also show that the $2$-token graph of $C_n$ has exactly one maximum independent set, or exactly $n$ when $n\equiv3\pmod 4$, all of them rotations of each other. The argument is self-contained and yields a new proof of the value of the independence number.
- comments
- 12 pages, 1 figure
- fields
- Combinatorics