کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872552 | 681651 | 2014 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the structure of arbitrarily partitionable graphs with given connectivity
ترجمه فارسی عنوان
در ساختار گرافهای اختیاری با اتصال داده شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار، اختیاری پارتیشن بندی اتصال
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A graph G=(V,E) is arbitrarily partitionable if for any sequence Ï of positive integers adding up to |V|, there is a sequence of vertex-disjoint subsets of V whose orders are given by Ï, and which induce connected subgraphs. Such a graph models, e.g., a computer network which may be arbitrarily partitioned into connected subnetworks. In this paper we study the structure of such graphs and prove that unlike in some related problems, arbitrarily partitionable graphs may have arbitrarily many components after removing a cutset of a given size â¥2. The sizes of these components grow exponentially, though.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 381-385
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 381-385
نویسندگان
Olivier Baudon, Florent Foucaud, Jakub PrzybyÅo, Mariusz Woźniak,