Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331900 | Information Processing Letters | 2015 | 6 Pages |
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
Xue Zhou,