Condition Structure And Substructure Connectivity Of Balanced Hypercubes

The n dimensional balanced hypercube BHn has attracted extensive attention and research because of its good properties such as bipartition,vertices symmetry,edge transitive and struc-tural hierarchy and so on.Given a simple graph G,let H be a subgraph of G.Let H(G,H)be a set of connected subgraphs of G,which are isomorphic to H,determine UT?H(G,H){all the sub-graph of T} as HS(G,H).Let F(?)H(G,H),F is an H conditional structure cut of G if and only if G-F is disconnected.If the H conditional structure cut of G is exist,then the H conditional structure connectivity ?s(G,H)of G is the minimum cardinality of H conditional structure cut.If the H conditional structure cut of G doesn't exist,we defined the H conditional structure connectivity is +?.Let F(?)H(G,H),f is an H conditional substructure cut if and only if G-F is disconnected.If the H conditional substructure cut of G is exist,then the H conditional substructure connectivity ?s(G,H)of G is the cardinality of a minimum subset of H conditional substructure cut.If the H conditional substructure cut of G doesn't exist,we de-fined the H conditional substructure connectivity is +?.This paper we studied the conditional structure and substructure connectivity of balance hypercubes.The main contents are as follows.In chapter 1,we first briefly introduces the research background,research status,some basic concepts of graph theory and the definition and some properties of balance hypercubes.In chapter 2,we adopt the method of constructed K1,t conditional structure cut proved that[2n/t]is an upper bound of K1,t conditional structure connectivity.Then,we prove that deleted any substructure set in the balanced hypercubes of its cardinality does not exceed[2n/t]the balanced hypercube network is still connected.Therefore,[2n/t]also is a lower bound of K1,t conditional substructure connectivity.And because the property that the conditional substructure connectivity of the balanced hypercubes is not exceed the conditional structure connectivity,we get ?(BHn;K1,t)=?s(BHn;K1,t)=[2n/t],for n? 2,1?k?2nIn chapter 3,we adopt a similar method in chapter 2 of get a equal upper bound and lower bound to proved that(1).?(BHn;Pk)=?s(BHn;Pk)=[2n/[(k+1)/22]],for n?2,3?k?7,and there Pk is a path length of k.(2).?(BHn;C4)=?s(BHn;C4)=n,for n?2,and there C4 is a cycle length of 4.