کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418686 | 681709 | 2014 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A bound for judicious kk-partitions of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A bound for judicious kk-partitions of graphs A bound for judicious kk-partitions of graphs](/preview/png/418686.png)
چکیده انگلیسی
Judicious Partition Problem is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let kk be a positive integer and GG a graph with mm edges. It is proved in this paper that the vertex set of GG can be partitioned into kk parts V1,…,VkV1,…,Vk such that e(Vi)≤mk2+k−12k2(2m+14−12)+23 for each i∈{1,2,…,k}i∈{1,2,…,k} and e(V1,…,Vk)≥k−1km+k−12k(2m+14−12)−(k−2)28k, where e(Vi)e(Vi) is the number of edges with both ends in ViVi and e(V1,…,Vk)=m−∑i=1ke(Vi). This partially solves a problem proposed by Bollobás and Scott, and, for some values of mm, solves the problem affirmatively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 179, 31 December 2014, Pages 86–99
Journal: Discrete Applied Mathematics - Volume 179, 31 December 2014, Pages 86–99
نویسندگان
Genghua Fan, Jianfeng Hou, Qinghou Zeng,