کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650693 1342498 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge degrees and dominating cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Edge degrees and dominating cycles
چکیده انگلیسی

The edge degree d(e)d(e) of the edge e=uve=uv is defined as the number of neighbours of e  , i.e., |N(u)∪N(v)|-2|N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G  , if d(e1)+d(e2)>|V(G)|-4d(e1)+d(e2)>|V(G)|-4 for any remote edges e1,e2e1,e2, then all longest cycles C in G   are dominating, i.e., G-V(C)G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G   is a 2-connected triangle-free graph with σ2(G)>|V(G)|/2σ2(G)>|V(G)|/2, then all longest cycles are dominating.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 12, 28 June 2008, Pages 2594–2599
نویسندگان
,