کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10331900 686963 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new lower bound for the number of perfect matchings of line graph
ترجمه فارسی عنوان
یک مرز پایین تر برای تعدادی از منطق های مناسب گراف خط
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
,