Some Results On The Number Of Perfect Matchings In The Line Graph

Matchings of a graph and its counting play an important role not only in graph theory and computational science,but also in statistical physics and quantum chemistry.The counting of perfect matchings and maximum matchings is an NP-hard problem.In this thesis,we study the counting of perfect matchings and maximum matchings for line graphs of some special graphs.Let G be a connected graph with n vertices and m edges,and let L（G）denote its line graph,M（G）and Max（G）denote the number of perfect matchings and maximum matchings in G,respectively,then the main content and results are as follows:1.Let G be a traceable graph with even edges,we study the number of perfect matchings of L（G）.For this family of graphs,we first express M（L（G））as the sum of M（L（T））of 2^m-n+1caterpillar trees T,and then we obtain upper and lower bounds for M（L（G））by determining the minimum and maximum values of M（L（T））.2.Let G be a graph with even edges and the maximum degree equal to n-1,we study the number of perfect matchings of L（G）.For this family of graphs,we first express M（L（G））as the sum of M（L（S））of 2^m-n+1blossomed star trees S,then we obtain upper and lower bounds for M（L（G））by determining the minimum and maximum values of M（L（S））.3.Let G be a graph with odd edges,we study the number of maximum matchings of L（G）.First,we determine the number of edges contained in the maximum matchings of L（G）and a general expression for Max（L（G））.Then we discuss Max（L（G））further when G is a tree or a unicyclic graph.We obtain some results for the extremal values of Max（L（G））,and get some explicit expressions for Max（L（G））when G belongs to some special families of graphs.