ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 301-313
Matchings in m-generalized fullerene graphs
Afshin Behmaram *
Faculty of Mathematical Sciences, University of Tabriz, Tabriz, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box:19395-5746, Tehran, Iran
Tomislav Doslic f
Faculty of Civil Engineering, Kacideva 26, 10000 Zagreb, Croatia
Shmuel Friedland *
Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607-7045, USA
Received 29 June 2015, accepted 24 October 2015, published online 29 December 2015
A connected planar graph is called m-generalized fullerene if two of its faces are m-gons and all other faces are pentagons and hexagons. In this paper we first determine some structural properties of m-generalized fullerenes and then use them to obtain new results on the enumerative aspects of perfect matchings in such graphs. We provide both upper and lower bounds on the number of perfect matchings in m-generalized fullerene graphs and state exact results in some special cases.
Keywords: Perfect matching, Pfaffian graph, fullerene graph, Hadamard-Fischer inequality. Math. Subj. Class.: 05C30, 05C70, 15A15
1 Introduction
Classical fullerene graphs have been intensely researched since the discovery of buckmin-sterfullerene in the fundamental paper [20], which appeared in 1985. This paper gave rise to the whole new area of fullerene science. Most of the research has been driven by a need
*This research was in part supported by a grant from IPM (No. 93050018) t Partially support by Croatian Science Foundation under the project 8481 (BioAmpMode).
* Partially supported by NSF grant DMS-1216393.
E-mail addresses: behmaram@tabrizu.ac.ir (Afshin Behmaram), doslic@grad.hr (Tomislav Doslic), friedlan@uic.edu (Shmuel Friedland)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
302
Ars Math. Contemp. 11 (2016) 403-413
to find a reliable predictor of fullerene stability. It became clear very early that the most stable (i.e., the experimentally observed) isomers all have isolated pentagons (IP). The main focus since has been on the invariants that could further distinguish between the isolated pentagon isomers. Several graph-theoretic invariants have been tested in this capacity and none of them was found completely satisfactory. In the meantime, the experimental evidence appeared indicating that for larger number of atoms some non-IP isomers might be energetically preferable to the IP ones, and even that some non-classical cages (i.e., with faces that are neither pentagons nor hexagons) are favored over the classical ones. Those observations motivated various generalizations of fullerene graphs. One such generalization is the subject of the present study.
A fullerene graph is a cubic, planar, 3-connected graph with only pentagonal and hexagonal faces. It follows easily from the Euler's formula that there must be exactly 12 pentagonal faces, while the number of hexagonal faces can be zero or any natural number greater than one. The smallest possible fullerene graph is the dodecahedron on 20 vertices, while the existence of fullerene graphs on an even number of vertices greater than 22 follows from a result by Griinbaum and Motzkin [12] obtained long before the discovery of fullerenes. Analogous results for IP fullerenes was obtained by Klein et al. [18].
A connected 3-regular planar graph G = (V, E) is called an m-generalized fullerene if exactly two of its faces are m-gons and all other faces are pentagons and/or hexagons. (We also count the outer (unbounded) face of G.) In the rest of the paper we only consider m > 3; note that for m = 5, 6 an m-generalized fullerene graph is a classical fullerene graph. As for the classical fullerenes it is easy to show that the number of pentagons is fixed, while the number of hexagons is not determined. The smallest m-generalized fullerene has 4m vertices and no hexagonal faces. Such graphs are sometimes called m-barrels. They have two m-gons and 2m pentagons and they can be elongated by inserting k > 0 layers of m hexagons between two half-barrels. The elongated barrels are one of the main subjects of the present paper, since their highly symmetric structure allows for obtaining good bounds and even exact results on the number of perfect matchings in them.
A matching M in a graph G is a collection of edges of G such that no two edges of M share a vertex. If every vertex of G is incident to an edge of M, the matching M is called perfect. Perfect matchings have played an important role in the chemical graph theory, in particular for benzenoid graphs, where their number correlates with the compound's stability. Although it turned out that for fullerenes they do not have the same role as for benzenoids, there are many results concerning their structural and enumerative properties.
The paper is organized as follows. In the next section we state and prove some structural results about m-generalized fullerene graphs. In particular, we show that the number of hexagons is not necessarily an integer multiple of m. In section 3 we examine the diameter, the hamiltonicity and the leapfrog transformation of the elongated barrels, while in section 4 we obtain the upper bounds on the number of their perfect matchings. In section 5 we refine the results of section 4 by using the transfer matrix method. Finally, in the concluding section we state some conjectures about the entropy of the family of elongated barrels.
2 m-generalized fullerene graphs
In this introductory section we consider some structural properties of m-generalized fullerenes. For the beginning, we show that the number of pentagonal faces must be fixed.
Lemma 2.1. Let m > 3 be a non-negative integer different from 5. Then an m-generalized
A. Behmaram et al.: Matchings in m-generalized fullerene graphs
303
fullerene G = (V, E) has exactly 2m pentagonal faces.
Proof. Let v, e, f be the number of vertices, edges and faces, respectively, of an m-genera-lized fullerene G. From the Euler formula, v - e + f = 2, and 3-regularity of G we obtain 3v = 2e. Let p and h denote the number of pentagonal and hexagonal faces, respectively, of G. Since every edge appears in exactly two faces, and every vertex in exactly 3 faces, we have the equality 2e = 2m + 5p + 6h. By plugging it into Euler formula we obtain
2m + 5p + 6h 2m + 5p + 6h

