کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648287 | 1342404 | 2012 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the minimum number of edges of two-connected graphs with given diameter
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We answer the following question: what is the minimum number of edges of a 2-connected graph with a given diameter? This problem stems from survivable telecommunication network design with grade-of-service constraints. In this paper, we prove tight bounds for 2-connected graphs and for 2-edge-connected graphs. The bound for 2-connected graphs was a conjecture of B. Bollobás (AMH 75–80) [3].
► We introduce the notion of peri-eccentricity which relates the trail decomposition of lobes to the diameter a graph.
► We give a tight minimum bound for the number of edges of a 2-connected graph with given diameter.
► We prove a tight minimum bound for the number of edges of a 2-edge-connected graph with given diameter.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 4, 28 February 2012, Pages 757–762
Journal: Discrete Mathematics - Volume 312, Issue 4, 28 February 2012, Pages 757–762
نویسندگان
A. Jarry, A. Laugier,