کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650160 1342477 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sufficient conditions for super kk-restricted edge connectivity in graphs of diameter 2
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Sufficient conditions for super kk-restricted edge connectivity in graphs of diameter 2
چکیده انگلیسی

For a connected graph G=(V,E)G=(V,E), an edge set S⊆ES⊆E is a kk-restricted edge cut if G−SG−S is disconnected and every component of G−SG−S has at least kk vertices. The kk-restricted edge connectivity of GG, denoted by λk(G)λk(G), is defined as the cardinality of a minimum kk-restricted edge cut. Let ξk(G)=min{|[X,X¯]|:|X|=k,G[X]is connected}. GG is λkλk-optimal if λk(G)=ξk(G)λk(G)=ξk(G). Moreover, GG is super-λkλk if every minimum kk-restricted edge cut of GG isolates one connected subgraph of order kk. In this paper, we prove that if |NG(u)∩NG(v)|≥2k−1|NG(u)∩NG(v)|≥2k−1 for all pairs uu, vv of nonadjacent vertices, then GG is λkλk-optimal; and if |NG(u)∩NG(v)|≥2k|NG(u)∩NG(v)|≥2k for all pairs uu, vv of nonadjacent vertices, then GG is either super-λkλk or in a special class of graphs. In addition, for kk-isoperimetric edge connectivity, which is closely related with the concept of kk-restricted edge connectivity, we show similar results.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 4, 6 March 2009, Pages 908–919
نویسندگان
, , ,