کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4649707 1342464 2017 7 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
Clique partitions of complements of forests and bounded degree graphs
ترجمه فارسی عنوان
پارتیشن های دسته از مکمل های نمودارهای جنگل و درجه محدود
کلمات کلیدی
پارتیشن های کلاسیک؛ سیستم های 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
نویسندگان
, ,