Structure connectivity and substructure connectivity of star graphs.

The connectivity is an important measurement for the fault-tolerance of networks. The structure connectivity and substructure connectivity are two generalizations of the classical connectivity. For a fixed graph H , a set F of subgraphs of G is called an H -structure cut (resp., H -substructure cut) of G , if G − ∪ F ∈ F V (F) is disconnected and every element of F is isomorphic to H (resp., a connected subgraph of H). The H -structure connectivity (resp., H -substructure connectivity) of G , denoted by κ (G ; H) (resp., κ s (G ; H)), is the cardinality of a minimal H -structure cut (resp., H -substructure cut) of G. In this paper, we will establish both κ (S n ; H) and κ s (S n , H) for every H ∈ { K 1 , K 1 , 1 , K 1 , 2 , ... , K 1 , n − 2 , P 4 , P 5 , C 6 } , where S n is the n -dimensional star graph. These results will show that star networks are highly tolerant of structure faults. [ABSTRACT FROM AUTHOR]