کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654847 1632833 2007 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Perfect packings with complete graphs minus an edge
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Perfect packings with complete graphs minus an edge
چکیده انگلیسی

Let Kr− denote the graph obtained from KrKr by deleting one edge. We show that for every integer r≥4r≥4 there exists an integer n0=n0(r)n0=n0(r) such that every graph GG whose order n≥n0n≥n0 is divisible by rr and whose minimum degree is at least (1−1/χcr(Kr−))n contains a perfect Kr−-packing, i.e. a collection of disjoint copies of Kr− which covers all vertices of GG. Here χcr(Kr−)=r(r−2)r−1 is the critical chromatic number of Kr−. The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large nn.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 28, Issue 8, November 2007, Pages 2143–2155
نویسندگان
, , ,