Structure connectivity and substructure connectivity of the directed k-ary n-cube. Issue 6 (2nd November 2022) - Wang, Yu; Meng, Jixiang
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 .