کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331949 | 686992 | 2005 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sufficient conditions for λâ²-optimality of graphs with small conditional diameter
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A restricted edge-cut S of a connected graph G is an edge-cut such that GâS has no isolated vertex. The restricted edge-connectivity λâ²(G) is the minimum cardinality over all restricted edge-cuts. A graph is said to be λâ²-optimal if λâ²(G)=ξ(G), where ξ(G) denotes the minimum edge-degree of G defined as ξ(G)=min{d(u)+d(v)â2:uvâE(G)}. The P-diameter of G measures how far apart a pair of subgraphs satisfying a given property P can be, and hence it generalizes the standard concept of diameter. In this paper we prove two kind of results, according to which property P is chosen. First, let D1 (resp. D2) be the P-diameter where P is the property that the corresponding subgraphs have minimum degree at least one (resp. two). We prove that a graph with odd girth g is λâ²-optimal if D1⩽gâ2 and D2⩽gâ5. For even girth we obtain a similar result. Second, let FâV(G) with |F|=δâ1, δ⩾2, being the minimum degree of G. Using the property Q of being vertices of GâF we prove that a graph with girth gâ{4,6,8} is λâ²-optimal if this Q-diameter is at most 2â(gâ3)/2â.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 95, Issue 4, 31 August 2005, Pages 429-434
Journal: Information Processing Letters - Volume 95, Issue 4, 31 August 2005, Pages 429-434
نویسندگان
C. Balbuena, M. Cera, A. Diánez, P. GarcÃa-Vázquez, X. Marcote,