| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649665 | Discrete Mathematics | 2009 | 9 Pages |
A cyclic edge-cut of a graph GG is an edge set, the removal of which separates two cycles. If GG has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph GG, the cyclic edge-connectivity cλ(G)cλ(G) is the cardinality of a minimum cyclic edge-cut of GG. In this paper, we first prove that for any cyclically separable graph GG, cλ(G)≤ζ(G)=min{ω(X)∣Xinduces a shortest cycle inG}, where ω(X)ω(X) is the number of edges with one end in XX and the other end in V(G)∖XV(G)∖X. A cyclically separable graph GG with cλ(G)=ζ(G)cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected kk-regular vertex-transitive graph with k≥4k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal.
