© Wuhan University 2023

0 Introduction

Let $G$ be a graph. A perfect matching of $G$ is also called a Kekulé structure in mathematical chemistry. Since the study of Kekulé structure of molecules helps to study the structural stability, aromaticity and other chemical properties of molecules, chemists and graph theorists have paid extensive attention to Kekulé structure and its related properties^[1]. For example, studying the sextet pattern of Kekulé structures in hydrocarbons can predict the relative stability and aromaticity of compounds^[2], and calculating the number of Kekulé structures in hydrocarbons can estimate the resonance energy of compounds^[3]. Therefore, it is of great theoretical significance to study the enumeration of perfect matchings of molecular graphs. Hence the enumeration problem for perfect matchings has played an important role in the chemical graph theory. For general graphs, the problem is NP-hard even in bipartite graphs^[4]. Therefore, it is very difficult to obtain the formula of the perfect matchings in a graph.

A $\left(k,\mathrm{6}\right)$‐fullerene $\left(k\ge \mathrm{3}\right)$ is a $\mathrm{3}$-connected cubic planar graph whose faces are only $k$-length or hexagons. Došlić^[5] showed that $\left(k,\mathrm{6}\right)$-fullerene only exists for $k=\mathrm{3},\mathrm{4}$ and $\mathrm{5}$. A $\left(\mathrm{5,6}\right)$-fullerene is the ordinary carbon fullerene molecular graph for which the problem of establishing an exponential lower bound on the number of perfect matchings for all fullerene graphs was settled by Kardoš et al^[6]. However, there is no systematic study on the number of perfect matchings in $\left(\mathrm{4,6}\right)$-fullerenes and $\left(\mathrm{3,6}\right)$-fullerenes. In the 1970s, Lovász and Plummer^[7] conjectured that the number of perfect matchings of a cubic bridgeless graph $G$ should grow exponentially with its order. It was solved in the affirmative by Esperet et al^[8]. That is, every cubic bridgeless graph $G$ with $n$ vertices has at least ${\mathrm{2}}^{\raisebox{1ex}{$n$}\!\left/ \!\raisebox{-1ex}{$\mathrm{3656}$}\right.}$ perfect matchings. And many scholars have given the enumeration formulas of perfect matchings for some graphs with special structures^[9,10].

A $\left(\mathrm{3,6}\right)$-fullerene graph is a plane cubic graph whose faces are only triangles and hexagons. It is known that a $\left(\mathrm{3,6}\right)$-fullerene graph is $\mathrm{1}$-extendable^[7] and has the connectivity $\mathrm{2}$ or $\mathrm{3}$. The $\left(\mathrm{3,6}\right)$-fullerenes with connectivity $\mathrm{2}$ are the tubes consisting of $l\left(l\ge \mathrm{1}\right)$ concentric hexagonal layers such that each layer consists of two hexagons, capped on each end by two adjacent triangles, denoted by $T_l\left(l\ge \mathrm{1}\right)$. And a $\left(\mathrm{3,6}\right)$-fullerene $T_l$ with $n$ vertices has exactly ${\mathrm{2}}^{\frac{n}{\mathrm{4}}}+\mathrm{1}$ perfect matchings ^[11-13]. The structure of a $\left(\mathrm{3,6}\right)$-fullerene $G$ with connectivity $\mathrm{3}$ can be determined by only three parameters $r,s$ and $t$, thus we denote it by $G=\left(r,s,t\right)$, where $r$ is the radius (number of rings), $s$ is the size (number of spokes in each layer,$s\ge \mathrm{4}$, $s$ is even), and $t$ is the torsion ($\mathrm{0}\le t<s,$$t\equiv r\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}$)^[14-16]. A set of edges $M$ of a graph $G$ is called a matching if no two edges of $M$ have a vertex in common. A perfect matching of a graph $G$ is a matching $M$ that covers all vertices of $G$^[17-19]. Let $G$ be a graph with perfect matchings. If two perfect matchings $M_{\mathrm{1}}$ and $M_{\mathrm{2}}$ of $G$ have a different edge, then $M_{\mathrm{1}}$ and $M_{\mathrm{2}}$ are said to be two different perfect matchings of $G$. A graph $G$ is called a planar graph if $G$ can be drawn in the plane so that its edges intersect only at their ends. Such a drawing is called a planar embedding of $G$ in the plane. If a graph contains a vertex whose degree is exactly one, then such a vertex is called a pendant vertex of the graph ^[18,19].

The paper is organized as follows. In Section 1, we recall some notions, definitions and lemmas which will be used throughout the paper. In Section 2, we give the counting formulas of the perfect matchings in $G=\left(n+\mathrm{1,4},t\right)$.

1 Preliminaries

