On the number of perfect matchings in the line graph of a traceable graph

Given a graph G=(V,E), let L(G) denote its line graph and M(G) denote the number of perfect matchings of G. In this paper, for a traceable graph G of order n with a Hamilton path Pn, we first observe that M(L(G)) can be expressed as M(L(G))=∑T∈TM(L(T)), where T is the set of caterpillar trees determ...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2023-03, Vol.327, p.110-118
Main Authors: Chen, Haiyan, Ye, Yinzhu
Format: Article
Language:English
Subjects:
Caterpillar tree
Line graph
Perfect matching
Traceable graph
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph G=(V,E), let L(G) denote its line graph and M(G) denote the number of perfect matchings of G. In this paper, for a traceable graph G of order n with a Hamilton path Pn, we first observe that M(L(G)) can be expressed as M(L(G))=∑T∈TM(L(T)), where T is the set of caterpillar trees determined by G and Pn. Then by determining the minimum and maximum values of M(L(T)),T∈T, we obtain lower and upper bounds for M(L(G)). We also show that our lower bounds for this kind of graphs are much better than some known lower bounds for general graphs if the average degree of G is larger than 4.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2022.12.011