Connectivity code of torus graphs C_t × C_s
Open Problem: m(C_t × C_s) for all t, s · arXiv:2308.07653
Status open high confidence
The problem of determining $m(C_t \times C_s)$ for all $t, s$ was posed in Alon's paper arXiv:2308.07653 (published in Random Structures & Algorithms 65, 2024). The paper establishes the partial result $m(C_3 \times C_s) \leq 8$ for all $s > 36$, and notes that $m(C_3 \times C_3) = 16$. No subsequent paper resolving the full problem was found in a broad web search across arXiv and journal databases.
Reviewer notes. The source paper was published in Random Structures & Algorithms (2024, vol. 65, no. 3, pp. 451-459). The open problem asks for the exact value of $m(C_t \times C_s)$ for all pairs $t, s$; the only known result in the paper beyond $m(C_3 \times C_3) = 16$ is the upper bound $m(C_3 \times C_s) \leq 8$ for $s > 36$. Five web searches and fetches found no follow-up paper resolving or substantially advancing the general problem.
Context
Proposition 3.2 establishes that $m(C_3 \times C_s) \leq 8$ for all $s > 36$ (since $K_3 = C_3$), answering a question raised in [6] about whether the connectivity code for large tori is strictly smaller than the trivial edge-connectivity bound $2^4 = 16$. The paper explicitly notes that the broader problem of determining $m(C_t \times C_s)$ for all $t$ and $s$ remains open.
Notes. PDF source; $\times$ denotes the Cartesian (box) product of graphs. The special case $t=3$ ($K_3=C_3$) is resolved by Proposition 3.2; all other cases remain open.
Source paper
Connectivity Graph-Codes
Noga Alon · 2023-09-06
https://arxiv.org/abs/2308.07653
PDF source