کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331900 | 686963 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new lower bound for the number of perfect matchings of line graph
ترجمه فارسی عنوان
یک مرز پایین تر برای تعدادی از منطق های مناسب گراف خط
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات ترکیبی شمارش تطبیق کامل، نمودار خط، نمودار 2-اتصال
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let G=(V,E) be a graph, V(G)={u1,u2,â¯,un} and |E| be even. In this paper, we show that M(L(G))â¥2|E|â|V|+1+âi=1n(fG(ui)+gG(ui))!!ân, where fG(ui)=dG(ui)âw(Gâui), w(Gâui) is the number of components of Gâui, gG(ui) is the number of those components of Gâui each of which has an even number of edges, and M(L(G)) is the number of perfect matchings of the line graph L(G). Also we show that M(L(G))â¥Î·(Î)â
2|E|â|V|âÎ+2 for every 2-connected graph G, and give a sufficient and necessary condition about 2-connected graphs G such that M(L(G))=η(Î)â
2|E|â|V|âÎ+2, where η(Î)=â0â¤kâ¤Î/2(Î2k)(2k)!!, Î is the maximum degree of G, and (2k)!!=(2kâ1)(2kâ3)â¯3â
1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 269-274
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 269-274
نویسندگان
Xue Zhou,