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

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22830
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Luis Manuel Rivera
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

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

Luis Manuel Rivera
preprint en

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.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon