On Cyclic Edge-connectivity Of Transitive Graphs

Let G be a simple connected graph.A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles.If G has a cyclic edge-cut,then it is said to be cyclically separable.For a cyclically separable graph G,the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G.Firstly,in this thesis we show an upper bound for cλ(G) of a cyclically separable graph G,that is,we have cλ(G)≤ζ(G)=min{ω(X) | X induces a shortest cycle in G}, whereω(X) is the number of edges with one end in X and the other end in V(G) \ X.A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. Secondly,we give a sufficient condition for the cyclic optimality of vertex- or edgetransitive graphs,that is:any connectedκ-regular vertex-transitive graph with k≥4 and girth at least five is cyclically optimal;any connected edge-transitive graph with minimum degree at least four and order at least six is cyclically optimal.We call a graph super cyclically edge-connected,if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle.Finally,we show that a connected vertex-transitive or edge-transitive graph is super cyclically edge-connected if either G has minimum degreeδ(G)≥4 and girth g(G)≥6,or G is cubic with girth g(G)≥7.