Let $G=\left(n+\mathrm{1},s,t\right)$ be a $\mathrm{3}$-connected $\left(\mathrm{3,6}\right)$-fullerene graph, where $s=\mathrm{4}$, $\mathrm{0}\le t<\mathrm{4}$, $t\equiv \left(n+\mathrm{1}\right)\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}$. That is,$G$ is a tubular $\left(\mathrm{3,6}\right)$-fullerene consisting of $n$ concentric hexagonal layers such that each layer consists of four hexagons, capped on each end by two opposite triangles and a hexagon. Since every simple $\mathrm{3}$-connected planar graph has a unique planar embedding, for the sake of simplification, $G$ also represents its planar embedding graph. Since $\mathrm{0}\le t<\mathrm{4}$, $t\equiv \left(n+\mathrm{1}\right)\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}$, $G$ can be classified: $\left(\mathrm{i}\right)$ If $n$ is odd and $t=\mathrm{0}$, then $G\cong Q_n^{\mathrm{1}}$ (see Fig. 1(a));$\left(\mathrm{i}\mathrm{i}\right)$ If $n$ is odd and $t=\mathrm{2}$,then $G\cong Q_n^{\mathrm{2}}$ (see Fig. 1(b)); $\left(\mathrm{i}\mathrm{i}\mathrm{i}\right)$ If $n$ is even and $t=\mathrm{1}$, then $G\cong Q_n^{\mathrm{3}}$ (see Fig. 1(c)); $\left(\mathrm{i}\mathrm{v}\right)$ If $n$ is even and $t=\mathrm{3}$, then $G\cong Q_n^{\mathrm{4}}$ (see Fig. 1(d)). It is easy to verify that $Q_n^{\mathrm{3}}\cong Q_n^{\mathrm{4}}$ . Therefore, there are three types of $G=\left(n+\mathrm{1,4},t\right)$ in the sense of isomorphism.

Fig. 1 A $\left(\mathrm{3,6}\right)$-fullerene $\mathit{G}=\left(\mathit{n}+\mathrm{1},\mathrm{4},\mathit{t}\right)$

Proposition 1   If $G=\left(n+\mathrm{1,4},t\right)$ is a $\left(\mathrm{3,6}\right)$-fullerene, then $G$ is isomorphic to $Q_n^{\mathrm{1}}$, $Q_n^{\mathrm{2}}$, or $Q_n^{\mathrm{3}}$(see Fig. 1).