3
2
+ (2+ p + h) = 2,
and hence p = 2m.	□
The above proof works also for the case m = 5, yielding the familiar value of 12 pentagonal faces for classical fullerenes.
It is clear from the definition of elongated barrels that the number of hexagons in such graphs must be divisible by m. Here we show that there are also m-generalized fullerenes in which this is not the case. Take a hemi-dodecahedral cap shown in Fig. 1 left and truncate it at two non-adjacent vertices of the central pentagon. (A hemi-dodecahedral
6	6	
6	6	6
Figure 1: Nanotube caps with the number of hexagons not divisible by m.
6
6
cap is a pentagon surrounded by five other pentagons. Without any hexagons, two such caps make a dodecahedron, while by inserting a number of hexagonal layers one obtains a narrow nanotube.) The central pentagon now becomes a heptagon, and four out of five surrounding pentagons become hexagons. Now insert a vertex on both new edges in the heptagon and join them by an edge. The heptagon gives rise to a pentagon and a hexagon. We have obtained a cap with 21 vertices consisting of 2 quadrangles, 2 pentagons and 5 hexagons. We can now construct an infinite sequence of m-generalized fullerenes by taking another hemi-dodecahedral cap and connecting it with our cap using I = 4« - 1 layers of hexagons. The total number of hexagons in such a graph will not be divisible by m = 4. Another example, this time of a cap with two triangles and eight hexagons giving rise to an infinite sequence of nanotubes of circumference six, is shown in Fig. 1 right.
Lemma 2.2. Let G = (V, E) be an m-generalizedfullerene with h hexagons. If G has an m-gonalface surrounded by m pentagons, then there exists an m-generalizedfullerene G' with h + m hexagons in which one m-gonal face is surrounded by m pentagons.
304
Ars Math. Contemp. 11 (2016) 403-413
Proof. Add additional m vertices in the middle of each edge of the m-gon to make it C2m. Each of the m surrounding pentagons becomes a hexagon. Now connect the new m vertices to a new m-gon.	□
So if there exists G satisfying the above lemma, where h = 0 modulo m, then we can create a sequence of generalized m-fullerene with h + 1m hexagons for 1 G N.
From a given fullerene graph G its leapfrog transform Le(G) is obtained by first taking the dual of G and then truncating it. It is easy to see that Le(G) is again a fullerene graph, with the number of vertices three times that of the original graph. Leapfrog fullerenes have many important properties; in particular, they are always IP, and they are rich in perfect matchings [7, 8]. It follows from the above results that the class of m-generalized fullerenes is also closed under the leapfrog transform.
Lemma 2.3. The leapfrog of an m-generalized fullerene is again an m-generalized fullerene.
3 The elongated barrels F(m, k)
In this section we describe a special family of m-generalized fullerenes, the elongated barrels, and list their properties. Recall that an elongated barrel F(m, k) is obtained from the corresponding barrel by inserting k > 0 layers (or rings) of m hexagons between two halves of the barrel. For m = 5 and m = 6 we obtain classical fullerene nanotubes. Most of the nanotube properties are also preserved by elongated barrels. Note that F(m, k) has n = 2m(k + 2) vertices.
Elongated barrels can be neatly represented graphically using a sequence of k + 3 concentric circles with monotonically increasing radii such that the innermost and the outermost circle each have m vertices (representing, hence, two m-gons), while all other circles have 2m vertices each. An example is shown in Fig. 3. It follows that all elongated bar-
Figure 2: Elongated barrel F(8,2).
rels are circular graphs in the sense of ref. [5]. (A graph G is circular if all its vertices can be placed on a number of concentric circles with increasing radii so that the edges are either arcs of the circles or connect vertices on neighboring circles without intersections between circles. A graph is semi-circular if there is a set V0 of its vertices that cannot be placed on the circles in the above manner; instead, the subgraph induced by V0 is placed
A. Behmaram et al.: Matchings in m-generalized fullerene graphs
305
within the innermost circle. Since any connected planar graph without bridges is trivially semi-circular, of interest are graphs for which V0 is either empty or small.)
Theorem 3.1. Let m > 3 and k be non-negative integers. Then the diameter d(F(m, k)) of the elongated barrel F (m, k) is given by d(F (m, k)) = 2k + 3 for large enough k.
Proof. It is clear that for k = 0 the diameter is equal to m and that it is achieved along the circumference. The effect of circumference is still felt for small k; for large k, however, (where large means k > m), the effect vanishes as the diameter is achieved between two vertices in antipodal caps. So, take a vertex v in one of antipodal m-gons. There are three vertices at distance one from v, one of them already at the first layer of hexagons, the other two in the same m-gon. Two more steps are needed to reach the second layer of hexagons; however, two more steps from other vertices at distance one from v will also advance along the m-gon and along the concentric circle of the first layer of hexagons. It is clear that after some (roughly) 2m steps the advances along concentric circles will meet on the opposite side, and from there on, all vertices on the ¿-th concentric circle will be at the distance of either 2i or 2i + 1 from v. The antipodal ring of pentagon is reached after 2k +1 steps, and additional two steps are needed to reach any vertex in the antipodal m-gon.	□
For m = 5,6, i.e., for fullerene nanotubes, the above result is consistent with results of [2,3].
The problem of hamiltonicity of fullerene graphs had been open for a long time. There were several partial results [17,19,21], until this special case of Barnette's conjecture was settled by Kardos, who provided a computer-assisted proof [15].
Theorem 3.2. For all natural numbers m > 3 and k, F(m, k) is Hamiltonian.
Proof. We construct a Hamiltonian cycle in F(m, k) in the following way. Start from the innermost m-gon. Label its vertices clockwise by v0j1,..., v0,m. Connect them by the path P0 = v01v02... v0jm-1v0 m. Each of the end-vertices of this path has exactly one neighbor not in the m-gon. Moreover, those neighbors both lie in the same pentagon and they are not adjacent. Hence, they both lie on C2m. Label the vertices of C2m by
v1;1,..., v12m-1, v12m clockwise so that v1;1 is adjacent to v0j1 and v1j2m-1 is adjacent to v0,m. Extend the path on one end by edges v0 mv1j2m-1 and v1j2m-1v12m, and on the
306	Ars Math. Contemp. 11 (2016) 403-413
other side by the path v0,ivi,ivi,2... vi,2m-2 and denote the new path by Pi. Proceed in the same manner toward next concentric circle. After k +1 steps the end-vertices of Pk+i will be adjacent each to one of two adjacent vertices, vk+2 i and vk+2,m, on the outer Cm, and hence, those two edges, together with all edges of the outer Cm except vfc+2,mvfc+2,i, will form a Hamilton cycle when added to Pk+i.	□
The existence of Hamiltonian cycles has several consequences important formatchings-related properties of elongated barrels.
Corollary 3.3. F(m, k) has at least three different perfect matchings. Moreover, each edge of F(m, k) is contained in some perfect matching of F(m, k).
The first claim is obvious - there are two perfect matchings formed by taking every other edge in a Hamiltonian cycle, and the third one formed by the edges that do not participate in it. The second claim of the above corollary says that all elongated barrels are 1-extendable. (A graph G is 1-extendable if each its edge is contained in a perfect matching of G.) This fact gives us a linear lower bound on the number of perfect matchings in F(m, k), but we will derive much better lower bounds later. A bit better linear bounds would also follow for m > 5 by using the fact that all F(m, k) are also 2-extendable, i.e., that any two independent edges are contained in (and hence can be extended to) a perfect matching. The 2-extendability follows from the fact that for m > 5 all F(m, k) are cyclically 5-edge connected, i.e., they cannot be separated into two components, each containing a cycle, by deleting fewer than 5 edges [6], and result by Holton and Plummer [14] which claims that a cubic 3-connected planar graph which is cyclically 4-edge connected and has no faces of size 4 is 2-extendable.
Another consequence is 3-edge-colorability of F(m, k). It means that its edges can be partitioned into 3 perfect matchings. As perfect matchings are also known as 1-factors, we have the following result.
Corollary 3.4. F(m, k) is 1-factorizable.
An interesting perspective of elongated barrels has been offered by recently introduced concept of altans. Let G be a planar graph and S a cyclically ordered set of k vertices of degree 2 incident with its unbounded side. Altan A(G) is obtained by encircling G by C2k and connecting every other vertex of C2k to a vertex of S respecting the cyclical order. The obtained graph can serve itself as input for another round of the altan transform; in that way we obtain iterated altans An(G) for n > 0. The above definition is very informal, but it captures the most important aspects; we refer the reader to [4,13] for formal definition of altans and exhaustive survey of their properties.
Starting from G = Cm and taking S = V(Cm), the altan transform will result in one half of barrel F(m, 0). Further iterations will result in adding successive layers of hexagons, so that k + 1 iterations will give us F(m, k) without one of its two caps.
An interesting property of altan transform is that it exactly doubles the number of perfect matchings of the starting graph [4].
Theorem 3.5. Let $(G) denote the number of perfect matchings in G. Then $(A(G)) = 2$(G). Hence, $(A"(G)) = 2"$(G).
The above result gives us an exponential lower bound on the number of perfect match-ings in F(m, k) for an even m.
A. Behmaram et al.: Matchings in m-generalized fullerene graphs
307
Corollary 3.6. Let m be even. Then
$F(m,k) > 2k+3.
It is clear that the above result underestimates $(F(m,k)), since it does not take into account perfect matchings containing some (or even all) edges connecting Ak+1(Cm) with the other cap. We will later compare this bound with some more precise bounds obtained using transfer matrices. For odd m the above result is of no use, since all iterated altans of Cm have an odd number of vertices for odd m.
It would be interesting to see if similar exponential lower bounds could be established for all m-generalized fullerenes. A similar long-standing open problem for fullerenes was settled recently in [16].
Another consequence of being Hamiltonian is the following upper bound on the number of perfect matchings in F(m, k). It is a direct consequence of Corollary 11 of [5].
Corollary 3.7. Let $(F (m, k)) denote the number of perfect matchings in F (m, k). Then $(F(m, k)) < 8n/8 for mk even and $(F(m, k)) < a/3 • 8(n-2)/8 for mk odd. Here n denotes the number of vertices of F (m, k).
Since 81/8 « 1.29684 < 1.34801 « 61/6, our result improves the upper bound of 6n/6 of reference [1].
The last result of this section shows that the property of circularity is preserved under the leapfrog transform for even k and not preserved for odd k.
Theorem 3.8. The leapfrog transform of F (m, k) is circular if and only if k is even. In that case, the circular structure of Le(F (m, k)) is as follows. The first inner circle is Cm, the second circle is C3m, then there are 3k + 1 circles C4m, then follows the circle C3m, and the last circle is Cm. If k is odd then Le(F (m, k)) is semi-circular and has the following structure. The first circle is Cm, then the next circles are C4m. The next to the last circle is C3m, and the last circle is Cm. Inside the first circle there are m vertices.
The proof follows along the same lines as for Theorem 15 of [5] and we omit the details.
4 Improved upper bounds on the number of perfect matchings in
F(m, k)
In this section we use the Hadamard-Fischer inequality to improve the upper bounds on $(F(m, k)) from the previous section. To this end, we consider two orientations of Cm. In the first one, all edges are oriented clockwise; in the second one, one edge is oriented anticlockwise, while all other edges are oriented clockwise. The first orientation we denote by 1 ^ 2 ^ ... ^ n ^ 1, the second one by 1 ^ 2 ^ ... ^ n, 1 ^ n. Let Tn,_, Tn,+ be the skew symmetric matrices obtained from the first and from the second orientation, respectively. We will need the following result (Lemma 18 of ref. [5]).
Lemma 4.1. For n > 3
det(/n - Tl+) = det(/n - T2-) = ((^)n + (^)n)2 if n is odd; det(/n - T2,+) = ((^^^)n + ()n + 2)2	if n is even;
det(/n - T2 _) = (()n + ()n - 2)2	if n is even.
308
Ars Math. Contemp. 11 (2016) 403-413
Furthermore, for n > 3 the odd-indexed subsequence of (det(In — T",+ ))1 is increasing, while the even-indexed subsequence is decreasing. Both subsequences converge to
(i+^I)2 ^ 2.6180.
Now we combine the lemma with the Hadamard-Fischer inequality to establish an upper bound on $(F(m, k)) better than those of the previous section.
Theorem 4.2. The number of perfect matchings in F (m, k) is bounded from above by
• fc+i
((^ r + (^ D ((^ j2™ + (^ j2™ + ^ 2	if m is odd;
k+i
((^j™ + (^j™ + 2)((^j2™ + (^j2™ + ^ 2 if m is even.
Proof. The proof is along the lines of the proof of Theorem 9 of [5]. We use the Hadamard-Fischer inequality to estimate from above the determinant of B := —S2(F(m, k)), which is equal to $(F(m, k))4. Let V, i e [k + 3] be all vertices of F(m, k) on the i — th circle. So V and Vk+3 have m vertices, while all other V have 2m vertices. Recall the Hadamard-Fischer inequality
det B < n det B[V,].
¿e[fc+3]
Note that since the path of distance 2 between any two edges on each V can be obtained only using the edges on the cycle F(m, k)(Vi), it follows that B[Vi] = /|V.| — S(F(m, k + 1)(Vi))2. Here S(F(m, k)(Vi)) is a skew symmetric matrix induced by the Pfaffian orientation of F(m, k) on the cycle F(m, k)(Vi). (See [24] for more on Pfaffian graphs.) The arguments in Section 5 of [5] yield that det B(Vi) = det(/|V.| — T|2V,| +). The theorem now follows by applying Lemma 4.1.	□
Theorem 4.2 gives better upper bounds than Corollary 3.7. It is only to be expected, since it fully draws on the information stored in the structure of F(m, k), while Corollary 3.7 uses only its hamiltonicity and regularity. While the asymptotic behavior of Corollary 3.7 is of the type 8"/8 « 1.29684" and does not depend on m, Theorem 4.2 yields the asymptotic + 2) , that is roughly of the order of « 1.2720" for large m.
5 The transfer matrix method for counting perfect matchings in
F(m, k)
In this section we provide some explicit formulas and some asymptotics result of the type $(F(m, k)) ~ Cp(m)k, where p(m) is the spectral radius of certain nonnegative irreducible matrix associated with F(m, k). We use the transfer matrix method to count the matchings as in [10].
Consider the cycle C2to. Fix a vertex on C2to and call this vertex 1. View 1 as colored in white. Then color other vertices of C2to black and white so we get a bipartite partition of C2to, where the edges connect white and black vertices. Delete a black neighbor vertex to the left of 1 on C2to to obtain the path P2to_i. Then the vertex i for i = 2,..., m is the white vertex of distance 2(i — 1) from 1 on P2to_i. The black vertex i on C2to is located to the right of the white vertex i. So the distance between the white vertex 1 and the black vertex i e [m — 1] is 2i — 1 on P2to_i. The distance between the white vertex 1 and the
A. Behmaram et al.: Matchings in m-generalized fullerene graphs
309
black vertex m is 1 on C2m. Let S C [m] = {1,2,..., m}. Then a(S), P(S) are the sets of those white vertices and black vertices on C2m whose indices belong to S, respectively.
Let A(m) = [aST] be the following 2m x 2m matrix with nonnegative integer entries. Each S, T is a subset of [m] = {1,..., m}. (S, T are allowed to be empty.) Then aST is the number of perfect matchings in the subgraph of C2m obtained by deleting the vertices a(S) U P(T). We assume that a[m][m] = 1.
Lemma 5.1. Let m > 3 be an integer, and assume that A(m) = [aST]STC[m] is defined as above. Then aST = 0 if |S| = |TIn particular, A is a direct sum of m +1 submatrices
Ai,m = [aST]S,Tc[m],|S| = |T|=i for i = 0 . . . , m.
Proof. Let S, T C [m]. Delete the vertices from a(S), P(T) in C2m to obtain the subgraph G. Then G has m — |S|, m - |T| white and black vertices, respectively. To have a perfect
matching in G we need the equality |S| = |T|. Hence A(m) = diag(A0,m,..., Am,m).
' ' □
As an illustration, we construct matrix A for the smallest case m = 3. Here by i ± 1 we mean modulo 3. So 3 + 1 = 1 and 1 — 1 = 3. Note that aST = 0 if |S| + |T| is odd. Then the following elements of A are nonzero:
a00 = 2, a{i}{i} = a{i}{i+1} = a{i}{i+2} = a{i,j}{i,j} = a{i,j}{i-1,j-1} = a[3][3] = 1.
Hence A(3) is an 8 x 8 matrix whose rows and columns are indexed by the subsets of
[3] in the following way: 0, {1}, {2}, {3}, {1,2}, {1,3}, {2, 3}, {1, 2,3}.
0 0 " 00 00 00 00 1 0 1 0 01
A(3)
to	0	0	0	0	0
0	1	1	1	0	0
0	1	1	1	0	0
0	1	1	1	0	0
0	0	0	0	1	1
0	0	0	0	0	1
0	0	0	0	1	0
0	0	0	0	0	0
We can see that A(3) is the direct sum of the following matrices:
	1	1	1		1	1	0
Ao,3 = [2], A13 =	1	1	1	, A2,3 =	0	1	1
	1	1	1		1	0	1
A3,3 = [1].
Let now m > 3 and k be nonnegative integers. In F(m, k) we label each vertex on Oi for i = 1,..., k + 3 as follows. Choose a vertex on O1, which is Cm, and call it vertex 1. Then the right neighbor of i is i +1 for i = 1,..., m — 1. Assume that all m vertices of Cm are colored in black. Now the white vertex indexed i on O2, which is C2m, is connected to the vertex i in O1. Now label the black vertices on O2 as above and connect black vertices in O2 to white vertices in O3, which have the same index i G [m]. Continue in the same manner until we color and label all vertices of F(m, k). Note that the color of all vertices on Ok+3, which is Cm, is white. Furthermore, the only edges that connect two vertices with the same color in F(m, k) lie on O1 and Ok+3.
310
Ars Math. Contemp. 11 (2016) 403-413
Let x = (xS), S C [m] be the following vector with 0,1, 2 coordinates. Consider the cycle Cm, which is either O1 or Ok+3, where the vertices are marked as above. Then xS is the number of perfect matchings in the subgraph of Cm induced by the set of vertices
[m] \ S.
Theorem 5.2.
$(F (m,k)) = xTA(m)k+1x. Proof. The right-hand side of the above formula can be written as
xTA(m)k+1x = £ xSoxSfc+2 JJ aSjSj+i.	(5.1)
Sl,...,Sfc+2 C[m]	je[fc]
One summand xSlxSk+1	aSiSi+1 counts perfect matchings in which S1 vertices in
Cm are matched with S1 corresponding white vertices in the adjacent C2m, while the remaining vertices on Cm are matched between themselves. The number of such matchings is xSl. The black vertices i, where i G S2, in C2m, are matched with the white vertices next level in C2m, which is the third circle of the circular graph F(m, k). (We assumed for simplicity that k > 1.) Continue in this way until the last white vertices in the set Sk+2 of Ok+2, which is C2m, are matched with the black vertices in the set Sk+1 of Ok+1. The set of black vertices on Ok+2, denoted by Sk+2 are connected to the cycle Cm, which is the last circle Ok+3. Observe that aSfcSk+1 is the number of perfect matchings in the subgraph C2m when we remove the white vertices Sk and the black vertices Sk+1. Finally, xSk+3 is the number of perfect matchings in the subgraph Cm after removing vertices Sk+3. To summarize, the summand xSlxSk+1 nie[k] aSiSi+1 counts the total number of perfect matchings in F(m, k) where for each j G [k + 2], Sj is the set of white vertices on Oj+1 which is matched to the black vertices in O j.	□
Now we use the above result to count perfect matchings in F(m, k) for small values of
m.
Corollary 5.3. $(F(3, k)) = 3k+2 + 1.
Proof. Note that x has 8 coordinates. There are 4 nonzero coordinates. First x[3] = 1. This corresponds to the situation where we match all three vertices in C3 in the circle O1 to 3 vertices in C6 in the circle O2. But then to have a nonzero perfect matching we need to match the remaining 3 vertices on C6 to 3 vertices in the next level. Continuing in this fashion we deduce that we have only one such perfect matching corresponding to the matching whose edges consist of all edges between different circles. The corresponding summand in the right hand side of formula (5.1) is the contribution of the matrix A3 3 = [1] in A(3). The three nonzero coordinates correspond to x^} = 1 for i = 1,2, 3. These 3 coordinates correspond to the matrix A1,3 in A(3). Clearly Ak,3 = 3k-1A1,3. Hence the contribution of all such terms in (5.1) is equal to 3k+2.	□
Corollary 5.4.
$(F(4, k)) = 2(2 + V2)fc+1 + 2(2 - V2)fc+1 + 2k+3 + 1.
Proof. We need to consider only the cases when S has cardinality 0,2,4. If S1 = 0, then xS1 = 2. In this case we need to choose S1 = ... = Sk+2 = 0. So we match the edges on the circles O1,..., Ok+3. The number of perfect matchings for each even cycle is 2.
A. Behmaram et al.: Matchings in m-generalized fullerene graphs
311
Hence the total number of such matchings is 2k+3. Now suppose that Si = [4]. Then Si = ... = Sk+1. So we match only the vertices between the circles O1,..., Ok+3. The number of such perfect matchings is 1. Suppose finally that |S11 = 2. So xSl =1 if and only if the two vertices in S1 are neighbors. In other words, two vertices in S1 form an edge in C4. Let us write down the 6 x 6 matrix A2,4 with rows and columns indexed by 2-element subsets of [4] in the following order: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}.
So A2,4 is an irreducible matrix with a positive diagonal. Its characteristic polynomial
x6 - 6x5 + 14x4 - 24x3 + 28x2 - 24x + 8 factors as (x2 - 4x + 2)(x2 - 2x + 2)(x2 + 2). It has two real eigenvalues, 2 + %/2 and 2 - %/2, and two pairs of conjugated complex eigenvalues. Hence, $(F(4, k)) will be dominated by the (k + 1)-st power of the spectral radius, (2 + A/2)fc+1, with the correction term (2 - A/2)fc+1. The claim now follows by adding all contributions.	□
Corollary 5.5.
Proof. Note that xs > 0 if and only if |S| = 1,3,5. For |S| = 5, i.e. S = [5] we deduce that the number of perfect matchings is 1 , which is achieved by matching the adjacent vertices on different circles. This gives us the last term in the right hand side. Consider now the case |S| = 1. First choose any vertex on O1, which is C5. There are 5 choices. Connect this vertex to a white vertex on O2, which is C10. Now choose any black vertex on O2. Delete these two vertices. We obtain one or two paths of even length which have 1 perfect matching. That is, a{j},{j} = 1 for any i, j G [5]. Continuing in this manner we obtain the number of perfect matchings to be 5k+2, the dominant term on the right hand side. The middle term is obtained by considering the eigenvalues of A3,5, the 10 by 10 matrix whose row and columns are indexed by lexicographically ordered 3-element subsets of [5].
A-2,4
1110 0 0 0 11110 001011 10 0 110 110011 010101
(5.2)
+ 1.
A3,5
1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1
(5.3)
□
312
Ars Math. Contemp. 11 (2016) 403-413
Corollary 5.6.
$(F(6,k)) - (2(2 + V3))fc+2.
Proof. The dominant term is the power of the spectral radius of A2,6, a matrix of order 15 that we omit.	□
Results of Corollaries 5.3 and 5.4 are new. Corollary 5.5 is in agreement with results of Sachs, Hansen and Zheng from [23], while Corollary 5.6 agrees with findings in [22].
6 The entropy of the family F(m,k), k G N
Recall that the graph F(m, k) has 2m(k + 2) vertices. The dimer entropy h(m) of the family F(m, k) is defined as
log$(F (m,k)) h(m) :=l7-T 2m(k + 2) .
(See [9-11].) From the previous section we deduce
log p(m)
h(m) =
2m
Equivalently, it says that the number of perfect matchings in F(m, k) for m fixed and k > 1 is of order ekh(m).
Empirical results suggest that narrow nanotubes have the largest number of perfect matchings among all fullerene graphs on 10k vertices. That motivates us to advance the following conjecture.
Let n be an integer number greater than 11 so that there is a fullerene with 2n vertices. Denote by ^2n the maximal number of perfect matchings in all fullerene graphs with 2n vertices. Define
, log M2n hF := limsup —--.
n^w 2n
We conjecture that hF = h(5).
Similar claim seems plausible also for m-generalized fullerenes. Fix an integer m > 3, m = 5,6. Let ^2m(k+2),m be the maximal number of perfect matchings in all m-generalized fullerene graphs with 2m(k + 2) vertices. Define
, , S	log M2m(fc+2)
hF (m) :=lim\S^UP 2m(k + 2) . We conjecture that hF(m) = h(m).
References
[1]	N. Alon and S. Friedland, The maximum number of perfect matchings in graphs with a given degree sequence, Electron. J. Combin. 15 (2008), Note 13, 2.
[2]	V. Andova, D. Blenkus, T. Doslic, F. Kardos and R. Skrekovski, On diameter of nanotubical fullerene graphs, MATCH Commun. Math. Comput. Chem. 73 (2015), 529-542.
[3]	V. Andova, T. Doslic, M. Krnc, B. Luzar and R. Skrekovski, On the diameter and some related invariants of fullerene graphs, MATCH Commun. Math. Comput. Chem. 68 (2012), 109-130.
A. Behmaram et al.: Matchings in m-generalized fullerene graphs
313
[4]	N. Basic and T. Pisanski, Iterated altans and their properties, MATCH Commun. Math. Comput. Chem. 74 (2015), 645-658.
[5]	A. Behmaram and S. Friedland, Upper bounds for perfect matchings in Pfaffian and planar graphs, Electron. J. Combin. 20 (2013), Paper 64, 1-16.
[6]	T. Doslic, Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages, J. Math. Chem. 33 (2003), 103-112, doi:10.1023/A:1023299815308.
[7]	T. Doslic, Leapfrog fullerenes have many perfect matchings, J. Math. Chem. 44 (2008), 1-4, doi:10.1007/s10910-007-9287-x.
[8]	T. Doslic, Finding more perfect matchings in leapfrog fullerenes, J. Math. Chem. 45 (2009), 1130-1136, doi:10.1007/s10910-008-9435-y.
[9]	S. Friedland, E. Krop, P. H. Lundow and K. Markstrom, On the validations of the asymptotic matching conjectures, J. Stat. Phys. 133 (2008), 513-533, doi:10.1007/s10955-008-9550-y.
[10]	S. Friedland, E. Krop and K. Markstrom, On the number of matchings in regular graphs, Electron. J. Combin. 15 (2008), Research Paper 110, 28.
[11]	S. Friedland and U. N. Peled, Theory of computation of multidimensional entropy with an application to the monomer-dimer problem, Adv. in Appl. Math. 34 (2005), 486-522, doi:10. 1016/j.aam.2004.08.005.
[12]	B. Grunbaum and T. S. Motzkin, The number of hexagons and the simplicity of geodesics on certain polyhedra, Canad. J. Math. 15 (1963), 744-751.
[13]	I. Gutman, Altan derivatives of a graph, Iranian J. Math. Chem. 5 (2014), 85-90.
[14]	D. Holton and M. D. Plummer, 2-extendability in 3-polytopes, in: Combinatorics (Eger, 1987), North-Holland, Amsterdam, volume 52 of Colloq. Math. Soc. Janos Bolyai, pp. 281-300, 1988, doi:10.1016/0003-6870(88)90075-0.
[15]	F. Kardos, A computer-assisted proof of a barnette's conjecture: Not only fullerene graphs are hamiltonian, arXivpreprint arXiv:1409.2440 (2014).
[16]	F. Kardos, D. Kral, J. Miskuf and J.-S. Sereni, Fullerene graphs have exponentially many perfect matchings, J. Math. Chem. 46 (2009), 443-447, doi:10.1007/s10910-008-9471-7.
[17]	F. Kardos and R. Skrekovski, Cyclic edge-cuts in fullerene graphs, J. Math. Chem. 44 (2008), 121-132, doi:10.1007/s10910-007-9296-9.
[18]	D. J. Klein and X. Liu, Theorems for carbon cages, J. Math. Chem. 11 (1992), 199-205, doi: 10.1007/BF01164204, concepts in mathematical chemistry (Bled, 1991).
[19]	D. Kral, O. Pangrac, J.-S. Sereni and R. Skrekovski, Long cycles in fullerene graphs, J. Math. Chem. 45 (2009), 1021-1031, doi:10.1007/s10910-008-9390-7.
[20]	H. W. Kroto, J. R. Heath, S. C. O'Brien, R. F. Curl, R. E. Smalley et al., C 60: buckminster-fullerene, Nature 318 (1985), 162-163.
[21]	K. Kutnar and D. Marusic, On cyclic edge-connectivity of fullerenes, Discrete Appl. Math. 156 (2008), 1661-1669, doi:10.1016/j.dam.2007.08.046.
[22]	J. Qian and F. Zhang, On the number of Kekule structures in capped zigzag nanotubes, J. Math. Chem. 38 (2005), 233-246, doi:10.1007/s10910-005-5410-z.
[23]	H. Sachs, P. Hansen and M. Zheng, Kekule count in tubular hydrocarbons, MATCH Commun. Math. Comput. Chem. 33 (1996), 169-241.
[24]	R. Thomas, A survey of Pfaffian orientations of graphs, in: International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zurich, pp. 963-984, 2006.