کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423446 1342375 2012 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sparse graphs of girth at least five are packable
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Sparse graphs of girth at least five are packable
چکیده انگلیسی

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph G with girth at least 5 is packable.The conjecture was proved by Faudree et al. with the additional condition that G has at most 65n−2 edges. In this paper, for each integer k≥3, we prove that every non-star graph with girth at least 5 and at most 2k−1kn−αk(n) edges is packable, where αk(n) is o(n) for every k. This implies that the conjecture is true for sufficiently large planar graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 24, 28 December 2012, Pages 3606-3613
نویسندگان
, ,