An Ordering on the Even Discrete Torus (Q4388982)

The authors consider the graph \(T=T(k_1,\dots,k_n)\) represented as the Cartesian product of cycles of even lengths \(k_1,\dots,k_n\). For a set \(A\) of vertices of \(T\) let \(N(A)\) denote the vertex boundary of \(A\), i.e. the set \(\{x : \text{dist}(x,A)\leq 1\}\). The problem is to a find a set \(A\) of a given size that has minimum boundary. It is shown that there exists a total ordering of vertices of the torus so that any initial segment of this ordering forms a set with minimum boundary. A similar result was proved by \textit{V. M. Karakhanyan} and published in ``A discrete isoperimetric problem on multidimensional torus'' (in Russian), Dokl. Akad. Nauk Arm. SSR 74, No. 2, 61-65 (1992; Zbl 0499.05010). It turns out that the claim concerning the parity of the cycle lengths is essential, since otherwise no total order with the mentioned property exists in general.