کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647604 | 1632426 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Induced matchings in subcubic graphs without short cycles
ترجمه فارسی عنوان
تطبیق در گرافهای زیرمجموعه ای بدون چرخه کوتاه باعث شده است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مطابقت القاء شده، تطبیق قوی، شاخص رنگی قوی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
An induced matching of a graph GG is a set MM of edges of GG such that every two vertices of GG that are incident with distinct edges in MM have distance at least 2 in GG. The maximum number of edges in an induced matching of GG is the induced matching number νs(G)νs(G) of GG. In contrast to ordinary matchings, induced matchings in graphs are algorithmically difficult. Next to hardness results and efficient algorithms for restricted graph classes, lower bounds are therefore of interest.We show that if GG is a connected graph of order n(G)n(G), maximum degree at most 3, girth at least 6, and without a cycle of length 7, then νs(G)≥n(G)−15, and we characterize the graphs achieving equality in this lower bound.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volumes 315–316, 6 February 2014, Pages 165–172
Journal: Discrete Mathematics - Volumes 315–316, 6 February 2014, Pages 165–172
نویسندگان
Michael A. Henning, Dieter Rautenbach,