The 3-Path Connectivity of Dragonfly Networks

Dragonfly networks D(n,h) are a class of interconnection topologies widely used for large-scale high-performance computing (HPC) systems. In such networks, path connectivity serves as a fundamental metric for evaluating fault tolerance and operational reliability. Let G be a connected simple graph with vertex set V(G). Let Ω be a subset of V(G) with cardinality at least two. A path containing all vertices of Ω is said to be an Ω-path of G. Two paths (T1 and T2) of G are internally disjoint if V(T1)∩V(T2)=Ω and E(T1)∩E(T2)=∅. For an integer with 2≤ℓ, the ℓ-path connectivity πℓ(G) is defined as πℓ(G)=min{πG(Ω)|Ω⊆V(G)and|Ω|=ℓ}, where πG(Ω) represents the maximum number of internally disjoint Ω-paths. This paper focuses on resolving the exact value of 3-path connectivity of dragonfly networks, π3(D(n,h)), defined as the maximum number of internally disjoint paths among any three distinct vertices in D(n,h). For D(n,h) with n≥5 and h≥2, the exact 3-path connectivity is π3(D(n,h))=⌊3h+2n4⌋ if h≤n−2, and π3(D(n,h))=⌊3n+2h−24⌋ if h≥n−1.