pith. sign in

arxiv: 0906.3873 · v1 · submitted 2009-06-21 · 🧮 math.CO · math-ph· math.MP

Perfect matchings of line graphs with small maximum degree

classification 🧮 math.CO math-phmath.MP
keywords linematchingsnumberperfectconnecteddegreegraphcubic
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.