Star structure connectivities of pancake graphs and burnt pancake graphs. Issue 5 (3rd September 2021)

• Record Type: Journal Article
• Authors: Dilixiati, Subinur; Sabir, Eminjan; Meng, Jixiang
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 36:Issue 5(2021)
• Page Start: 440
• Page End: 448
• Publication Date: 2021-09-03
• Subjects: Star-structure connectivity -- star-substructure connectivity -- pancake graphs -- burnt pancake graphs -- Fault tolerance; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2021.1941006
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : Let H be a connected subgraph of a graph G . The H -structure connectivity κ ( G ; H ) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to H . Similarly, the H -substructure connectivity κ s ( G ; H ) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of H . Structure connectivity and substructure connectivity generalise the classic connectivity. Let P n and B P n be the n -dimensional pancake graph and n -dimensional burnt pancake graph, respectively. In this paper we show κ ( P n ; K 1, t 1 ) = κ s ( P n ; K 1, t 1 ) = n − 1 ( 1 ≤ t 1 ≤ n − 2 ), and κ ( B P n ; K 1, t 2 ) = κ s ( B P n ; K 1, t 2 ) = n ( 1 ≤ t 2 ≤ n − 1 ) .