کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649665 1342462 2009 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On cyclic edge-connectivity of transitive graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On cyclic edge-connectivity of transitive graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4555–4563
نویسندگان
, ,