| A graph can be used to represent the topology of an interconnected network,where the vertices in the graph correspond to the processors of the network,and the edges correspond to the connections between the communication processors.As we all know,the connectivity is an important parameter for measuring the network reliability.The greater the connectivity,the greater the reliability of the network.The traditional connectivity of a graph is mainly used to measure the reliability of a network when data is transmitted between two terminal processors.In parallel and distributed computing,data often needs to be transmitted among a group of terminal processors,which requires a subnetwork connecting these processors.Obviously,the more independent subnetworks that connect these processors,the greater the probability that data can still be transmitted normally when some components in the computing system fail.Based on this consideration,Chartrand et al.proposed the concept of tree connectivity as an extension of the traditional connectivity.The tree connectivity of undirected graphs is a hot topic in this field.In 2022,the concept of tree connectivity of directed graphs was also proposed.Let D=（V,A）be a strongly connected digraph,S-(x;y1,y2,…,yk-1)be a partial ordered set consisting of k vertices in D,and T be a subgraph of D.If for any i = 1,2,…,k-1,there is an（x,yi）-path in T,then T is called an S-subgraph of D.If two S-subgraphs T1 and T2 of D satisfy V（T1）∩V（T2）={x,y1,y2,…yk-1} and E（T1）∩ E（T2）=（?）,then T1 and T2 are said to be two internally disjoint S-subgraphs.Use κ（S）to represent the maximum number of internally disjoint S-subgraphs in D.For an integer k ∈ {2,3,…,|V（G）|｝,define κk（D）=min{κ（S）:S is a k-ary partial ordered set of V（D）} to be the k set tree connectivity of D.The research on tree connectivity of directed graphs is just beginning.This thesis will be divided into four chapters to study the 3 set tree connectivity of unidirectional toruses,unidirectional hyper cubes,and directed Kautz graphs.In Chapter 1,we firstly introduce the basic concepts,research background,and research status of unidirectional torus networks,unidirectional hypercube networks,and directed Kautz networks.Secondly,the concept of tree connectivity of undirected graphs and the research status on the tree connectivity of some well-known undirected networks are introduced.Finally,the concept of tree connectivity of directed graphs is introduced.In Chapter 2,it is proved that if k1,k2≥ 3 and they are not 3 at the same time,then the 3 set tree connectivity of the unidirectional 2 dimensional torus （?）k1 × （?）k2 is 2.It is also shown that the 3-set tree connectivity of the unidirectional 2 dimensional torus （?）3 × （?）3 is 1.In Chapter 3,we introduce some properties of unidirectional hypercubes,and then show that the 3 set tree connectivity of the（2n-1）-dimensional unidirectional hypercube （?）2n-1 is n-1 and the 3 set tree connectivity of the 2n-dimensional unidirectional hyper cube （?）2n is at least n-1.An example is given to illustrate that this lower bound is tight in a sense.In Chapter 4,we introduce some properties of directed Kautz graphs,and then prove that the 3 set tree connectivity of the directed Kautz graph K（d,1）is d and the 3 set tree connectivity of the directed Kautz graph K（d,n）is d-1 for any d≥2,n≥ 2. |
