Paperlane

no. 17 · Wednesday 18 November 2026

Independent sets in the 2-token graph of a cycle and kings on the torus

Luis Manuel Rivera

math.CO · 12 pp

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
pdf ↗ page arXiv:2611.22830 ↗