| 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. E-mail: 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 (B2014-060)
© 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 NP-hard 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 [11-13]. 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 (
)[14-16]. 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 
[17-19]. 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 |
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
|
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
|
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 1-3, 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): 2067-2074. [CrossRef] [Google Scholar]
- Swinborne R, Herndon W C, Gutman I. Kekulé structures and resonance energies of benzenoid hydrocarbons[J]. Tetrahedron Letters, 1975, 16(10): 755-758. [CrossRef] [Google Scholar]
- Valiant L G. The complexity of computing the permanent[J]. Theoretical Compute Science, 1979, 8(2): 189-201. [CrossRef] [MathSciNet] [Google Scholar]
- Došlić T. Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages[J]. Journal of Mathematical Chemistry, 2003, 33(2): 103-112. [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): 443-447. [CrossRef] [MathSciNet] [Google Scholar]
- Lovász L, Plummer M D. Matching Theory[M]. New York: North-Holland 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): 1646-1664. [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: 412-420. [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): 354-368. [CrossRef] [MathSciNet] [Google Scholar]
- Yang R, Zhang H P. Hexagonal resonance of (3,6)-fullerens[J]. Journal of Mathematical Chemistry, 2012, 50(1): 261-273. [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): 2785-2793. [CrossRef] [MathSciNet] [Google Scholar]
- Shi L J, Zhang H P. Forcing and anti-forcing numbers of (3,6)-fullerenes[J]. MATCH Commun Math Comput Chem, 2016, 76(3): 597-614. [MathSciNet] [Google Scholar]
- John P E, Sachs H. Spectra of toroidal graphs[J]. Discrete Mathematics, 2009, 309(9): 2663-2681. [CrossRef] [MathSciNet] [Google Scholar]
- Goodey P R. A class of Hamiltonian polytopes[J]. Journal of Graph Theory, 1977, 1(2): 181-185. [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: 744-751. [CrossRef] [Google Scholar]
- Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer-Verlag, 2008. [CrossRef] [Google Scholar]
- Brualdi R A. Introductory Combinatorics[M]. New York: North-Holland Press, 2009. [Google Scholar]
- Diestel R. Graph Theory[M]. New York: Springer-Verlag, 2005. [Google Scholar]
All Figures
|
Fig. 1 A |
| In the text | |
|
Fig. 2
|
| In the text | |
|
Fig. 3
|
| 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 (full-text 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 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.