کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419003 681731 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
kk-restricted edge connectivity in (p+1)(p+1)-clique-free graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
kk-restricted edge connectivity in (p+1)(p+1)-clique-free graphs
چکیده انگلیسی

Let GG be a graph with vertex set V(G)V(G) and edge set E(G)E(G). An edge subset S⊆E(G)S⊆E(G) is called a kk-restricted edge cut if G−SG−S is not connected and every component of G−SG−S has at least kk vertices. The kk-restricted edge connectivity of a connected graph GG, denoted by λk(G)λk(G), is defined as the cardinality of a minimum kk-restricted edge cut. Let [X,X̄] denote the set of edges between a vertex set X⊂V(G)X⊂V(G) and its complement X̄=V(G)∖X. A vertex set X⊂V(G)X⊂V(G) is called a λkλk-fragment if [X,X̄] is a minimum kk-restricted edge cut of GG. Let ξk(G)=min{|[X,X̄]|:|X|=k,G[X]is connected}. In this work, we give a lower bound on the cardinality of λkλk-fragments of a graph GG satisfying λk(G)<ξk(G)λk(G)<ξk(G) and containing no (p+1)(p+1)-cliques. As a consequence of this result, we show a sufficient condition for a graph GG with λk(G)=ξk(G)λk(G)=ξk(G).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 181, 30 January 2015, Pages 255–259
نویسندگان
, , ,