کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419841 683866 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The connectivity of a graph and its complement
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The connectivity of a graph and its complement
چکیده انگلیسی

Let GG be a graph with minimum degree δ(G)δ(G), edge-connectivity λ(G)λ(G), vertex-connectivity κ(G)κ(G), and let Ḡ be the complement of GG.In this article we prove that either λ(G)=δ(G)λ(G)=δ(G) or λ(Ḡ)=δ(Ḡ). In addition, we present the Nordhaus–Gaddum type result κ(G)+κ(Ḡ)≥min{δ(G),δ(Ḡ)}+1. A family of examples will show that this inequality is best possible.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 17, 28 October 2008, Pages 3325–3328
نویسندگان
, ,