Structure and substructure connectivity of circulant graphs and hypercubes
T. Tamizh Chelvam, M. Sivagami · Arab Journal of Mathematical Sciences · 2019
Let H be a connected subgraph of a connected graph G. The H -structure connectivity of the graph G , denoted by κ(G;H), is the minimum cardinality of a minimal set of subgraphs F={H1′,H2′,…,Hm′} in G , such that every H′i∈F is isomorphic to H and removal of F from G will disconnect G . The H -substructure connectivity of the graph G , denoted by κs(G;H), is the minimum cardinality of a minimal set of subgraphs F={J1′,J2′,…,Jm′} in G , such that every Ji′∈F is a connected subgraph of H and removal of F from G will disconnect G. In this paper, we provide the H -structure and the H -substructure connectivity of the circulant graph Cir (n,Ω) where Ω={1,…,k,n−k,…,n−1},1≤k≤⌊n2⌋ and the hypercube Qn for some connected subgraphs H.