Two-Disjoint-Cycle-Cover Pancyclicity of Dragonfly Networks

Interconnection networks (often modeled as graphs) are critical for high-performance computing systems, as they have significant impact on performance metrics like latency and bandwidth. The dragonfly network, denoted as D(n,r), is a promising topology owing to its modularity, low diameter, and cost-effectiveness. Ensuring reliability and efficiency in these networks requires robust cycle embedding properties. The two-disjoint-cycle-cover pancyclicity ensures that the network can be partitioned into two vertex-disjoint cycles of any feasible length. This suggests potential advantages for improving fault tolerance and load balancing strategies in interconnection networks. Formally, a graph G is called two-disjoint-cycle-cover [a1,a2]-pancyclic if for any integer ℓ satisfying a1≤𝓁≤a2, there exist two vertex-disjoint cycles C1 and C2 in G such that |V(C1)|=𝓁 and |V(C2)|=|V(G)|−𝓁. While prior work has established Hamiltonicity and pancyclicity for D(n,r), the two-disjoint-cycle-cover problem remains unexplored. This paper fills this gap by proving that D(n,r) is two-disjoint-cycle-cover [3,|V(D(n,r))|2]-pancyclic with n≥3 and r≥2, generalizing existing knowledge. Moreover, it can be obtained that D(n,r) is vertex-disjoint-cycle-coverable. Our proof employs a constructive method with case analysis, ensuring the existence of such cycles.