Applied Sciences, Vol. 15, Pages 13166: The One-Fault Directed Dimension-Balanced Hamiltonian Problem in Directed Toroidal Mesh Graphs

Applied Sciences doi: 10.3390/app152413166

Authors:
Yancy Yu-Chen Chang
Justie Su-Tzu Juan

Hamiltonian cycle problems play a central role in graph theory and have wide-ranging applications in network-on-chip architectures, interconnection networks, and large-scale parallel systems. When a network contains faulty nodes or faulty links, the feasibility of certain paths becomes restricted, making the construction of Hamiltonian cycles substantially more difficult and increasingly important for ensuring reliable communication. A dimension-balanced Hamiltonian cycle is a special type of cycle that maintains an even distribution of edges across multiple dimensions of a network. Its directed counterpart extends this idea to symmetric directed networks by balancing the number of edges used in each positive and negative direction. Such cycles are desirable because they support uniform traffic distribution and reduce communication contention in practical systems. Previous research has examined the existence of directed dimension-balanced Hamiltonian cycles in directed toroidal mesh networks and has shown that some configurations permit directed dimension-balanced Hamiltonian cycles while others do not. Building on this foundation, this paper investigates the fault-tolerant properties of such networks by analyzing whether directed dimension-balanced Hamiltonian cycles still exist when a single vertex (node) or a single edge (link) is faulty. Our results extend the current understanding of Hamiltonian robustness in symmetric directed networks.

Source link

Yancy Yu-Chen Chang www.mdpi.com