Issue 
Wuhan Univ. J. Nat. Sci.
Volume 28, Number 3, June 2023



Page(s)  192  200  
DOI  https://doi.org/10.1051/wujns/2023283192  
Published online  13 July 2023 
Mathematics
CLC number: O157.6
The Number of Perfect Matchings in (3,6)Fullerene
School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo 454003, Henan, China
Received:
20
November
2022
A fullerene is a connected cubic plane graph whose faces are only triangles and hexagons, and has the connectivity or . The fullerenes with connectivity are the tubes consisting of concentric hexagonal layers such that each layer consists of two hexagons, capped on each end by two adjacent triangles, denoted by . A fullerene with vertices has exactly perfect matchings. The structure of a fullerene with connectivity can be determined by only three parameters , and, thus we denote it by , where is the radius (number of rings), is the size (number of spokes in each layer, , is even), and is the torsion (). In this paper, the counting formula of the perfect matchings in is given, and the number of perfect matchings is obtained. Therefore, the correctness of the conclusion that every bridgeless cubic graph with vertices has at least perfect matchings proposed by Esperet et al is verified for fullerene .
Key words: perfect matching / (3,6)fullerene graph / recurrence relation / counting formula
Biography: YANG Rui, female, Ph. D., Associate professor, research direction: graph theory and its application. Email: yangrui@hpu.edu.cn
Fundation item: Supported by National Natural Science Foundation of China (11801148, 11801149 and 11626089) and the Foundation for the Doctor of Henan Polytechnic University (B2014060)
© Wuhan University 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
Let be a graph. A perfect matching of 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 NPhard even in bipartite graphs^{[4]}. Therefore, it is very difficult to obtain the formula of the perfect matchings in a graph.
A ‐fullerene is a connected cubic planar graph whose faces are only length or hexagons. Došlić^{[5]} showed that fullerene only exists for and . A 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 fullerenes and fullerenes. In the 1970s, Lovász and Plummer^{[7]} conjectured that the number of perfect matchings of a cubic bridgeless graph should grow exponentially with its order. It was solved in the affirmative by Esperet et al^{[8]}. That is, every cubic bridgeless graph with vertices has at least perfect matchings. And many scholars have given the enumeration formulas of perfect matchings for some graphs with special structures^{[9,10]}.
A fullerene graph is a plane cubic graph whose faces are only triangles and hexagons. It is known that a fullerene graph is extendable^{[7] }and has the connectivity or . The fullerenes with connectivity are the tubes consisting of concentric hexagonal layers such that each layer consists of two hexagons, capped on each end by two adjacent triangles, denoted by . And a fullerene with vertices has exactly perfect matchings ^{[1113]}. The structure of a fullerene with connectivity can be determined by only three parameters and , thus we denote it by , where is the radius (number of rings), is the size (number of spokes in each layer,, is even), and is the torsion ()^{[1416]}. A set of edges of a graph is called a matching if no two edges of have a vertex in common. A perfect matching of a graph is a matching that covers all vertices of ^{[1719]}. Let be a graph with perfect matchings. If two perfect matchings and of have a different edge, then and are said to be two different perfect matchings of . A graph is called a planar graph if can be drawn in the plane so that its edges intersect only at their ends. Such a drawing is called a planar embedding of 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 .
1 Preliminaries
Let be a connected fullerene graph, where , , . That is, is a tubular fullerene consisting of 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 connected planar graph has a unique planar embedding, for the sake of simplification, also represents its planar embedding graph. Since , , can be classified: If is odd and , then (see Fig. 1(a)); If is odd and ,then (see Fig. 1(b)); If is even and , then (see Fig. 1(c)); If is even and , then (see Fig. 1(d)). It is easy to verify that . Therefore, there are three types of in the sense of isomorphism.
Fig. 1 A fullerene 
Proposition 1 If is a fullerene, then is isomorphic to , , or (see Fig. 1).
Let .Denote by the concentric rings of from the inside to outside. The edge that is not on the concentric rings is called transversal edge. Let , then there are exactly one length face, two length faces, and the rest are length faces in . Let be the length face in , then there are four vertices of degree 2 and four vertices of degree 3 appearing on the boundary of f alternately. Denote by the any two vertices of degree 2 on the boundary of . Let be adjacent to a pendant vertex, say , and adjacent to a pendant vertex, say , such that . Let , then is a subgraph of . If is odd, by Proposition 1, then is isomorphic to or . Therefore, is isomorphic to the graph shown in Fig. 2(a). Thus, is isomorphic to , , or according to the position of (see Fig. 2).
Fig. 2 , when is odd 
Similarly, if is even, by Proposition 1, then . Therefore, is isomorphic to the graph shown in Fig. 3(a). Thus, is isomorphic to , , or according to the position of (see Fig. 3).
Fig. 3 , when is even 
Next, we give the number of perfect matchings in .
Lemma 1 Let be a fullerene, where . Let be a subgraph of formed by removing the inner cap of and adding two pendant vertices (see Figs. 2, 3 the subgraphs ). Denote by the number of perfect matchings in .
) If is odd and , then
) If is odd and , then
) If is odd and , then
) If is even and , then
) If is even and , then
) If is even and , then
Proof Let the planar embedding of be shown in Fig. 1. Let be the perfect matchings set of . Denote by the concentric rings of from the inside to outside. Denote by the vertices of along the clockwise direction of such that and are arranged on the same line for , .
If , then denote by the two pendant vertices such that and are adjacent to and respectively. Then the labelling of the vertices of the graph is shown in Fig. 4. Thus, can be expressed as four types: denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges . Thus , . That is, . Since , , , then
Fig. 4 The labelling of 
If , then denote by the two pendant vertices such that and are adjacent to and respectively. Similarly, denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges . Thus , . That is, . Since , , , then
If , then denote by the two pendant vertices such that and are adjacent to and respectively. Similarly, denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges . Thus , . That is, . Since ,,, , then
If , then denote by the two pendant vertices such that and are adjacent to and respectively. Similarly, denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges . Thus , . That is, . Since ,, , , then
If , then denote by the two pendant vertices such that and are adjacent to and respectively. Similarly, denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges . Thus , . That is, . Since , , , then
If , then denote by the two pendant vertices such that and are adjacent to and respectively. Similarly, denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges .Thus , .That is, . Since , , , then
According to , we can obtain
By the definition of , we can get and . Equations and imply that
According to , combining with , we can obtain
Then it follows that . Let , where is odd. Then . By canceling the items, we can get . That is,
Equations and imply that satisfies the recurrence relation
The homogeneous relation is , and the characteristic roots are . Therefore, the general solution is
We now seek a particular solution of the recurrence relation . We try as a particular solution. Substituting into (14), we now get
the above equation gives . Hence
is a solution for each choice of constants and . To satisfy the initial condition , then . Since is odd, then . Substituting it into (15), we get
where is odd. Combining with , we obtain
where is odd. Combining with , we obtain
where is odd. Substituting formulas , and into formulas , , , respectively, we conclude that
where is even.
2 Main Results
By Proposition 1 and Lemma 1 , we can get the number of perfect matchings in .
Theorem 1 Let be a fullerene, where . When is odd and , denote by the number of perfect matchings of . Then
Proof When is odd and , by Proposition 1, then (see Fig. 1(a)). Denote by the concentric rings of from the inside to outside. Denote by the vertices of along the clockwise direction of such that and are arranged on the same line for , . Let be a set of transversal edges (see Fig. 5).
Fig. 5 The labeled graph 
Let be the perfect matchings set of and the perfect matchings set of containing edges in . Thus , . That is, .
Since any perfect matching in does not contain any edge of , any perfect matching , the edges of must belong to . Thus there are two matching methods covering all vertices on . According to the fractional multiplication, we can get .
For , we select arbitrarily any traversal edge of as matched edge which can not be extended to a perfect matching of as at least one vertex on is not covered, that is, there is no perfect matching in ; Similarly, there is no perfect matching in . Thus .
For , there is exactly one perfect matching, that is, .
For , can be expressed as six types: denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges .Thus , . That is, .
Next we give the proof idea for finding the number of perfect matchings of . Let be a subgraph of formed by removing the inner cap of and adding two pendant vertices. Since is odd, . By Lemma 1, we know the number of perfect matchings in . On the other hand, we can calculate the number of perfect matchings in . Thus the number of perfect matchings of can be obtained by using the fractional multiplication.
Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . From the fractional multiplication, we can get , where and represent the number of perfect matchings of and , respectively. By definition , then , . Thus, . Similarly, we can get . Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . From the fractional multiplication, we can get . By definition , then , .Thus, . Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . By definition , then . Thus, .
Therefore, .
By Lemma 1, we can get the number of perfect matchings in .
Thus Theorem 1 is proved. On the other hand, we can verify that there are perfect matchings in and perfect matchings in by a simple calculation, which is consistent with the result calculated by formula .
Theorem 2 Let be a fullerene, where . When is odd and , denote by the number of perfect matchings of . Then
Proof When is odd and , by Proposition 1, then (see Fig. 1(b)). Denote by the concentric rings of from the inside to outside. Denote by the vertices of along the clockwise direction of such that and are arranged on the same line for , . Let be a set of transversal edges.
Let be the perfect matchings set of and the perfect matchings set of containing edges in . Thus ,. That is, .
Since any perfect matching in does not contain any edge of , any perfect matching , the edges of must belong to . Thus there are two matching methods covering all vertices on . According to the fractional multiplication, we can get .
For , we select arbitrarily any traversal edge of as matched edge which cannot be extended to a perfect matching of as at least one vertex on is not covered, that is, there is no perfect matching in ; Similarly, there is no perfect matching in . Thus .
For , there is exactly one perfect matching, that is, .
For , can be expressed as six types: denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges .Thus , . That is, .
Next we give the proof idea for finding the number of perfect matchings of . Let be a subgraph of formed by removing the inner cap of and adding two pendant vertices. Since is odd, . By Lemma 1, we know the number of perfect matchings in . On the other hand, we can calculate the number of perfect matchings in . Thus the number of perfect matchings of can be obtained by using the fractional multiplication.
Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . From the fractional multiplication, we can get , where and represent the number of perfect matchings of and , respectively. By definition , then , . Thus, . Similarly, we can get . Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . From the fractional multiplication, we can get . By definition , then ,.Thus, . Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . By definition , then . Thus, .
Therefore, .
By Lemma 1, we can get the number of perfect matchings in .
Thus Theorem 2 is proved. On the other hand, we can verify that there are perfect matchings in by a simple calculation, which is consistent with the result calculated by formula .
Theorem 3 Let be a fullerene, where . When is even, denote by the number of perfect matchings of . Then
Proof When is even, by Proposition 1, then (see Fig. 1(c)). Denote by the concentric rings of from the inside to outside. Denote by the vertices of along the clockwise direction of such that and are arranged on the same line for , . Let be a set of transversal edges.
Let be the perfect matchings set of and the perfect matchings set of containing edges in . Thus , . That is, .
Since any perfect matching in does not contain any edge of , any perfect matching , the edges of must belong to . Thus there are two matching methods covering all vertices on . According to the fractional multiplication, we can get .
For , we select arbitrarily any traversal edge of as matched edge which can not be extended to a perfect matching of as at least one vertex on is not covered, that is, there is no perfect matching in ; Similarly, there is no perfect matching in . Thus .
For , there is exactly one perfect matching, that is, .
For , can be expressed as six types: denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges ; denote by the perfect matchings set containing edges .Thus , . That is, .
Next we give the proof idea for finding the number of perfect matchings of . Let be a subgraph of formed by removing the inner cap of and adding two pendant vertices. Since is even, . By Lemma 1, we know the number of perfect matchings in . On the other hand, we can calculate the number of perfect matchings in . Thus the number of perfect matchings of can be obtained by using the fractional multiplication.
Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . From the fractional multiplication, we can get , where and represent the number of perfect matchings of and , respectively. By definition , then , . Thus, . Similarly, we can get . Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . From the fractional multiplication, we can get . By definition , then , . Thus, . Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in , and the other part is the matching edges in . From the fractional multiplication, we can get . By definition , then ,. Thus, . Similarly, we can get . Let , that is, contains edges . Then can be divided into two parts: one part is the matching edges restricted in graph , and the other part is the matching edges in . By definition , then . Thus, .
Therefore, .
By Lemma 1, we can get the number of perfect matchings in .
Thus Theorem 3 is proved. On the other hand, we can verify that there are perfect matchings in by a simple calculation, which is consistent with the result calculated by formula .
Let be a fullerene with vertices. Since has concentric rings, vertices on each ring, and all vertices of are on these concentric rings, then , that is, . By combining Theorems 13, we can get the perfect matchings number of .
Corollary 1 Let be a fullerene with vertices, and denote by the number of perfect matchings of . Then
References
 Trinajstić N. Chemical Graph Theory[M]. Boca Ratan: CRC Press, 2018. [CrossRef] [Google Scholar]
 Randić M. On the characterization of local aromatic properties in benzenoid hydrocarbons[J]. Tetrahedron, 1974, 30(14): 20672074. [CrossRef] [Google Scholar]
 Swinborne R, Herndon W C, Gutman I. Kekulé structures and resonance energies of benzenoid hydrocarbons[J]. Tetrahedron Letters, 1975, 16(10): 755758. [CrossRef] [Google Scholar]
 Valiant L G. The complexity of computing the permanent[J]. Theoretical Compute Science, 1979, 8(2): 189201. [CrossRef] [MathSciNet] [Google Scholar]
 Došlić T. Cyclical edgeconnectivity of fullerene graphs and (k, 6)cages[J]. Journal of Mathematical Chemistry, 2003, 33(2): 103112. [CrossRef] [MathSciNet] [Google Scholar]
 Kardoš F, Král' D, Miškuf J, et al. Fullerene graphs have exponentially many perfect matchings[J]. Journal of Mathematical Chemistry, 2009, 46(2): 443447. [CrossRef] [MathSciNet] [Google Scholar]
 Lovász L, Plummer M D. Matching Theory[M]. New York: NorthHolland Press, 1986. [Google Scholar]
 Esperet L, Kardoš F, King A D, et al. Exponentially many perfect matchings in cubic graphs[J]. Advances in Mathematics, 2011, 227(4): 16461664. [CrossRef] [MathSciNet] [Google Scholar]
 Feng X, Zhang L, Zhang M. Enumeration of perfect matchings of lattice graphs by Pfaffians[J]. Applied Mathematics and Computation, 2018, 338: 412420. [CrossRef] [MathSciNet] [Google Scholar]
 Zhang L Z, Wei S L, Lu F L. The number of Kekulé structures of polyominos on the torus[J]. Journal of Mathematical Chemistry, 2013, 51(1): 354368. [CrossRef] [MathSciNet] [Google Scholar]
 Yang R, Zhang H P. Hexagonal resonance of (3,6)fullerens[J]. Journal of Mathematical Chemistry, 2012, 50(1): 261273. [CrossRef] [MathSciNet] [Google Scholar]
 Sun C H, Zhang H P. On bicriticality of (3,6)fullerene graphs[J]. Journal of Mathematical Chemistry, 2018, 56(9): 27852793. [CrossRef] [MathSciNet] [Google Scholar]
 Shi L J, Zhang H P. Forcing and antiforcing numbers of (3,6)fullerenes[J]. MATCH Commun Math Comput Chem, 2016, 76(3): 597614. [MathSciNet] [Google Scholar]
 John P E, Sachs H. Spectra of toroidal graphs[J]. Discrete Mathematics, 2009, 309(9): 26632681. [CrossRef] [MathSciNet] [Google Scholar]
 Goodey P R. A class of Hamiltonian polytopes[J]. Journal of Graph Theory, 1977, 1(2): 181185. [CrossRef] [MathSciNet] [Google Scholar]
 Grünbaum B, Motzkin T S. The number of hexagons and the simplicity of geodesics on certain polyhedra[J]. Canadian Journal of Mathematics, 1963, 15: 744751. [CrossRef] [Google Scholar]
 Bondy J A, Murty U S R. Graph Theory[M]. Berlin: SpringerVerlag, 2008. [CrossRef] [Google Scholar]
 Brualdi R A. Introductory Combinatorics[M]. New York: NorthHolland Press, 2009. [Google Scholar]
 Diestel R. Graph Theory[M]. New York: SpringerVerlag, 2005. [Google Scholar]
All Figures
Fig. 1 A fullerene 

In the text 
Fig. 2 , when is odd 

In the text 
Fig. 3 , when is even 

In the text 
Fig. 4 The labelling of 

In the text 
Fig. 5 The labeled graph 

In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.