On Edge Connectedness Of Graphs With Two Orbits

In recent years,with the rapid development of networks, the network per-formance comes into focus. The topology of a network is very important toin?uence the network performance. When designing the underlying topologyof a multiprocessor network, what we care about most are the reliability of thenetwork, that is, the ability of the network to function even when some verticesand/or edges fail. The underlying topology of a multiprocessor network is oftenmodeled as a graph, and so some classical notions of graph theory, such as theconnectivity and the edge-connectivity, are utilized to measure the reliabilityof the corresponding networks. For further study, many variations have beenintroduced, which are known as higher connectedness, such as super-λ(super-κ), hyper-λ(hyper-κ),restricted edge connectivity and super-restricted edgeconnectedness etc. In this paper, we mainly study the arc connectedness ofregular digraphs with two orbits and the super edge connectedness of regulargraphs with two orbits.In Chapter 1, we introduce the background of our study and some no-tations, and recall known results on various kinds of edge connectivity. InChapter 2, we study the arc connectedness of regular digraphs with two or-bits. We prove the existence of k-regular m-arc-connected digraphs with twoorbits for given integers k and m (1 < m k), and present a su?cient con-dition for a connected regular digraphs with two orbits to be maximally arcconnected. In Chapter 3, we study the super edge connectedness of regulargraphs with two orbits, we show that a connected k-regular graph G with twoorbits, satisfying girth g(G) 6, is super-λ.