The Generalized 3-Connectivity Of Cayley Graphs

Computer networks are usually modelled by a connected graphs,where vertices represent processors and edges represent connections between processors.Therefore,the performances of a network can be measured by the parameters of a graph.Although classical connectivity is one of the important parameters to measure the fault tolerance of networks,it does not accurately measure the fault tolerance of large networks.In order to improve the classical connectivity,many scholars have promoted the classical connectivity.This paper focuses on one of the promotion-the generalized k-connectivity.Let G be a connected graph of order n and let k be an inter with 2?k?n.Let S(?)V(G),a tree T in Gis called an S-tree,if S(?)V(T).A collection {T1,T2,...,Tr } of S-trees in G is called internally disjoint,if E(Ti)? E(Tj)=(?)and V(Ti)?V(Tj)= S,where 1?i?j?r.Let ?G(S)denote the maximum number of internally disjoint S-trees.The generalized k-connectivity of G,denoted by ?k(G),where ?k(G)= min{?G(S)|S(?)V(G),and|S|= k}.Obviously,the generalized 2-connectivity ?2(G)of G is exactly ?(G).In recent years,the genera.lized connectivity has attracted the attention of many scholars and proved that it is NP-complete problem for a general graph G to decide whether there are k disjoint S-trees,where k ia a fixed int,eger and S(?)V(G).This paper is divided into two chapters.In addition to the introduction,Chap-ter 2 studies the Cayley graph generated by the complete graph CTn,t,he Cayley graph generated by the wheel graph WGn,and the Cayley graph generated by tri-angle tower TTn these three types of graphs,and their generalized 3-connectivity,the results are as follows:?3(CTn)=n(n-1)/2-1,where n?3;?3(W Gn)= 2n-3,where n?4;?3(TTn)= 2n-4,where n?3.