Perfect matchings of line graphs with small maximum degree

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\le d_G(v_i)\le 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ász and Plummer holds for the connected cubic line graphs. As applications, we enumerate perfect matchings of the Kagomé lattices, $\mathrm{3.12.12}$ lattices, and Sierpinski gasket with dimension two in the context of statistical physics.

20 pages, 12 figures

References in corpus (2)

• Exact solution of close-packed dimers on the kagome lattice
• Close-packed dimers on the kagome lattice: Finite lattices and the Grassmannian approach