2025/06/30 by S. A. Kandekar, Kandekar, S. A., R. Barabde +3
Computer Science · #Interconnection Networks and Systems #Advanced Graph Theory Research #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.2506.24071
Connectivity is a cornerstone concept in graph theory, essential for evaluating the robustness of networks against failures. To better capture fault tolerance in complex systems, researchers have extended classical connectivity notions, one such extension being the k-path-connectivity, πk(G), introduced by Hager. Given a connected simple graph G = (V, E) and a subset D ⊆ V with |D| ≥ 2, a D-path is a path that includes all vertices in D. A collection of such paths is internally disjoint if they intersect only at the vertices of D and share no edges. The maximum number of internally disjoint D-paths in G is denoted πG(D), and the k-path-connectivity is defined as πk(G) = min \ πG(D) | D ⊆ V(G), |D| = k\. In this paper, we investigate the 3-path-connectivity of the augmented cube AQn, a variant of the hypercube known for its enhanced symmetry and fault-tolerant structure. We establish the exact value of π3(AQn) and show that: π3(AQn) = \begincases (3n)/(2) - 2, amp; if n is even, (3(n - 1))/(2) - 1, amp; if n is odd. \endcases