کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649665 | 1342462 | 2009 | 9 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4555–4563