One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph

Given a graph G = (V, E), the edge set can be partitioned into k dimensions, for a positive integer k. The set of all i-dimensional edges of G is a subset of E(G) denoted by Ei. A Hamiltonian cycle C on G contains all vertices on G. Let Ei(C) = E(C) ∩ Ei. For any 1 ≤ i ≤ k, C is called a dimension-balanced Hamiltonian cycle (DBH, for short) on G if ||Ei(C)| − |Ej(C)|| ≤ 1 for all 1 ≤ i < j ≤ k. The dimension-balanced cycle problem is generated with the 3-D scanning problem. Graph G is called p-node q-edge dimension-balanced Hamiltonian (p-node q-edge DBH) if it has a DBH after removing any p nodes and any q edges. G is called h-fault dimension-balanced Hamiltonian (h-fault DBH, for short) if it remains Hamiltonian after removing any h node and/or edges. The design for the network-on-chip (NoC) problem is important. One of the most famous NoC is the toroidal mesh graph Tm,n. The DBC problem on toroidal mesh graph Tm,n is appropriate for designing simple algorithms with low communication costs and avoiding congestion. Recently, the problem of a one-fault DBH on Tm,n has been studied. This paper solves the one-node one-edge DBH problem in the two-fault DBH problem on Tm,n.