Connectivity Of Graphs With Two Edge Orbits

With the rapid development of information networks, many of the related theoreticalproblems come into focus, one of which is the reliability of the network, that is, the abilityof the network to function even when some vertices and/or edges fail. The underlyingtopology of a network is often modeled as a graph. Therefore, some classical notions ofgraph theory, such as the connectivity and the edge-connectivity, are utilized to measurethe reliability of networks.Let G be a connected graph with two edge orbits, E₁ and E₂ be its edge orbitsunder the action of Aut(G) on E(G). Let G₁ = G[E₁] and G₂ = G[E₂], which are calledthe edge transitive parts of G. then we say that G is an 2-edge-orbit graph. In thispaper, we mainly study the vertex connectedness of 2-edge-orbit graph and the the vertexconnectedness of 2-arc-orbit digraph.This thesis is divided into four chapters. In Chapter 1, we introduce the backgroundof our study, and recall the study of connectivity of transitive graph. In Chapter 2, Westudy the vertex connectivity of 2-edge-orbit graph. For II-kind and III-kind 2-edge-orbitgraph, we give some su?cient conditions such that the vertex connectivity is equal to itsminimum degree. In Chapter 3, we show that the vertex connectivity of a connected k(≤6)-regular 2-edge-orbit graph with girth g(G)≥8 is its minimum degree. In Chapter 4,we study the vertex connectedness of 2-arc-orbit digraph, and it is proved that the vertexconnectivity of a strongly connected 2-arc-orbit digraph D with girth g(D)≥(δ(D)-1)/(δ(D_i)) + 1is its minimum degree.