Mathematics – Combinatorics
Scientific paper
2009-06-21
Mathematics
Combinatorics
20 pages, 12 figures
Scientific paper
Let $G$ be a connected graph with vertex set $V(G)=\{v_1,v_2,...,v_{\nu}\}$, which may have multiple edges but have no loops, and $2\leq d_G(v_i)\leq 3$ for $i=1,2,...,\nu$, where $d_G(v)$ denotes the degree of vertex $v$ of $G$. We show that if $G$ has an even number of edges, then the number of perfect matchings of the line graph of $G$ equals $2^{n/2+1}$, where $n$ is the number of 3-degree vertices of $G$. As a corollary, we prove that the number of perfect matchings of a connected cubic line graph with $n$ vertices equals $2^{n/6+1}$ if $n>4$, which implies the conjecture by Lov\'asz and Plummer holds for the connected cubic line graphs. As applications, we enumerate perfect matchings of the Kagom\'e lattices, $3.12.12$ lattices, and Sierpinski gasket with dimension two in the context of statistical physics.
Yan Weigen
Zhang Fuji
No associations
LandOfFree
Perfect matchings of line graphs with small maximum degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Perfect matchings of line graphs with small maximum degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perfect matchings of line graphs with small maximum degree will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-505761