کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649707 | 1342464 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Clique partitions of complements of forests and bounded degree graphs
ترجمه فارسی عنوان
پارتیشن های دسته از مکمل های نمودارهای جنگل و درجه محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پارتیشن های کلاسیک؛ سیستم های Steiner؛ روش احتمالی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In this paper, we prove that for any forest F⊂KnF⊂Kn, the edges of E(Kn)⧹E(F)E(Kn)⧹E(F) can be partitioned into O(nlogn)O(nlogn) cliques. This extends earlier results on clique partitions of the complement of a perfect matching and of a hamiltonian path in KnKn.In the second part of the paper, we show that for n sufficiently large and any ε∈(0,1]ε∈(0,1], if a graph G has maximum degree O(n1-ε)O(n1-ε), then the edges of E(Kn)⧹E(G)E(Kn)⧹E(G) can be partitioned into O(n2-(1/2)εlog2n) cliques provided there exist certain Steiner systems. Furthermore, we show that there are such graphs G for which Ω(ε2n2-2ε)Ω(ε2n2-2ε) cliques are required in every clique partition of E(Kn)⧹E(G)E(Kn)⧹E(G).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 10, 28 May 2008, Pages 2011–2017
Journal: Discrete Mathematics - Volume 308, Issue 10, 28 May 2008, Pages 2011–2017
نویسندگان
Michael Cavers, Jacques Verstraëte,