کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5776976 1413647 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded
ترجمه فارسی عنوان
حداکثر تعداد لبه ها در نمودارهای ناقص است که حداکثر درجه و تعداد تطبیق آنها محدود است
کلمات کلیدی
نمودار افقی لبه، نمودارهای بدون چنگال، حداکثر تطبیق نظریه رمزی،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We determine the maximum number of edges that a claw-free graph can have, when its maximum degree and matching number are bounded. This is a famous problem that has been studied on general graphs, and for which there is a tight bound. The graphs achieving this bound contain in most cases an induced copy of K1,3, the claw, which motivates studying the question on claw-free graphs. Note that on general graphs, if one of the mentioned parameters is not bounded, then there is no upper bound on the number of edges. We show that on claw-free graphs, bounding the matching number is sufficient for obtaining an upper bound on the number of edges. The same is not true for the degree, as a long path is claw-free. We give exact tight formulas for both when only the matching number is bounded and when both parameters are bounded. We also construct claw-free graphs whose edge numbers match the given bounds.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 5, May 2017, Pages 927-934
نویسندگان
, , ,