Restricted Connectivity Of Line Digraphs And Cartesian Product Digrphs

With the rapid development of information networks, many theoretical problems come into focus, one of which is the reliability of the network, that is, the ability of the network to function even when some vertices and edges fail. The underlying topology of a network is often modeled as a graph or a digraph. So, some classical parameters of graph theory, such as the connectivity and the edge-connectivity, are utilized to measure the reliability of networks. These concepts have been generalized to many kinds of connectiv-ities. There are a lot of works on restricted connectivities in undirected graphs. However, works on digraphs in this aspect are relatively much less. In this thesis, we study the restricted connectivity of line digraphs and cyclic arc-connectivity of Cartesian product digraphs.This thesis is divided into three chapters. In Chapter 1, we introduce the background of our study and some notation. Then we state the main results in this thesis. In Chapter 2, we propose a new kind ofκ-restricted connectivity for digraphs, and study the relationship between the restricted arc-connectivity of digraph D and the restricted vertex-connectivity of it line digraph L(D). Under our definition, this relationship is very neat, which shows that our definition of restricted connectivity is more reasonable than previous ones. The concept of cyclic arc-connectivity is a special use of our restricted arc-connectivity. In Chapter 3, We give a necessary and sufficient condition for Cartesian product digraph D1×D2 to be cycle separable, and when D1×D2 is strongly connected, we give an upper bound and a lower bound for the cyclic arc-connectivityλc(D). Finally, it can be determined thatλc(Cn1×Cn2×…×Cnk)=(k-1)min{n1,n2,…,nk}, where Cni is a directed cycle of length ni.