Article ID Journal Published Year Pages File Type
10331900 Information Processing Letters 2015 6 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,