Indexed by:
Abstract:
Let G = (V, E) be a graph, V (G) = {u(1), u(2),..., u(n)} and vertical bar E vertical bar be even. In this paper, we show that M(L(G)) >= 2(vertical bar E vertical bar-vertical bar V vertical bar+1) + Sigma(n)(i=1) (f(G)(u(i)) + g(G)(u(i))!!-n, where f(G)(u(i))-w(G-u(i)), w(G-u(i)) is the number of components of G-u(i), g(G)(u(i)) is the number of those components of G-u(i) 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)) >= eta(Delta) . 2(vertical bar E vertical bar-vertical bar v vertical bar-Delta+2) for every 2-connected graph G, and give a sufficient and necessary condition about 2-connected graphs G such that M(L(G)) = eta(Delta) . 2(vertical bar E vertical bar-vertical bar v vertical bar-Delta+2), where eta(Delta) = Sigma(o <= k <=Delta/2)(Delta/2k)(2k)!!, Delta is the maximum degree of G, and (2k)!! = (2k-1)(2k- 3)...3.1. (C) 2014 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
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 Discipline: COMPUTER SCIENCE;
ESI HC Threshold:175
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 2
SCOPUS Cited Count: 2
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: