Abstract:

Let Kp be a complete graph of order p. Let L*n,p be the graph with n vertices obtained by identifying the vertex ui of Kp with the vertex vi of the tree Ti, where i=1,2,…,r,1≤r≤p. The graphs of L*n,p with maximal and minimal, with secondlargest and thirdlargest total number of matchings are obtained respectively.

Key words: The total number of matchings; graph transformation; extremal graph