Indexed by:
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. © 2014 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Source :
Information Processing Letters
ISSN: 0020-0190
Year: 2015
Issue: 2
Volume: 115
Page: 269-274
0 . 6 0 5
JCR@2015
0 . 7 0 0
JCR@2023
ESI HC Threshold:175
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: