The Study On Generalized Connectivity And Related Problems Of Networks

The topological structure of an interconnection network is usually represented by a graph,where vertices represent processors and edges represent communication links between processors.Connectivity is an important parameter to evaluate the reliability of an interconnection network.However,with the development of large scale network,traditional connectivity always underestimates the resilience of the network.To over-come the shortcomings of traditional connectivity,relevant scholars generalized the traditional connectivity and introduced the concepts of generalized connectivity,com-ponent connectivity and good neighbor connectivity et al.In the thesis,the generalized3,4-connectivity,the g-component connectivity and the g-good neighbor connectivity of some kinds of interconnection networks are studied.The thesis is organized as follows:In Chapter 1,the research background and research status are introduced firstly,then the main results of this thesis are introduced.In Chapter 2,the definitions,notations and basic lemmas needed in this thesis are introduced.In Chapter 3,the generalized 3-connectivity of（n,k）-star graph S_n,kand（n,k）-bubble-sort graph B_n,kare studied.As S _n,k S _nand B_n,k B_nfor k=n-1,the known results[Appl.Math.Comput.,2016,274:41–46]about the generalized 3-connectivity of star graph S _nand bubble-sort graph B_nare generalized.In Chapter 4,three families of regular graphs with each family having common properties are defined,and the generalized 3-connectivity of them under some restricted conditions are determined.Assume the n-dimensional regular graph N_nis constructed recursively by p_n（n-1）-dimensional regular graph N¹_n-1,N²_n-1,...,N^pn_n-1.For each vertex v∈V(Nⁱ_n-1),the neighbor of v which is not in Nⁱ_n-1is called the outside neighbor of v,where 1≤i≤p_n.The first family of n-dimensional regular graph is represented by L_nand any vertex of it has exactly one outside neighbor.In section 4.1,the generalized 3-connectivity of L_nunder some restricted conditions is obtained.As corollaries of the result,the generalized 3-connectivity of the alternating group network AN_n,pancake graph P_nand the star graph S _netc.can be obtained directly.The second family of n-dimensional regular graph is represented by G_nand any vertex of G_nhas exactly two outside neighbors.In section 4.2,the generalized 3-connectivity of G_nunder some restricted conditions is determined.As corollaries of the result,the generalized 3-connectivity of the alternating group graph AG_n,bubble-sort-star graph BS _n,split-star graph S_n²and k-ary n-cube Q_n^ketc.can be obtained directly.The third family of regular graph is represented by H_n,it is a connected graph that obtained by n k-regular and k-connected graphs I₁,I₂,...,I_nwith the same order and there is a perfect matching between any two distinct I_iand I _jin H_n[V（I_i∪I _j）],where1≤i≤n and 1≤j≤n.In section 4.3,the generalized 3-connectivity of H_nunder some restricted conditions is determined.As corollaries of the result,the generalized3-connectivity of the Cayley graph CT_ngenerated by complete graph K_nand the Cayley graph WG_ngenerated by wheel graph W_ncan be obtained directly.In Chapter 5,the generalized 4-connectivity of networks are mainly studied.First-ly,the generalized 4-connectivity of the exchanged hypercube EH（s,t）is studied.Sec-ondly,the generalized 4-connectivity of the hierarchical cubic network HCN_nis de-rived.Finally,the generalized 4-connectivity of the line graph L(K_m,n)of the complete bipartite graph K_m,nand total graph T(K_m,m)of the regular complete bipartite graph K_m,mare studied,respectively,which improves the known results[Appl.Math.Com-put.,2019,347:645-652]regarding to the generalized 3-connectivity of L(K_m,n)and T（Km,m）.In Chapter 6,the g-component connectivity and g-good neighbor connectivity of some families of networks are studied.Firstly,the 3-component connectivity of the Cayley graphΓ_ngenerated by trees is studied.As corollaries,the 3-component connec-tivity of the star graph S _nand the bubble-sort graph B_ncan be obtained directly.In addi-tion,the g-component connectivity of the dual cube D_nis studied,where 2≤g≤n.At last,the g-good neighbor connectivity of hierarchical hypercube network is determined,where 1≤g≤m-1 and n=2^m+m.In Chapter 7,the main results of this thesis are concluded and some problems that might be further studied are introduced.