Weakly Dimension-Balanced Hamiltonian Cycle on Three-Dimensional Toroidal Mesh Graph

The dimension-balanced cycle (DBC) problem is new in graph theory, with applications such as 3D stereogram reconstruction. In a graph whose edges are partitioned into k dimensions, a cycle is dimension-balanced if edge counts across dimensions differ by at most one. When such a cycle is Hamiltonian, it is called a dimension-balanced Hamiltonian cycle (DBH). Since DBHs do not always exist, a relaxed notion—the weakly dimension-balanced Hamiltonian (WDBH) cycle—was considered, allowing a difference of up to three. We prove that WDBH always exists in any 3-dimensional toroidal mesh graph Tm,n,r for all positive integers m, n, and r.