The Generalized Connectivity Of Hypercube-like Networks

It is well known that interconnection networks play an important role in parallel and distributed computer systems.An interconnection network is usually modeled by a graph in which the vertices correspond to the processors and the edges correspond to the links between the processors.So properties of networks can be measured by the properties and parameters of the corresponding graphs.In the design and analysis of an interconnection network,one major concern is its fault-tolerance.The connectivity and the spanning tree packing number of a graph axe two important measurements for the fault-tolerance of a network.As a common generalization of the classical connectivity and spanning tree packing number,the generalized connectivity is a more refined index for the fault-tolerance of networks.Let G be a connected graph of order n and let k be an integer with 2<k<n.For a set S of k vertices of G,a tree T in G is called an S-tree,if S(?)V(T).Two S-trees T,T'are called internally disjoint i V(T)?V(T')= S and E(T)?E(T')=(?).Let k(S)denote the maximum number r of internally disjoint S-trees T1,T2,…,Tr in G.We define the generalized k-connectivity kk(G)= min?k(S):S(?)(?)V(G),|S|=k}.Over the past few years,the generalized connectivity has drawn much attention.In 2012,Li et al.proved that the generalized 3-connectivity of n-dimensional hypercube Qn is n-1.In this paper,we give the generalized 4-connectivity of Qn and prove that the above result is an immediate consequence of this result.In addition,we also determine the generalized 3-connectivity of the k-ary n-cube.This thesis consists of three chapters.In Chapter 1,after introducing the used basic concepts and notations,a brief intro-duction to the research background of the generalized connectivity and hypercubes are given.In Chapter 2,we introduce the concept and relevant properties of the hypercube Qn first,then we evaluate the generalized 4-connectivity of Qn and obtain the following results:(1)K4(Qn)= n-1.(2)The result K3(Qn)= n-1 can be derived immediately from k4(Qn)= n-1.In Chapter 3,after introducing the concept and relevant properties of the k-ary n-cube Qnk,we evaluate the generalized 3-connectivity of Qnk and prove that k3(Qnk),= 2n-1.