Structure connectivity and substructure connectivity of the directed k-ary n-cube. Issue 6 (2nd November 2022)

• Record Type: Journal Article
• Authors: Wang, Yu; Meng, Jixiang
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 37:Issue 6(2022)
• Page Start: 649
• Page End: 658
• Publication Date: 2022-11-02
• Subjects: Structure connectivity -- Substructure connectivity -- Directed k-ary n-cube -- Directed star; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2022.2110592
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : Given a strongly connected digraph D and a connected subdigraph T of D, the T -structure connectivity κ ( D ; T ) of D is the cardinality of a minimum set of subdigraphs F = { T 1, T 2, …, T m } in D, whose removal results in a non-strongly connected digraph and T i ≅ T ( 1 ≤ i ≤ m ) . The T -substructure connectivity κ s ( D ; T ) of D is the cardinality of a minimum set of subdigraphs F = { T 1, T 2, …, T m } in D, whose removal results in a non-strongly connected digraph and each element T i ( 1 ≤ i ≤ m ) is isomorphic to a connected subdigraph of T . In this work, we study κ ( D n k ; K 1, t ← ) ( resp. κ s ( D n k ; K 1, t ← ) ) for k ≥ 3, n ≥ 2 and 1 ≤ t < m i n { n, 2 k − 1 } ; κ ( D n k ; P t → ) ( resp. κ s ( D n k ; P t → ) ) for k ≥ 3 and n ≥ 2 ; and κ ( D n k ; C t → ) ( resp. κ s ( D n k ; C t → ) ) for k ≥ 3, n ≥ 3, and n ≠ t + 1, where D n k is the directed k -ary n -cube, K 1, t ← is the in-star on t + 1 vertices, P t → and C t → are, respectively, the directed path and cycle of length t .