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.