Let $G=\left(n+\mathrm{1,4},t\right)$.Denote by $C_{\mathrm{1}},C_{\mathrm{2}},\cdots ,C_{n+\mathrm{1}}$ the $n+\mathrm{1}$ concentric rings of $G$ from the inside to outside. The edge that is not on the concentric rings is called transversal edge. Let $G^{\text{'}}=G-C_{\mathrm{1}}$, then there are exactly one $\mathrm{8}$-length face, two $\mathrm{3}$-length faces, and the rest are $\mathrm{6}$-length faces in $G^{\text{'}}$ . Let $f$ be the $\mathrm{8}$-length face in $G^{\text{'}}$, then there are four vertices of degree 2 and four vertices of degree 3 appearing on the boundary of f alternately. Denote by $u,v$ the any two vertices of degree 2 on the boundary of $f$. Let $u$ be adjacent to a pendant vertex, say $u^{\text{'}}$, and $v$ adjacent to a pendant vertex, say $v^{\text{'}}$, such that $u^{\text{'}}\ne v^{\text{'}}$. Let $L_n=G^{\text{'}}\bigcup \left\{u{u}^{\text{'}},v{v}^{\text{'}}\right\}$, then $L_n$ is a subgraph of $G$. If $n$ is odd, by Proposition 1, then $G$ is isomorphic to $Q_n^{\mathrm{1}}$ or $Q_n^{\mathrm{2}}$. Therefore, $G^{\text{'}}=G-C_{\mathrm{1}}$ is isomorphic to the graph shown in Fig. 2(a). Thus, $L_n$ is isomorphic to $L_n^{\mathrm{1}}$, $L_n^{\mathrm{2}}$, or $L_n^{\mathrm{3}}$ according to the position of $u^{\text{'}},v^{\text{'}}$ (see Fig. 2).

Fig. 2 ${\mathit{G}}^{\mathit{\text{'}}}$, ${\mathit{L}}_{\mathit{n}}^{\mathit{i}}\left(\mathit{i}=\mathrm{1,2},\mathrm{3}\right)$ when $\mathit{n}$ is odd

Similarly, if $n$ is even, by Proposition 1, then $G\cong Q_n^{\mathrm{3}}$. Therefore, $G^{\text{'}}=G-C_{\mathrm{1}}$ is isomorphic to the graph shown in Fig. 3(a). Thus, $L_n$ is isomorphic to $L_n^{\mathrm{4}}$, $L_n^{\mathrm{5}}$, or $L_n^{\mathrm{6}}$ according to the position of $u^{\text{'}},v^{\text{'}}$ (see Fig. 3).

Fig. 3 ${\mathit{G}}^{\mathit{\text{'}}}$, ${\mathit{L}}_{\mathit{n}}^{\mathit{i}}\left(\mathit{i}=\mathrm{4,5},\mathrm{6}\right)$ when $\mathit{n}$ is even

Next, we give the number of perfect matchings in $L_n^i\left(i=\mathrm{1,2},\cdots ,\mathrm{6}\right)$.

Lemma 1   Let $G=\left(n+\mathrm{1,4},t\right)$ be a $\left(\mathrm{3,6}\right)$-fullerene, where $\mathrm{0}\le t<\mathrm{4},t\equiv \left(n+\mathrm{1}\right)\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}$. Let $L_n$ be a subgraph of $G$ formed by removing the inner cap of $G$ and adding two pendant vertices (see Figs. 2, 3 the subgraphs $L_n^i,i=\mathrm{1,2},\cdots ,\mathrm{6}$). Denote by $f_i\left(n\right)$ the number of perfect matchings in $L_n^i\left(i=\mathrm{1,2},\cdots ,\mathrm{6}\right)$.

$\mathrm{1}$) If $n$ is odd and $L_n\cong L_n^{\mathrm{1}}$, then

$\begin{array}{l}{f}_{\mathrm{1}}\left(n\right)=-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+\left(\frac{\mathrm{1}}{\mathrm{2}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ -{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}\end{array}$

$\mathrm{2}$) If $n$ is odd and $L_n\cong L_n^{\mathrm{2}}$, then

$\begin{array}{l}{f}_{\mathrm{2}}\left(n\right)=-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+\left(\frac{\mathrm{1}}{\mathrm{2}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ +{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}\end{array}$

$\mathrm{3}$) If $n$ is odd and $L_n\cong L_n^{\mathrm{3}}$, then

$f_{\mathrm{3}}\left(n\right)=\frac{\mathrm{1}}{\mathrm{4}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+\frac{\mathrm{1}}{\mathrm{4}}{\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^n$

$\mathrm{4}$) If $n$ is even and $L_n\cong L_n^{\mathrm{4}}$, then

$\begin{array}{l}{f}_{\mathrm{4}}\left(n\right)=\left(\frac{\mathrm{1}}{\mathrm{2}}-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ +\left(\mathrm{2}+\frac{\mathrm{3}\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{2}}\end{array}$

$\mathrm{5}$) If $n$ is even and $L_n\cong L_n^{\mathrm{5}}$, then

$\begin{array}{l}{f}_{\mathrm{5}}\left(n\right)=\left(\frac{\mathrm{1}}{\mathrm{2}}-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}\right){\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ +\left(\frac{\mathrm{3}}{\mathrm{2}}+\sqrt[]{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{2}}-{\mathrm{2}}^{\frac{n-\mathrm{2}}{\mathrm{2}}}\end{array}$

$\mathrm{6}$) If $n$ is even and $L_n\cong L_n^{\mathrm{6}}$, then

$\begin{array}{l}{f}_{\mathrm{6}}\left(n\right)=\left(\frac{\mathrm{1}}{\mathrm{2}}-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}\right){\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ +\left(\frac{\mathrm{3}}{\mathrm{2}}+\sqrt[]{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{2}}+{\mathrm{2}}^{\frac{n-\mathrm{2}}{\mathrm{2}}}\end{array}$

Proof   Let the planar embedding of $G$ be shown in Fig. 1. Let ${\mathrm{ℳ}}_i$ be the perfect matchings set of $L_n^i\left(i=\mathrm{1,2},\cdots ,\mathrm{6}\right)$. Denote by $C_{\mathrm{2}},C_{\mathrm{3}},\cdots ,C_{n+\mathrm{1}}$ the $n$ concentric rings of $L_n$ from the inside to outside. Denote by $u_{i\mathrm{1}},u_{i\mathrm{2}},\cdots ,u_{i\mathrm{8}}$ the vertices of $C_i$ along the clockwise direction of $C_i$ such that $u_{ij}$ and $u_{i,j+\mathrm{4}}$ are arranged on the same line for $i=\mathrm{2,3},\cdots ,n+\mathrm{1}$, $j=\mathrm{1,2},\mathrm{3,4}$.

If $L_n\cong L_n^{\mathrm{1}}$, then denote by $u_{\mathrm{13}},u_{\mathrm{17}}$ the two pendant vertices such that $u_{\mathrm{13}}$ and $u_{\mathrm{17}}$ are adjacent to $u_{\mathrm{23}}$ and $u_{\mathrm{27}}$ respectively. Then the labelling of the vertices of the graph $L_n^{\mathrm{1}}$ is shown in Fig. 4. Thus, ${\mathrm{ℳ}}_{\mathrm{1}}$ can be expressed as four types: denote by ${\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{1}}$ the perfect matchings set containing edges $u_{\mathrm{22}}{u}_{\mathrm{32}},u_{\mathrm{24}}{u}_{\mathrm{34}}$; denote by ${\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{2}}$ the perfect matchings set containing edges $u_{\mathrm{22}}{u}_{\mathrm{32}},u_{\mathrm{26}}{u}_{\mathrm{36}}$; denote by ${\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{3}}$ the perfect matchings set containing edges $u_{\mathrm{28}}{u}_{\mathrm{38}},u_{\mathrm{24}}{u}_{\mathrm{34}}$; denote by ${\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{4}}$ the perfect matchings set containing edges $u_{\mathrm{28}}{u}_{\mathrm{38}},u_{\mathrm{26}}{u}_{\mathrm{36}}$. Thus ${\mathrm{ℳ}}_{\mathrm{1}}^i\bigcap {\mathrm{ℳ}}_{\mathrm{1}}^j=\mathrm{\varnothing }\left(\mathrm{1}\le i<j\le \mathrm{4}\right)$,${\mathrm{ℳ}}_{\mathrm{1}}={\displaystyle \underset{i=\mathrm{1}}{\overset{\mathrm{4}}{\cup }}}{\mathrm{ℳ}}_{\mathrm{1}}^i$ . That is, $\left|{\mathrm{ℳ}}_{\mathrm{1}}\right|={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{4}}}\left|{\mathrm{ℳ}}_{\mathrm{1}}^i\right|$. Since $\left|{\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{2}}\right|=\left|{\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{3}}\right|=f_{\mathrm{4}}(n-\mathrm{1})$, $\left|{\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{1}}\right|=\left|{\mathrm{ℳ}}_{\mathrm{1}}^{\mathrm{4}}\right|=f_{\mathrm{5}}(n-\mathrm{1})$, $f_{\mathrm{1}}(n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{4}}}\left|{\mathrm{ℳ}}_{\mathrm{1}}^i\right|$, then

Fig. 4 The labelling of ${\mathit{L}}_{\mathit{n}}^{\mathrm{1}}$

$f_{\mathrm{1}}(n)=\mathrm{2}{f}_{\mathrm{4}}(n-\mathrm{1})+\mathrm{2}{f}_{\mathrm{5}}(n-\mathrm{1})$(1)

If $L_n\cong L_n^{\mathrm{2}}$, then denote by $u_{\mathrm{11}},u_{\mathrm{15}}$ the two pendant vertices such that $u_{\mathrm{11}}$ and $u_{\mathrm{15}}$ are adjacent to $u_{\mathrm{21}}$ and $u_{\mathrm{25}}$ respectively. Similarly, denote by ${\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{1}}$ the perfect matchings set containing edges $u_{\mathrm{22}}{u}_{\mathrm{32}},u_{\mathrm{26}}{u}_{\mathrm{36}}$; denote by ${\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{2}}$ the perfect matchings set containing edges $u_{\mathrm{22}}{u}_{\mathrm{32}},u_{\mathrm{28}}{u}_{\mathrm{38}}$; denote by ${\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{3}}$ the perfect matchings set containing edges $u_{\mathrm{24}}{u}_{\mathrm{34}},u_{\mathrm{26}}{u}_{\mathrm{36}}$; denote by ${\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{4}}$ the perfect matchings set containing edges $u_{\mathrm{24}}{u}_{\mathrm{34}},u_{\mathrm{28}}{u}_{\mathrm{38}}$. Thus ${\mathrm{ℳ}}_{\mathrm{2}}^i\bigcap {\mathrm{ℳ}}_{\mathrm{2}}^j=\mathrm{\varnothing }\left(\mathrm{1}\le i<j\le \mathrm{4}\right)$, ${\mathrm{ℳ}}_{\mathrm{2}}={\displaystyle \underset{i=\mathrm{1}}{\overset{\mathrm{4}}{\cup }}}{\mathrm{ℳ}}_{\mathrm{2}}^i$ . That is, $\left|{\mathrm{ℳ}}_{\mathrm{2}}\right|={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{4}}}\left|{\mathrm{ℳ}}_{\mathrm{2}}^i\right|$. Since $\left|{\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{1}}\right|=\left|{\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{4}}\right|=f_{\mathrm{4}}(n-\mathrm{1})$, $\left|{\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{2}}\right|=\left|{\mathrm{ℳ}}_{\mathrm{2}}^{\mathrm{3}}\right|=f_{\mathrm{6}}(n-\mathrm{1})$, $f_{\mathrm{2}}(n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{4}}}\left|{\mathrm{ℳ}}_{\mathrm{2}}^i\right|$, then

$f_{\mathrm{2}}(n)=\mathrm{2}{f}_{\mathrm{4}}(n-\mathrm{1})+\mathrm{2}{f}_{\mathrm{6}}(n-\mathrm{1})$(2)

If $L_n\cong L_n^{\mathrm{3}}$, then denote by $u_{\mathrm{11}},u_{\mathrm{13}}$ the two pendant vertices such that $u_{\mathrm{11}}$ and $u_{\mathrm{13}}$ are adjacent to $u_{\mathrm{21}}$ and $u_{\mathrm{23}}$ respectively. Similarly, denote by ${\mathrm{ℳ}}_{\mathrm{3}}^{\mathrm{1}}$ the perfect matchings set containing edges $u_{\mathrm{22}}{u}_{\mathrm{32}},u_{\mathrm{24}}{u}_{\mathrm{34}}$; denote by ${\mathrm{ℳ}}_{\mathrm{3}}^{\mathrm{2}}$ the perfect matchings set containing edges $u_{\mathrm{22}}{u}_{\mathrm{32}},u_{\mathrm{26}}{u}_{\mathrm{36}}$; denote by ${\mathrm{ℳ}}_{\mathrm{3}}^{\mathrm{3}}$ the perfect matchings set containing edges $u_{\mathrm{22}}{u}_{\mathrm{32}},u_{\mathrm{28}}{u}_{\mathrm{38}}$. Thus ${\mathrm{ℳ}}_{\mathrm{3}}^i\bigcap {\mathrm{ℳ}}_{\mathrm{3}}^j=\mathrm{\varnothing }\left(\mathrm{1}\le i<j\le \mathrm{3}\right)$, ${\mathrm{ℳ}}_{\mathrm{3}}={\displaystyle \underset{i=\mathrm{1}}{\overset{\mathrm{3}}{\cup }}}{\mathrm{ℳ}}_{\mathrm{3}}^i$ . That is, $\left|{\mathrm{ℳ}}_{\mathrm{3}}\right|={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\left|{\mathrm{ℳ}}_{\mathrm{3}}^i\right|$. Since $\left|{\mathrm{ℳ}}_{\mathrm{3}}^{\mathrm{1}}\right|=f_{\mathrm{5}}(n-\mathrm{1})$,$\left|{\mathrm{ℳ}}_{\mathrm{3}}^{\mathrm{2}}\right|=f_{\mathrm{4}}(n-\mathrm{1})$,$\left|{\mathrm{ℳ}}_{\mathrm{3}}^{\mathrm{3}}\right|=f_{\mathrm{6}}(n-\mathrm{1})$, $f_{\mathrm{3}}(n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\left|{\mathrm{ℳ}}_{\mathrm{3}}^i\right|$, then

$f_{\mathrm{3}}(n)=f_{\mathrm{4}}(n-\mathrm{1})+f_{\mathrm{5}}(n-\mathrm{1})+f_{\mathrm{6}}(n-\mathrm{1})$(3)

If $L_n\cong L_n^{\mathrm{4}}$ , then denote by $u_{\mathrm{12}},u_{\mathrm{16}}$ the two pendant vertices such that $u_{\mathrm{12}}$ and $u_{\mathrm{16}}$ are adjacent to $u_{\mathrm{22}}$ and $u_{\mathrm{26}}$ respectively. Similarly, denote by ${\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{1}}$ the perfect matchings set containing edges $u_{\mathrm{23}}{u}_{\mathrm{33}},u_{\mathrm{27}}{u}_{\mathrm{37}}$; denote by ${\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{2}}$ the perfect matchings set containing edges $u_{\mathrm{23}}{u}_{\mathrm{33}},u_{\mathrm{21}}{u}_{\mathrm{31}}$; denote by ${\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{3}}$ the perfect matchings set containing edges $u_{\mathrm{25}}{u}_{\mathrm{35}},u_{\mathrm{27}}{u}_{\mathrm{37}}$; denote by ${\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{4}}$ the perfect matchings set containing edges $u_{\mathrm{25}}{u}_{\mathrm{35}},u_{\mathrm{21}}{u}_{\mathrm{31}}$. Thus ${\mathrm{ℳ}}_{\mathrm{4}}^i\bigcap {\mathrm{ℳ}}_{\mathrm{4}}^j=\mathrm{\varnothing }\left(\mathrm{1}\le i<j\le \mathrm{4}\right)$, ${\mathrm{ℳ}}_{\mathrm{4}}={\displaystyle \underset{i=\mathrm{1}}{\overset{\mathrm{4}}{\cup }}}{\mathrm{ℳ}}_{\mathrm{4}}^i$ . That is, $\left|{\mathrm{ℳ}}_{\mathrm{4}}\right|={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{4}}}\left|{\mathrm{ℳ}}_{\mathrm{4}}^i\right|$. Since $\left|{\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{1}}\right|=f_{\mathrm{1}}(n-\mathrm{1})$,$\left|{\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{4}}\right|=f_{\mathrm{2}}(n-\mathrm{1})$, $\left|{\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{2}}\right|=\left|{\mathrm{ℳ}}_{\mathrm{4}}^{\mathrm{3}}\right|=f_{\mathrm{3}}(n-\mathrm{1})$, $f_{\mathrm{4}}(n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{4}}}\left|{\mathrm{ℳ}}_{\mathrm{4}}^i\right|$, then

$f_{\mathrm{4}}(n)=f_{\mathrm{1}}(n-\mathrm{1})+f_{\mathrm{2}}(n-\mathrm{1})+\mathrm{2}{f}_{\mathrm{3}}(n-\mathrm{1})$(4)

If $L_n\cong L_n^{\mathrm{5}}$ , then denote by $u_{\mathrm{16}},u_{\mathrm{18}}$ the two pendant vertices such that $u_{\mathrm{16}}$ and $u_{\mathrm{18}}$ are adjacent to $u_{\mathrm{26}}$ and $u_{\mathrm{28}}$ respectively. Similarly, denote by ${\mathrm{ℳ}}_{\mathrm{5}}^{\mathrm{1}}$ the perfect matchings set containing edges $u_{\mathrm{27}}{u}_{\mathrm{37}},u_{\mathrm{21}}{u}_{\mathrm{31}}$; denote by ${\mathrm{ℳ}}_{\mathrm{5}}^{\mathrm{2}}$ the perfect matchings set containing edges $u_{\mathrm{27}}{u}_{\mathrm{37}},u_{\mathrm{23}}{u}_{\mathrm{33}}$; denote by ${\mathrm{ℳ}}_{\mathrm{5}}^{\mathrm{3}}$ the perfect matchings set containing edges $u_{\mathrm{27}}{u}_{\mathrm{37}},u_{\mathrm{25}}{u}_{\mathrm{35}}$. Thus ${\mathrm{ℳ}}_{\mathrm{5}}^i\bigcap {\mathrm{ℳ}}_{\mathrm{5}}^j=\mathrm{\varnothing }\left(\mathrm{1}\le i<j\le \mathrm{3}\right)$, ${\mathrm{ℳ}}_{\mathrm{5}}={\displaystyle \underset{i=\mathrm{1}}{\overset{\mathrm{3}}{\cup }}}{\mathrm{ℳ}}_{\mathrm{5}}^i$ . That is, $\left|{\mathrm{ℳ}}_{\mathrm{5}}\right|={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\left|{\mathrm{ℳ}}_{\mathrm{5}}^i\right|$. Since $\left|{\mathrm{ℳ}}_{\mathrm{5}}^{\mathrm{2}}\right|=f_{\mathrm{1}}(n-\mathrm{1})$, $\left|{\mathrm{ℳ}}_{\mathrm{5}}^{\mathrm{1}}\right|=\left|{\mathrm{ℳ}}_{\mathrm{5}}^{\mathrm{3}}\right|=f_{\mathrm{3}}(n-\mathrm{1})$, $f_{\mathrm{5}}(n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\left|{\mathrm{ℳ}}_{\mathrm{5}}^i\right|$, then

$f_{\mathrm{5}}(n)=f_{\mathrm{1}}(n-\mathrm{1})+\mathrm{2}{f}_{\mathrm{3}}(n-\mathrm{1})$(5)

If $L_n\cong L_n^{\mathrm{6}}$, then denote by $u_{\mathrm{12}},u_{\mathrm{18}}$ the two pendant vertices such that $u_{\mathrm{12}}$ and $u_{\mathrm{18}}$ are adjacent to $u_{\mathrm{22}}$ and $u_{\mathrm{28}}$ respectively. Similarly, denote by ${\mathrm{ℳ}}_{\mathrm{6}}^{\mathrm{1}}$ the perfect matchings set containing edges $u_{\mathrm{21}}{u}_{\mathrm{31}},u_{\mathrm{23}}{u}_{\mathrm{33}}$; denote by ${\mathrm{ℳ}}_{\mathrm{6}}^{\mathrm{2}}$ the perfect matchings set containing edges $u_{\mathrm{21}}{u}_{\mathrm{31}},u_{\mathrm{25}}{u}_{\mathrm{35}}$; denote by ${\mathrm{ℳ}}_{\mathrm{6}}^{\mathrm{3}}$ the perfect matchings set containing edges $u_{\mathrm{21}}{u}_{\mathrm{31}},u_{\mathrm{27}}{u}_{\mathrm{37}}$.Thus ${\mathrm{ℳ}}_{\mathrm{6}}^i\bigcap {\mathrm{ℳ}}_{\mathrm{6}}^j=\mathrm{\varnothing }$$\left(\mathrm{1}\le i<j\le \mathrm{3}\right)$, ${\mathrm{ℳ}}_{\mathrm{6}}={\displaystyle \underset{i=\mathrm{1}}{\overset{\mathrm{3}}{\cup }}}{\mathrm{ℳ}}_{\mathrm{6}}^i$.That is, $\left|{\mathrm{ℳ}}_{\mathrm{6}}\right|={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\left|{\mathrm{ℳ}}_{\mathrm{6}}^i\right|$. Since $\left|{\mathrm{ℳ}}_{\mathrm{6}}^{\mathrm{2}}\right|=f_{\mathrm{2}}(n-\mathrm{1})$, $\left|{\mathrm{ℳ}}_{\mathrm{6}}^{\mathrm{1}}\right|=\left|{\mathrm{ℳ}}_{\mathrm{6}}^{\mathrm{3}}\right|=f_{\mathrm{3}}(n-\mathrm{1})$, $f_{\mathrm{6}}(n)={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\left|{\mathrm{ℳ}}_{\mathrm{6}}^i\right|$, then

$f_{\mathrm{6}}(n)=f_{\mathrm{2}}(n-\mathrm{1})+\mathrm{2}{f}_{\mathrm{3}}(n-\mathrm{1})$(6)

According to $(\mathrm{1})$-$(\mathrm{6})$, we can obtain

$f_{\mathrm{1}}(n)=\mathrm{4}{f}_{\mathrm{1}}(n-\mathrm{2})+\mathrm{2}{f}_{\mathrm{2}}(n-\mathrm{2})+\mathrm{8}{f}_{\mathrm{3}}(n-\mathrm{2})$(7)

$f_{\mathrm{2}}(n)=\mathrm{2}{f}_{\mathrm{1}}(n-\mathrm{2})+\mathrm{4}{f}_{\mathrm{2}}(n-\mathrm{2})+\mathrm{8}{f}_{\mathrm{3}}(n-\mathrm{2})$(8)

$f_{\mathrm{3}}(n)=\mathrm{2}{f}_{\mathrm{1}}(n-\mathrm{2})+\mathrm{2}{f}_{\mathrm{2}}(n-\mathrm{2})+\mathrm{6}{f}_{\mathrm{3}}(n-\mathrm{2})$(9)

By the definition of $f_i(\mathrm{1})$, we can get $f_{\mathrm{1}}\left(\mathrm{1}\right)=\mathrm{0},f_{\mathrm{2}}\left(\mathrm{1}\right)=\mathrm{2}$ and $f_{\mathrm{3}}\left(\mathrm{1}\right)=\mathrm{1}$. Equations $(\mathrm{7})$ and $(\mathrm{8})$ imply that

$f_{\mathrm{2}}(n)=f_{\mathrm{1}}(n)+{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}$(10)

According to $(\mathrm{10})$, combining $(\mathrm{8})$ with $(\mathrm{9})$, we can obtain

$f_{\mathrm{2}}(n)=\mathrm{6}{f}_{\mathrm{2}}(n-\mathrm{2})+\mathrm{8}{f}_{\mathrm{3}}(n-\mathrm{2})-{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}$(11)

$f_{\mathrm{3}}(n)=\mathrm{4}{f}_{\mathrm{2}}(n-\mathrm{2})+\mathrm{6}{f}_{\mathrm{3}}(n-\mathrm{2})-{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}$(12)

Then it follows that $f_{\mathrm{2}}(n)+\sqrt[]{\mathrm{2}}{f}_{\mathrm{3}}(n)=\left(\mathrm{6}+\mathrm{4}\sqrt[]{\mathrm{2}}\right)$$\left[f_{\mathrm{2}}(n-\mathrm{2})+\sqrt[]{\mathrm{2}}g(n-\mathrm{2})\right]-\left(\mathrm{1}+\sqrt[]{\mathrm{2}}\right)\cdot {\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}$. Let $f\left(n\right)=f_{\mathrm{2}}(n)+\sqrt[]{\mathrm{2}}{f}_{\mathrm{3}}(n)$, where $n$ is odd. Then $f\left(\mathrm{1}\right)=f_{\mathrm{2}}(\mathrm{1})+\sqrt[]{\mathrm{2}}{f}_{\mathrm{3}}(\mathrm{1})=\mathrm{2}+\sqrt[]{\mathrm{2}}$. By canceling the items, we can get $f\left(n\right)=\left(\mathrm{1}+\sqrt[]{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}+{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}$. That is,

$f_{\mathrm{2}}(n)+\sqrt[]{\mathrm{2}}{f}_{\mathrm{3}}(n)=\left(\mathrm{1}+\sqrt[]{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}+{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}$(13)

Equations $(\mathrm{12})$ and $(\mathrm{13})$ imply that $f_{\mathrm{3}}(n)$ satisfies the recurrence relation

$f_{\mathrm{3}}(n)=\left(\mathrm{6}-\mathrm{4}\sqrt[]{\mathrm{2}}\right)f_{\mathrm{3}}(n-\mathrm{2})+\left(\mathrm{4}+\mathrm{4}\sqrt[]{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{3}}$(14)

The homogeneous relation is $f_{\mathrm{3}}\left(n\right)=\left(\mathrm{6}-\mathrm{4}\sqrt[]{\mathrm{2}}\right)$$f_{\mathrm{3}}(n-\mathrm{2})$, and the characteristic roots are $q_{\mathrm{1}}=\mathrm{2}-\sqrt[]{\mathrm{2}},q_{\mathrm{2}}=\sqrt[]{\mathrm{2}}-\mathrm{2}$. Therefore, the general solution is

$f_{\mathrm{3}}\left(n\right)=c_{\mathrm{1}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+c_{\mathrm{2}}{\left(\sqrt[]{\mathrm{2}}-\mathrm{2}\right)}^n$

We now seek a particular solution of the recurrence relation $(\mathrm{14})$. We try $f_{\mathrm{3}}\left(n\right)=p{\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^n$ as a particular solution. Substituting $f_{\mathrm{3}}\left(n\right)$ into (14), we now get

$\begin{array}{l}p{\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^n=\left(\mathrm{6}-\mathrm{4}\sqrt[]{\mathrm{2}}\right)\cdot p\cdot {\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{2}}\\ +\left(\mathrm{4}+\mathrm{4}\sqrt[]{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{3}}\end{array}$

the above equation gives $p=\frac{\mathrm{1}}{\mathrm{4}}$. Hence

$f_{\mathrm{3}}\left(n\right)=c_{\mathrm{1}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+c_{\mathrm{2}}{\left(\sqrt[]{\mathrm{2}}-\mathrm{2}\right)}^n+\frac{\mathrm{1}}{\mathrm{4}}{\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^n$(15)

is a solution for each choice of constants $c_{\mathrm{1}}$ and $c_{\mathrm{2}}$. To satisfy the initial condition $f_{\mathrm{3}}\left(\mathrm{1}\right)=\mathrm{1}$, then $c_{\mathrm{1}}-c_{\mathrm{2}}=\frac{\mathrm{1}}{\mathrm{4}}$ . Since $n$ is odd, then ${\left(\sqrt[]{\mathrm{2}}-\mathrm{2}\right)}^n=-{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n$. Substituting it into (15), we get

$f_{\mathrm{3}}\left(n\right)=\frac{\mathrm{1}}{\mathrm{4}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+\frac{\mathrm{1}}{\mathrm{4}}{\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^n$(16)

where $n$ is odd. Combining $(\mathrm{13})$ with $(\mathrm{16})$, we obtain

$\begin{array}{l}{f}_{\mathrm{2}}\left(n\right)=-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+\left(\frac{\mathrm{1}}{\mathrm{2}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ +{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}\end{array}$(17)

where $n$ is odd. Combining $(\mathrm{10})$ with $(\mathrm{17})$, we obtain

$\begin{array}{l}{f}_{\mathrm{1}}\left(n\right)=-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}{\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^n+\left(\frac{\mathrm{1}}{\mathrm{2}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ -{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}\end{array}$(18)

where $n$ is odd. Substituting formulas $(\mathrm{16})$, $(\mathrm{17})$ and $(\mathrm{18})$ into formulas $(\mathrm{4})$, $(\mathrm{5})$, $(\mathrm{6})$, respectively, we conclude that

$\begin{array}{l}{f}_{\mathrm{4}}\left(n\right)=\left(\frac{\mathrm{1}}{\mathrm{2}}-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ +\left(\mathrm{2}+\frac{\mathrm{3}\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{2}}\end{array}$

$\begin{array}{l}{f}_{\mathrm{5}}\left(n\right)=\left(\frac{\mathrm{1}}{\mathrm{2}}-\frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}\right){\left(\mathrm{2}-\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{1}}\\ +\left(\frac{\mathrm{3}}{\mathrm{2}}+\sqrt[]{\mathrm{2}}\right){\left(\mathrm{2}+\sqrt[]{\mathrm{2}}\right)}^{n-\mathrm{2}}-{\mathrm{2}}^{\frac{n-\mathrm{2}}{\mathrm{2}}}\end{array}$