Connectedness Of Some Kinds Of Graphs

In recent years,with the rapid development of information networks,the network comes into focus.The topology of information network is very important to influence the network performance.When designing the underlying topology of a multiprocessor network,what we care is the reliability of the network,that is,the ability of the network to function even when some vertices or edges fail.People often model the underlying topology of a multiprocessor network as a graph,hence,some classical notations of graph theory,such as the vertex connectivity and the edge connectivity,are utilized to measure the reliability of the corresponding networks.For further study,many new concepts of connectedness have been introduced,such as the super(edge)connectedness,the cyclic vertex(edge)connectivity,the restricted connectivity,etc.In this paper,we mainly study the cyclic edge connectivity of mixed Cayley graphs,the cyclic vertex connectivity and the restricted connectivity of Cartesian products,the cyclic vertex connectivity of minimal circulant graphs,and the connectivity of half vertex transitive digraphs.In Chapter 1,we introduce the background,some definitions,notations and termi-nology,and recall the study of the cyclic edge connectivity,the cyclic vertex connectivity,and the restricted connectivity.In Chapter 2,we study the cyclic edge connectivity of mixed Cayley graphs,and we describe a sufficient and necessary condition of cyclic edge optimal for mixed Cayley graphs.In Chapter 3,we characterize the cyclic vertex connec-tivity and the restricted connectivity of Cartesian products.For Cartesian products,we obtain an upper bound and a lower bound of the cyclic vertex connectivity,and research the 3-restricted connectivity and the 4-restricted connectivity,in the last,we give two con-jectures for ?>5 restricted connectivity of Cartesian products.In Chapter 4,we research the cyclic vertex connectivity of minimal circulant graphs,and for any minimal circulant graph X = C(Z_n,S)(n ? 12),we have ?_c(X)= g(?-2),where g is the girth,and ?(>2)is the regularity.In Chapter 5,we characterize the connectivity of digraphs,and we prove that the connectivity of half vertex transitive digraphs equals to the minimum degree.