Analysis On Problems Related With Trees And Cycles Of Some Networks

In recent years,the reliability analysis based on the connectivity of networks has attracted the attention of the network researchers.Although traditional connectivity can be used to assess the strength of the connection between two nodes,however,such measure is inadequate for evaluating the connectivity among a set of multiple nodes in a network.The generalized connectivity as one kind of generalization of the connectivity can effectively solve the above problem.Let S(?)V(G),?_G(S)denote the maximum number r of S-trees T₁,T₂,···,T_rin G such that V(T_i)?V(T _j)=S and E(T_i)?E(T _j)=(?)for any i,j?{1,2,···,r}and i j.These S-trees are called internally disjoint S-trees.The generalized k-connectivity of graph G is defined as?_k(G)=min{?_G(S)|S(?)V(G)and|S|=k}for k?2.In addition,in the design and analysis of the network,an important issue is its graph embedding ability.Cycles are one of the most basic structures of parallel and distributed computing.How to embed multiple cycles into the network is an important research content.Among them,the k-disjoint cycle cover of a graph G refers to embedding k disjoint cycles into the graph G and cover all the vertices of G.This thesis studies the generalized connectivity problem based on the tree structure and the two disjoint cycle cover problem based on the cycle structure.First,combining the mathematical inductive method and classified discussion according to the random distribution of faulty vertices,this thesis studies the generalized 3-connectivity of n-dimensional balanced hypercube BH_nand n-dimensional augmented cube AQ_n,respec-tively.Next,it is also proved that there exists two-disjoint-cycle-cover bipancyclicity of n-dimensional balanced hypercube BH_n.This thesis is organized as follows.Chapter 1 is the introduction.We introduce basic definitions and preliminaries related to this thesis and give the background of the generalized connectivity and two-disjoint-cycle-cover bipancyclicity,the definitions of networks used in the thesis and the main works of this thesis.In Chapter 2,the related conclusions of generalized connectivity and n-dimensional balanced hypercubes BH_nare first given.Then based on the structural characteristics and properties of BH_n,we prove that the generalized 3-connectivity of BH_nis 2n-1for n?1.In Chapter 3,the related properties of n-dimensional augmented cubes AQ_nare first given,and then it is proved that the generalized 3-connectivity of AQ_nis 4,5,8for n=3,4,5,respectively,and finally it is proved that the generalized 3-connectivity of AQ_nis 2n-2 for n?6.In Chapter 4,based on the structural properties of BH_n,the existence of two-disjoint-cycle-cover[4,2^2n-1]-bipancyclicity of BH_nis proved for n?2.This result improves the known results about Hamiltonicity and bipancyclicity for the length of the cycle with 4??2²ⁿ-4 in BH_n.In Chapter 5,we summarize the thesis and give further research directions.