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) 353-379
Mathematical aspects of fullerenes
Vesna Andova *
Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ., Ruger Boskovik 18, 1000 Skopje, Macedonia

Frantisek Kardos LaBRI, University of Bordeaux, 351, cours de la Liberation, 33405 Talence, France
Riste Skrekovski
4=
Faculty of Mathematics and Physics, University of Ljubljana,
Jadranska 21,1000 Ljubljana, Slovenia, Faculty of Information Studies, 8000 Novo Mesto, Slovenia, Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Glagoljaska 8, 6000 Koper, Slovenia
Received 9 April 2015, accepted 8 February 2016, published online 25 March 2016
Fullerene graphs are cubic, 3-connected, planar graphs with exactly 12 pentagonal faces, while all other faces are hexagons. Fullerene graphs are mathematical models of fullerene molecules, i.e., molecules comprised only by carbon atoms different than graphites and diamonds. We give a survey on fullerene graphs from our perspective, which could be also considered as an introduction to this topic. Different types of fullerene graphs are considered, their symmetries, and construction methods. We give an overview of some graph invariants that can possibly correlate with the fullerene molecule stability, such as: the bipartite edge frustration, the independence number, the saturation number, the number of perfect matchings, etc.
Keywords: Fullerene, cubic graph, planar graph, topological indices. Math. Subj. Class.: 05C12, 05C90, 92E10, 94C12
* Partially supported by Slovenian ARRS Program P1-00383 and Creative Core - FISNM - 3330-13-500033. E-mail addresses: vesna.andova@gmail.com (Vesna Andova), frantisek.kardos@labri.fr (Frantisek Kardos), skrekovski@gmail.com (Riste Skrekovski)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
354
Ars Math. Contemp. 11 (2016) 247-254
1	Introduction
The first fullerene molecule, with a structure like a football, was discovered experimentally in 1985 by Kroto et al. [75]. The discovered molecule C60, is comprised only by 60 carbon atoms, and it resembles the Richard Buckminster Fuller's geodetic dome, therefore it was named buckminsterfullerene. Until that moment the only all-carbon structures the modern science was aware of were graphite and diamond. In 1991, the Science magazine pronounced the buckminsterfullerene for the "Molecule of the year", and later in 1996 the discovery of C60 was rewarded with the Nobel price for chemistry. Soon after the experimental discovery of the buckminsterfullerene, its existence in the nature was confirmed along with similar structures having 70, 76, 78, 82, 84, 90, 94, or 96 carbon atoms. Each of these all-carbon molecules have polyhedral structure, and all faces of the polyhedron are either pentagons or hexagons. All polyhedral molecules made entirely of carbon atoms are called fullerenes. The discovery of the Buckminsterfullerene marked the birth of fullerene chemistry and nanotechnology, but at the same time the fullerenes were studied from different perspectives. The experimental work was paralleled by theoretical investigations, applying the methods of graph theory to the mathematical models of fullerene molecules called fullerene graphs.
The study from graph theoretical point of view has been motivated by a search for invariants that will correlate with their stability as a chemical compound. Later graph invariant were used in order to predict the physical and chemical properties of a fullerene compound. A number of graph-theoretical invariants were examined as potential stability predictors with various degrees of success [42, 29]. Graph theory invariants that have been considered as possible stability predictors are: the bipartite edge frustration, the independence number, the saturation number, the number of perfect matchings, etc. As a result of those investigations, we have achieved a fairly thorough understanding of fullerene graphs and their properties. However, some problems and questions still remain open [25, 78,49]. Special place among them have several interesting conjectures made by Graffiti, a conjecture making software [41].
2	Fullerene graphs
Fullerenes can also be seen as graphs, vertices represent atoms, and edges represent bonds between atoms. A fullerene graph is a 3-connected 3-regular planar graph with only pentagonal and hexagonal faces. In what follows fullerene graphs will be also called fullerenes. Due to Whitney's Theorem (1933) simple planar 3-connected graphs have a unique planar embedding, and therefore the same holds for fullerene graphs. By Euler's formula follows the next property of fullerene graphs.
Proposition 2.1. The number of pentagonal faces in a fullerene graph is 12.
The previous result gives no restriction on the number of hexagons. Griinbaum and Motzkin [59] showed that fullerene graphs exist for any number of hexagonal faces except for 1, i.e., they proved the following.
Theorem 2.2. Fullerene graphs with n vertices exist for all even n > 24 and for n = 20.
Usually in chemistry the fullerene molecule on n vertices is denoted by Cn. Although the number of pentagonal faces is negligible compared to the number of hexagonal faces, their layout is crucial for the shape of the corresponding fullerene molecule. Notice that as
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
355
the number of vertices (hexagons) grows, the number of fullerenes increases as well. For example the fullerenes on 20, 24 and 26 vertices have the unique layout, but the fullerene C40 has 40 isomers, while the buckminsterfullerene has 1812 different isomers. There is a believe that number of fullerenes on n vertices is of order ©(n9), see Fowler and Manolopoulos in [45] and Cioslowski [22] for more details.
2.1 Types of fullerene graphs
Regarding the position of the pentagons we distinguish several types of fullerene graphs. The fullerene graphs where no two pentagons are adjacent, i.e., each pentagon is surrounded by five hexagons, satisfy the isolated pentagon rule or shortly IPR, and they are considered as stable fullerene compounds [76]. Cioslowski [22] stated the following conjecture concerning the number of IPR fullerenes on n vertices.
Conjecture 2.3. For all n > 106, the number of the IPR fullerene isomers with n carbon atoms is bracketed by the total numbers of isomers of the Cn-50 and Cn-48 fullerenes.
If all pentagonal faces are "equally distributed", we obtain fullerene graphs of icosahe-dral symmetry, whose smallest representative is the dodecahedron. The dodecahedron is the only icosahedral fullerene that does not satisfy the IPR. On the other hand, if the pentagonal faces are grouped in two clusters by six, we obtain nanotubical fullerene graphs. Now, we consider these types of graphs separately.
2.1.1 Icosahedral fullerene graphs
The common feature of all icosahedral fullerenes is their geometrical shape. The simplest icosahedral fullerene graph is the dodecahedron, C20; the next one is the famous buckminsterfullerene C60. Caspar and Klug [21] and Coxeter [23] suggested a method that constructs the duals of the icosahedral fullerene graphs: geodesic domes, i.e., triangulations of the sphere with vertices of degree 5 and 6.
Figure 1: Construction of a (2,3)-triangle, a metaface of a (2, 3)-icosahedral fullerene graph. The vertices of the equilateral triangle ABC are centers of pentagons.
Goldberg [54] observed that all icosahedral fullerene graphs can be obtained by mapping (a part of) the hexagonal grid onto the triangular faces of an icosahedron. He also showed that the number of vertices n in a fullerene of icosahedral symmetry can be determined by two integers i and j by the following equation, conveniently called the Goldberg equation
n = 20(i2 + ij + j2).	(2.1)
356
ArsMath. Contemp. 11 (2016)353-379
The integers i and j in the Goldberg equation are in fact the components of a two-dimensional Goldberg vector G = (i, j), sometimes also called Coxeter coordinates. We always assume that 0 < i < j and 0 < j in order to avoid the mirror effect. This vector determines the distance and positions of the vertices of the (i, j)-triangle in the hexagonal lattice, see Figure 1 for a construction method of an (2, 3)-triangle. Precisely 20 such (i, j)-triangles produce an (i, j)-icosahedral fullerene in a manner shown on Figure 2. The vertices of the triangles are centers of the 12 pentagons of the fullerene graph. Observe that the dodecahedron is the (0,1)-icosahedral fullerene, whereas the buckminsterfullerene is the (1,1)-icosahedral fullerene.
If i = j or j = 0, then the (i, j)-icosahedral fullerene graph has mirror symmetry, its symmetry group is (isomorphic to) Ih, the full symmetry group of a regular icosahedron. Otherwise, its symmetry group is (isomorphic to) I, the group of rotations of a regular icosahedron.
A	A	A	A	A
E	E	E	E	E
Figure 2: A (2, 3)-icosahedral fullerene. Its triangular faces are constructed as on Figure 1. The vertices with the same label coincide.
2.1.2 Fullerenes with other symmetry groups
A symmetry group of a fullerene can contain an m-fold rotational axis only for m = 2, 3, 5, and 6. This makes the list of all possible symmetry groups finite; it consists of 36 groups:
icosahedral: Ih, I; tetrahedral: Th, Td, T; prismatic: D^h, D3h, D2h; antiprismatic: D6d, D5d, D^,
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
357
dihedral: De, D5, D3, D2; skewed: S12, S10, S4; rotation-reflection: C6h, C5h, C3h, C2h; pyramidal: C6v, CL, C3V, C2v; rotation only: C6, C5, C3, C2, nonaxial: Cs, Ci, C1.
Figure 3: Examples of smallest fullerenes with prismatic, antiprismatic and dihedral symmetry groups.
It was proved that whenever a five-fold or six-fold rotational axis is present, the structure of the fullerene implies a perpendicular twofold rotational axis [46]. This means that the groups S12, S10, C6h, C5h, C6v, C5v, C6, and C5 only occur as subgroups of icosahe-dral, prismatic, antiprismatic, or dihedral groups Ih, I, D6h, D5h, D6d, D5d, D6, and D5. The final list of 28 fullerene symmetry groups is therefore:
Ih, I; Th, Td, T; D6h, D5h, D3h, D2h D6d, Dm, D3d, D2d;
D6, D5, D3, D2; S6, S4; C3h, C2h; , C2v; C3, C2; Cs, Ci, C1.
As shown in [46], fullerenes of each group can be found among all fullerenes on n vertices 20 < n < 140. From a fullerene with a given symmetry group, by a leapfrog
358
Ars Math. Contemp. 11 (2016) 247-254
transformation (see Figure 9) one can construct a bigger fullerene with the same symmetry group. Thus, there is an isolated pentagon fullerene for each of the 28 symmetry groups. Symmetry groups for small fullerenes are considered in [8] and [45]. In the later work the smallest fullerene is found for each possible symmetry group, see Figures 3, 4, and 5. All fullerenes with symmetry group of at least 10 elements, i.e., Ih, I, Td, Th, T, D6h, D6, D5h, D5d or D5, are catalogued in [57].
2.1.3 Nanotubical fullerene graphs
While the icosahedral fullerenes have "spherical" shape, there is a class of fullerene graphs of tubular shapes, called nanotubical graphs or simply nanotubes. From the aspect of mathematics they are not well defined. However, they are cylindrical in shape, with the two ends capped with a subgraph containing six pentagons and possibly some hexagons. The cylindrical part of a nanotube can be obtained by rolling a planar hexagonal grid. The way the grid is wrapped is represented by a Goldberg vector (i, j), called also the type of the nanotube. See Figure 6 for an example of the construction of the cylindrical part of a nanotube, also called an open nanotube.
For a given nanotube of type (i, j), the sum i + j is called perimeter of the nanotube. The smallest possible perimeter is 1, but the open nanotube (0,1) is not simple. The open nanotubes with perimeter 2 are the nanotubes (1,1) and (0,2), but these graphs are not 3-connected. The smallest perimeter such that the graph is 3-connected is 3. On the other side in nature, the thinnest (open) nanotube is (2, 2)-nanotube [95]. Since fullerene graphs are cyclically 5-edge connected [28] it is not possible to close an open nanotube with perimeter smaller than 5. Even more there is a cap with six pentagons that closes (0, 5)-nanotube, but there are no caps for (1,4), and (2,3)-nanotube. For all vectors (i, j) with i + j > 6 there exists a nanotube. A (0,5)-nanotube is depicted on Figure 13.
Notice that the caps of nanotubes are not well defined. One can find (infinitely) many caps for an (i, j)-nanotube by inserting or removing a hexagonal face from a patch with six pentagons that is a subgraph of the nanotube. On the other hand Brinkmann et al. [15] showed that from all possible caps for an (i, j)-nanotube, we can always choose a "nice" cap. We call a cap P nice if its boundary can be represented by the sequence (23)®(32)j, and at least one pentagon is incident to the boundary of P. An edge on the boundary is called i-j edge if its end vertices are of degree i and j, respectively. Observe that if
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
359
Figure 5: Examples of smallest fullerenes with other symmetry groups.
i > j > 0 the boundary of a nice cap has precisely one 2-2 edge and one 3-3 edge. If j = 0, all the edges on the boundary are 2-3 edges. Starting with any cap, and inserting or removing a finitely many hexagons we can construct a nice cap. If the number of vertices of the nanotube is large enough compared to i and j, we can always choose the two caps such that they are nice and disjoint.
Although the caps are not well defined, a result from Brinkmann et al. [15] provides the existence of "nice" caps.
Theorem 2.4. Let F be a long enough (i,j )-nanotube. Then, among all possible caps of F, there are caps such that their border can be represented by the sequence (23)®(32)j.
Let P(i, j) be the set of all possible nice caps for an (i, j)-nanotube. A nice cap according to Brinkmann et al. [15] can be transformed into a nice cap according to current definition by inserting less than i + j hexagons. Brinkmann et al. in [15, 13] give a method for constructing all possible nice caps for an (i, j)-nanotubes. Due to this result we have that P(i, j) is a finite set.
Nanotubes with i = 0 are called zig-zag nanotubes, and the ones with i = j are called armchair nanotubes. These are the only types of nanotubes where the cylindrical part has a mirror symmetry. The buckminsterfullerene C60 can be viewed as the smallest nanotube of type (5,5), see Figure 7. It is also the smallest nanotube with the caps satisfying the IPR.
360
Ars Math. Contemp. 11 (2016) 247-254
Figure 6: An example of a (2,4) nanotube. The hexagons denoted equally overlap.
There are IPR nanotubes for all types (i, j) with i + j > 11 and for (5,5), (0, 9), (0,10), (1,9), and (2, 8).
2.2 Pentagonal-hexagonal patches
Not every fullerene graph is a nanotube. Therefore, subgraphs with similar structure as the nanotube caps were studied in order to facilitate fullerene generation and enumeration.
A patch is a 2-connected plane graph with only pentagonal or hexagonal faces, except maybe one (the unbounded) face. All interior vertices of a patch are of degree 3, and all vertices of the exceptional face, which we consider as the outer face, are of degree 2 or 3. Let P be a patch with h hexagons and p pentagons. All the vertices incident to the outer face - the boundary of P, b(P) - are of degree two or three; let the number of vertices of degree two and three on the border of P be denoted by n2,b(P) and n3,b(P), respectively. Clearly for the size of the border holds |b(P)| = n2,b(P) + n3,b(P). Bornhoft et al. [11], and independently Kardos et al. [70] give the following relation between the number of vertices on the border and the number of pentagons in the patch.
Proposition 2.5. Let P be a patch with p pentagons. Then, |b(P) | = 2n3,b(P) +6 — p.
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
361
The last result gives the relation between n2,b(P) and n3,b(P), i.e., n2,b(P)-n3,b(P) = 6 - p. If P is a patch with six pentagons, then the number of vertices of degree 2, and the number of vertices of degree 3 are equal, not depending on the size or shape of P. Observe that if one ring of hexagons around P is added, the length of the border does not change. If P has less than six pentagons, then after adding a ring of hexagons around P, the number of vertices on the outer face will increase, and vice versa if P has more than six pentagons after adding the ring of hexagons the number of vertices on the outer face will decrease. This result confirms that in order to preserve the constant perimeter of the tube in the nanotubes, each cap must have precisely six pentagons.
The degrees of the vertices on the boundary can be regarded as a sequence of length |b(P) | whose elements are 2 and 3.
Inserting a face (pentagon or hexagon) to a patch P means creating a new patch from P with one face more than P such that the new face is incident to at least one edge from the outer face of P. Removing a face is an inverse operation of the insertion.
Let the set of all patches with h hexagons andp pentagons be denoted by Pp,h. There is a "monotone" method (with respect to the length of the patch boundary) for construction of all possible patches with at most 5 pentagons and given upper bound on the border starting with pentagonal or hexagonal face.
Proposition 2.6. Each patch P with h hexagons and p < 5 pentagons can be obtained by adding a pentagon or hexagon to some patch P' G Pp-1 h UPph_i such that |b(P)| >
|b(P ')|.
Bornhoft et al. [11] determined the minimum and maximum possible boundary lengths of pentagon-hexagon patches with h hexagons and p < 6 pentagons. They show that the minimal boundary length is obtained for a face spiral patch Sp,h starting with all p pentagons and continuing with the hexagons. A maximum boundary length is obtained for a patch with a tree as its inner dual. Let min(p, h) and max(p, h) be the minimal boundary length and maximal boundary length of a patch with p pentagons and h hexagons respectively. The following theorem from [11] determines which intermediate values can occur as a boundary length of a patch with p pentagons and h hexagons.
Theorem 2.7. For p < 6 there exists a patch P with p pentagons and h hexagons and a boundary length b if and only if min(p, h) < b < max(p, h) and b = p (mod 2).
3 Construction of fullerene graphs
As said before for a fullerene on n vertices, there should be ©(n9) isomers. Searching for an efficient method that constructs all possible isomers on n vertices resulted in several different approaches. Here, we consider the spiral method, Stone-Wales rearrangement, and patch replacement transformation.
By Coxeter and Coldberg constructions, one can construct icosahedral fullerene as described in Section 2. A modification of the same method can be used in order to construct other fullerenes with smaller number of symmetries, but as the number of symmetries decreases, this construction method gets more complicated. When icosahedral fullerenes are constructed all 20 triangles are the same and equilateral, but in the case of fullerenes with lower symmetries the triangles can be isosceles or scalene. This implies that the triangles are not equal, and therefore more parameters are needed, what makes this method compli-
362
Ars Math. Contemp. 11 (2016) 247-254
cated. A Coxeter method for construction of tetrahedral and dihedral fullerenes is given in [80].
Fullerenes can be constructed from other fullerenes with two simple techniques; rearranging the faces known as Stone-Wales rearrangement, or by adding two new vertices by Endo-Kroto insertion:
•	The Stone-Wales rearrangement [90] is a transformation that constructs an isomer of a fullerene graph. This transformation rearranges the pentagons and hexagons in a patch with two pentagons and two hexagons without changing the number of vertices as shown on Figure 8.
•	The Endo-Kroto C2 insertion [38] is a transformation that results a bigger fullerene, i.e., a fullerene on n + 2 vertices. This transformation is possible only if the fullerene contains a patch as on Figure 8 (c).
Stone-Wales rearrangement	Endo-Kroto C2 insertion
Figure 8: Stone-Wales rearrangement and Endo-Kroto C2 insertion. Stone-Wales rearrangement: replaces the patch (a) by the patch (b). Endo-Kroto C2 insertion: replaces the patch (c) by the patch (d), and inserts two new vertices.
It is easy to see that these two transformations do not allow to construct all the fullerene graphs. Moreover, since the pentagons can be arbitrarily far away from each other, no finite set of transformations can be sufficient to generate all the fullerene graphs. However, later it was shown [47] that these two transformations are special cases of more general transformations based on patch replacement considered later in Subsection 3.2.
Besides these methods, the leapfrog operation of a fullerene graph is another method that produces (bigger) fullerenes. The leapfrog operation of a fullerene graph G, L(G), is usually used for construction of bigger and isolated pentagon fullerenes. The leapfrog graph L(G) is obtained by truncating the dual of the fullerene graph G, i.e.,
L(G) = Tr(Du(G)),
where Du(G) is dualization, and Tr(G) is truncation of the graph G. At the same time leapfrog operation can be viewed as a composition of stelliation St(G), and dualization
Du(G),
L(G) = Du(St(G)).
The operations stellisation, dualization and truncation for a given graph are defined as follows:
• Stellisation, St(G), adds a vertex in the center of each face of a planar graph G, and connects the new vertex with each boundary vertex of the corresponding face. Notice that this operation is also a triangulation.
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes	363
Figure 9: (a) Dodecahedron and its dual graph. (b) Buckminsterfullerene graph obtained with the leapfrog operation on the dodecahedron, truncating dodecahedron's dual.
•	Dualization of a graph G is the operation that produces the dual of G. Recall that the dual graph of a planar graph G, Du(G), is a graph with vertices corresponding to each face of G. Two vertices in Du(G) are adjacent if the corresponding faces in G share an edge.
•	Truncation, Tr(G), of a plane graph G is an operation that adds two new vertices on each edge, and then removes the vertices of G. Two vertices are adjacent if they are added to the same edge of G or they belong to two consecutive edges incident to the same vertex of G. The truncation of a polyhedron cuts off one third of each edge at each of both ends.
It is easy to see that L(G) is a fullerene graph on |2E(G) | vertices. Even more L(G) is an isolated pentagon fullerene. The leapfrog graph of the dodecahedron C20 is the buckminsterfullerene C60, see Figure 9.
3.1 Spiral method
A face spiral is an ordering of the faces of the fullerene graph such that each face in the spiral has a common edge with its predecessor and successor on the spiral (except the first and last faces). The face spiral ordering is shown in Figure 10. A face spiral sequence is a sequence of twelve different integers that correspond to the position of the twelve pentagons in the fullerene. The first face in the face spiral has the position 0, see Figure 10. The face spiral sequence can be also be given as a sequence of twelve fives and a number of sixes, and the position of the fives (resp. sixes) corresponds to the position of the pentagons (resp. hexagons) in the spiral ordering.
The spiral conjecture states that the surface of a fullerene polyhedron can be unwrapped as a continuous spiral strip of adjacent faces, i.e., every fullerene has a face spiral. Although each fullerene with at most 176 vertices has at least one face spiral [12] and fullerenes with icosahedral symmetry have a spiral [48], the conjecture is not true in general, since there are unspiral fullerenes with more than 380 vertices [79].
364
Ars Math. Contemp. 11 (2016) 247-254
An analog to the face spiral is the vertex spiral. A spiral is a path that starts with an edge and always takes the most left (resp. right) edge not incident with a vertex that is already on the spiral. A vertex spiral is the numbering of the fullerene vertices in the order they appear on the spiral. Although the vertex spiral is useful for the nomenclature of the fullerene isomers, it is shown that such paths do not always exist. One such example is the (2,1)-icosahedral fullerene C80 [45].
Figure 10: The fullerene on 28 vertices is spiral. The face spiral sequence is 0, 2,4,5,6, 7,
8, 9,10,11,12,14, or 5, 6, 5, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 5.
A spiral method is a consequence of the spiral conjecture. This method simply generates all the sequences of n - 10 sixes and twelve fives as a face spiral of pentagons and hexagons and tries to close them into a fullerene on n vertices. This method was the first attempt to construct all fullerenes on n vertices given by Manolopoulos and May [81]. This algorithm is incomplete, i.e., not every fullerene can be generated with it, since not all fullerenes are spiral [79].
3.2 Expansion operations
Expansion is an operation that replaces a patch from the fullerene graph with a bigger one, and the inverse operation is called a reduction. These operations are also known as patch replacement operations. The simplest patch replacement operations are Stone-Wales rearrangement and Endo-Kroto C2 insertion considered above.
According to the results of Brinkmann et al. [14], no finite set of expansion operations is sufficient to construct all fullerene graphs, starting with a smaller fullerene. Hashem-inezhad et al. [62] defined an infinite set of expansions grouped in three classes: Li for i > 0, Bi,j for i, j > 0 and F expansion. These three expansions are defined as follows:
•	Li expansion. This expansion is defined for i > 0, and uses a path of length 2i + 3 that alternate left-right at each of its vertices and connects two pentagonal faces, also known as it zig-zag path. On Figure 11 the expansion L1 is shown. This expansion starts with a subgraph as shown on Figure 11(a), between the two pentagonal faces there is a ziz-zag path of length 5, and replaces this subgraph with a subgraph shown on Figure 11(b). The Li expansion adds i + 2 new (hexagonal) faces, see Figure 11, i of which are between the two pentagonal faces.
•	Bi,j expansion. Similarly as in the case of Li expansion, the Bijj, i, j > 0 expansion uses a path of length 2i + 2j + 5 between two pentagonal faces. This path alternates
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
365
(a)
(b)
Figure 11: L1 expansion.
left-right for all the vertices on the path except for the vertices 2i + 2 and 2i + 3, these two vertices keep the same orientation, see Figure 12(a). The Bi,j expansion adds i + j + 3 new (hexagonal) faces, i + j + 1 of which are between the two pentagons. Figure 12 shows the expansion B0j1, the subgraph on Figure 12(a) is replaced by the subgraph shown on Figure 12(b).
• F expansion. This expansion adds five hexagonal faces around a cap of a (5,0)-nanotube (see Figure 13) comprised only by six pentagons one of which is central. This operation is equivalent to adding an extra ring in a (5,0)-nanotube.
Observe that the faces drawn completely or the ones labeled by fk or gk are all distinct.
Also, the faces that are not drawn completely can be either pentagons or hexagons.
Using this infinite class of expansions Hasheminezhad et al. showed [62] the following.
Theorem 3.1. Every fullerene except the tetrahedral C28 can be constructed from the dodecahedron C20 using expansions Li, Bi,j, and F. Moreover, if the fullerene is not a (5,0)-nanotube, it can be constructed from C20 using expansions Li and Bij.
Additionally, they showed that all fullerene except the tetrahedral C28 (see Figure 4) and a (5,0)-nanotube (see Figure 13) with up to 300 vertices can be constructed from the dodecahedron and Li expansion.
4 Structural properties of fullerene graphs
As we already mentioned earlier, the distribution of the twelve pentagons determine the shape of the fullerene and its structural properties. In this section, we consider several structural properties of fullerenes, such as: cyclic-edge connectivity, diameter, bipartisa-tion, independence number, specter, etc.
(a)
(b)
Figure 12: Bi,0 expansion.
366
ArsMath. Contemp. 11 (2016)353-379
4.1 Cyclic connectivity
Fullerene graphs are 3-connected and 3-edge connected, but not 4-connected and 4-edge connected. Here we consider cyclic connectivity. Recall that an edge-cut C of G is cyclic if each component of G - C contains a cycle. A graph is cyclically k-edge-connected if at least k edges must be removed to disconnect it into two components such that each contains a cycle. A cyclical edge-cut is trivial if it isolates a single cycle.
A graph G is cyclically k-connected if G can be expressed as a union of two edge disjoint subgraphs Gi and G2, both Gi and G2 containing cycles, and |V(Gi) n V(G2) | > k. The cyclic connectivity of G is the maximum integer k (if exists) such that G is cyclically k-connected. For fullerene graphs, Doslic [28] proved the following theorem.
Theorem 4.1. Every fullerene graph F is cyclically 5-edge-connected.
Clearly, the result is best possible, since each pentagonal face is separated from the rest of the graph by 5 edges. We say that a cyclic 5-edge cut is trivial, if it separates only one pentagonal face, otherwise it is not trivial. Kardos and Skrekovski [71], and Marusic and Kutnar [77] proved that fullerenes which have nontrivial 5-edge-cut are of unique type.
Theorem 4.2. Nanotubes of type (0,5) are the only fullerene graphs with a nontrivial cyclic 5-edge-cut.
A (0, 5)-nanotube is depicted on Figure 13. Observe that every nontrivial cyclic 5-edge-cut of a (0,5)-nanotube separates the two caps (containing six pentagonal faces each) from each other.
Figure 13: A (0, 5)-nanotube.
Similarly, for each nanotube of type (i, j) there are cyclic (i + j)-edge cuts separating the two caps from each other. However, the nanotubes are not the only fullerene graphs with such edge-cuts. An example of a fullerene graph, in which the twelve pentagonal faces are partitioned into four clusters containing 1, 2, 4, and 5 pentagons each, is depicted on Figure 14. It is easy to see that this graph is not a nanotube.
With the next theorem Qi and Zhang [96] determined the cyclic connectivity of fullerene graphs.
Theorem 4.3. Every fullerene graph F is 5-cyclically connected.
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes	367
Figure 14: A half of a fullerene graph, which is not a nanotube, but it is possible to separate six pentagonal face from the other six. In order to obtain the whole graph, the depicted graph is to be glued with its mirror copy along the boundary of the outer face such that the 3-regularity is preserved.
4.2 Diameter of fullerene graphs
For large enough fullerene graphs of spherical shape, the diameter diam(F), the largest distance between any two vertices, is proportional to the radius of the sphere, whereas the number of vertices n is proportional to its surface. Hence, one could expect the diameter of such graphs to be of order ©(^n). On the other hand, for a nanotubical fullerene graph of type (i, j), the diameter diam(F) is proportional to the length of the cylindrical part of the graph, whereas the number of vertices n is proportional to the product of the length of the tube and its circumference i + j. In this case, one could expect the diameter of such graphs is of order ©(n).
A well known result on the degree-diameter problem states that the number of vertices in a planar graph with maximum degree 3 grows at most exponentially with diameter [50]. Let G be a planar graph with maximum degree 3. Then, G has at most
2diam(G)+l _ ^
vertices. This results gives a logarithmic lower bound on the diameter in terms of the number of vertices. The logarithmic character of the bound can be attributed to the presence of faces of large size. It would be reasonable to expect that better lower bounds exist for polyhedral graphs with bounded face size.
As mentioned above, fullerene graphs only have pentagonal and hexagonal faces, and this fact can be used to show [2] that if F is a fullerene graph on n vertices, then diam(F) > V24n - 15/6 - 1/2.
For fullerene graphs with full icosahedral symmetry the diameter has been determined exactly in [6].
Theorem 4.4. The diameter of a fullerene graph with n vertices is of order Q(y/n). If F is a full icosahedral symmetry fullerene (i,j), 0 < i < j, 0 < j, then diam(F) = 4j + 6j — 1.
Observe that an icosahedral fullerene (i, j) has full icosahedral symmetry if i = 0 or i = j. By (2.1) we have that if i = 0, then diam(F) = y/9n/5 — 1, and if i = j, then diam(F) = -^5 n/3 — 1. As the geometrical shape of these fullerenes is "almost spherical" we believed that they have the smallest diameter, so we conjectured that the diameter of any fullerene graph on n vertices is at least |_\/5n/3j — 1. Nicodemos and Stehlik [84] found an infinite class of fullerene graphs of diameter at most \J4n/3, where n is the number of vertices, and disproved this conjecture.
368
Ars Math. Contemp. 11 (2016) 247-254
As far as the upper bound is concerned, the nanotubes of small circumference are the extremal graphs, as says the following theorem [2].
Theorem 4.5. Let F be a fullerene graph with n vertices that is not a (5,0)-nanotube. Then,
/T-,-. n 5 diam(F) < 6 + 2 '
If F is a (5,0)-nanotube on n = 30,40 vertices, then diam(F) = n/5, and if n > 50, then
diam(F) = n/5 — 1.
4.3	Bipartisation of fullerenes
The bipartite edge frustration of a graph G, denoted by y(G), is the smallest cardinality of a set of edges of G that needs to be removed from G in order to obtain a bipartite spanning subgraph. Bipartite edge frustration of a fullerene graph G can be efficiently computed by finding a minimum-weight perfect matching in the pentagon-distance graph of G [35]. In the same reference it was shown that y(G) > 6 for any fullerene graph G and that this bound is sharp.
If the fullerene graph satisfies the isolated pentagon rule, then <^(G) > 12. Furthermore, it was shown that the bipartite edge frustration of fullerene graphs with icosahedral symmetry is proportional to the square root of the number of vertices (see [35, Proposition 11 and Corollary 12]). The numerical computations suggested that it cannot behave worse than that, and prompted the authors conjecture that the independence number of a fullerene graph on n vertices is at most \J 12n/5.
First, Dvorak, Lidicky, and Skrekovski [37] proved a theorem with a weaker multiplicative constant. Later Faria, Klein and Stehlik [43] proved the following celebrating result.
Theorem 4.6. Let G be a fullerene graph with n vertices. Then, y(G) < ^J12 n. Moreover, the equality holds if and only if G is an (i, i)-icosahedral fullerene graph.
The bipartite edge frustration is considered for a possible predictor of molecular stability: If y(G) is close to the upper bound, it means that there is no way to partition the 12 pentagonal faces into six pairs in such a way that the pentagons within the pairs are close to each other.
On the other side, a small value for <^(G) does not say much about the structure of the fullerene graph and about the shape of the molecule. The smallest possible value of y(G) is attained for any fullerene graph where the 12 pentagonal faces can be partitioned into 6 pairs, adjacent to each other. Those pairs of pentagonal faces can be distributed in a widely varied list of possible configurations, leading to molecules of different shapes, including nanotubes of all possible types.
4.4	Independence number
Another invariant tested as a possible stability predictor is the independence number [42]. A set I C V (G) is independent if no two vertices from I are adjacent in G. The cardinality of any largest independent set in G is called the independence number of G and denoted by a(G).
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
369
Independence number of fullerene graphs attracted attention also in the context of study of independent sets as possible models for addition of bulky segregated groups such as free radicals or halogen atoms [10]. Sharp upper bounds on the independence number of n/2 — 2 for general fullerenes and n/2 — 4 for those with isolated pentagons follow by simple counting argument [44]. Lower bounds were gradually improved from (almost) trivial a(G) > n/3 valid for all 3-chromatic graphs to a(G) > 3n/8 [63] valid for all triangle-free planar cubic graphs. A better lower bound of type a(G) > n/2 — C^n, where C is some constant, was first established for icosahedral fullerenes [58].
This observation was formalized in a pair of conjectures in a recent Ph.D. thesis by Daugherty ([25, pp. 96]). The first one states that the minimum possible independence number is achieved on the icosahedral fullerenes that also figure prominently in Theorem 4.6. The second one [25, Conjecture 5.5.2] states the precise form of the conjectured lower bound, i.e., states that a(G) > n/2 — 3\Jn/15. Notice that the constant 3/%/15 is exactly one half of the constant \J 12/5 from Theorem 4.6.
The first result that approaches the conjecture is due to Andova et al. [2]. They showed that a(G) > n/2 — 78.58 Vn for a graph G on n vertices. Finally, using Theorem 4.6, this conjecture was confirmed [43].
Theorem 4.7. Let G be a fullerene graph with n vertices. Then,
Moreover, the equality holds if and only if G is an (i, i)-icosahedral fullerene graph.
Similarly to the bipartite edge frustration, a small value of independence number means that the corresponding polyhedron/molecule is close to being of a spherical shape. On the other hand, a value of a(G) close to n/2 does not say much about the structure or the shape of the molecule.
The relations between diameter and the independence number of fullerenes appear in Conjecture 912 of Graffiti [49]. This conjecture was first established in [2] for large fullerenes using Theorem 4.5 and the lower bound on the independence number established in [2]. Later this theorem was solved by Faria et al. [51] for all fullerenes, which confirms the following nice relation.
Theorem 4.8. If G is a fullerene graph, then
4.5 Spectra of fullerene graphs
An eigenvalue of a graph G is an eigenvalue of its adjacency matrix A(G). The set of all eigenvalues of a graph is called its spectrum. We denote the eigenvalues of G by Ai > A2 > • • • > An. The fullerene graph G is 3-regular, and therefore the largest eigenvalue A1 is always equal to 3. Since the fullerene graphs are not bipartite, the smallest eigenvalue is greater than —3. In this section, we consider the bounds for the smallest eigenvalue An and the second largest eigenvalue of a fullerene graph.
The fullerenes can be arranged in decreasing order by their smallest eigenvalue. This arrangement is known as the smallest-eigenvalue order. It should be noted that there are nonisomorphic fullerenes with the same smallest eigenvalue. Fowler et al. [51] gave the first several fullerene graphs of the smallest-eigenvalue order.
a(G) > 2(diam(G) — 1).
370
Ars Math. Contemp. 11 (2016) 247-254
Theorem 4.9. Amongst all fullerenes the smallest eigenvalue is maximal for the dodecahedron.
The eigenvalues of the dodecahedron [24] are 3, V5,1,0, -2, -%/5 with the multiplicity, 1, 3, 5,4,4, 3, respectively, thus the smallest eigenvalue is -%/5. Observe that there are unique fullerene graphs on 24 and 26 vertices, while there are two non-isomorphic fullerene graphs on 28 vertices, one of which is called tetrahedral fullerene. The smallest eigenvalue of these three fullerene graphs is -1 - %/2 with multiplicity 2, 3, and 4 respectively.
Theorem 4.10. The smallest eigenvalue of a fullerene with at least 28 vertices, which is not isomorphic to the tetrahedral fullerene on 28 vertices is less than -1 - %/2.
The smallest eigenvalue of the second non-tetrahedral fullerene on 28 vertices is « -2.5247.
The above results state that the dodecahedron is the first fullerene in the smallest-eigenvalue order of fullerenes, followed by the unique fullerenes on 24 and 26 vertices and the tetrahedral fullerene on 28 vertices. In the class of isolated pentagon fullerenes the buckminsterfullerene C60 has the smallest eigenvalue [51].
Theorem 4.11. The icosahedral C60 has maximum smallest eigenvalue amongst all isolated pentagon fullerenes.
This result lead to the following result [36]
Theorem 4.12. Among all fullerene graphs with at least 60 vertices, the buckminster-fullerene has the maximum smallest eigenvalue.
Theorem 4.6 and Theorem 4.12 are connected by a result on Laplacian eigenvalues from the monograph by Godsil and Royle ([52, pp. 293]).
Theorem 4.13. Let G be a graph with n vertices. Then bip(G) < n^TO(G).
Here bip(G) denotes the maximum number of edges in a bipartite spanning subgraph of G (hence the number of edges in G minus the bipartite edge frustration), and (G) is the largest Laplacian eigenvalue of G.
Recall that the smallest eigenvalue An (G) of a 3-regular graph G and the largest Laplacian eigenvalue ^(G) of G are related by the following relation ([52, pp. 280]):
An(G) = 3 - Mto(G).
By plugging this into Theorem 4.13 and noting that bip(G) = 3n/2n - y(G) we obtain an upper bound on An (G) in terms of the bipartite edge frustration of G of the form An (G) < -3 + 4y(G)/n. By taking into account the upper bound of <^(G) from Theorem 4.6 we immediately obtain the following upper bound on the smallest eigenvalue of a fullerene graph with n vertices [43].
Theorem 4.14. Let G be a fullerene graph with n vertices. Then,
An(G) < -3 + 8^5^.
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
371
The difference s(G) = 3 - A2 is known as the separator of G or as a spectral cap. Caporossi and Stevanovic [89] showed that the separator 3 - A2 of a fullerene graph is at most 1. Even more, using the well known interlacing theorem about the spectra of a matrix, they proved that the separator of a fullerene with n vertices is at most 1 - 3/n. These two results were conjectured by Graffiti. Related to this Doslic and Reti [34] proved the following theorem:
Theorem 4.15. Let G be a fullerene graph on n vertices. Then, the separator of G is at most 24/n.
5 Matchings
5.1	Number of perfect matchings
Since all carbon atoms are 4-valent, for every atom precisely one of the three bonds should be doubled. Such a set of double bonds is called a Kekule structure in a fullerene. It corresponds to the notion of perfect matchings in fullerene graphs: a matching in a graph G is a set of edges of G such that no two edges in M share an end-vertex. A matching M is perfect if any vertex of G is incident with an edge of M.
The computation of the number of perfect matchings in typical fullerene graphs with a small number of vertices indicates that this number should grow exponentially with n [30]. The first general lower bounds for the number of perfect matchings in fullerene graphs were linear in the number of vertices [26, 27, 99]. The best of them asserts that a fullerene graph with n vertices has at least |"3(n + 2)/4] different perfect matchings [99]. The number of perfect matchings was proved to be exponential for several special classes of fullerene graphs: (0, 5)-nanotubes [77], icosahedral fullerenes [30] or those who are obtained using specific operations [32], before the following general result from [69].
Theorem 5.1. Let G be a fullerene graph with n vertices that has no non-trivial cyclic 5-edge-cut. The number of perfect matchings of G is at least 2 n 61 .
The idea of the proof is to find a perfect matching with (n - 380)/61 non-adjacent resonant hexagons. For such a perfect matching, any subset of the set of resonant hexagons can be switched to obtain a different perfect matching. The bound from Theorem 5.1 is not optimal. Doslic [33] studied the number of perfect matchings in leapfrog fullerene graphs, and found the following.
Theorem 5.2. Let G be a leapfrog fullerene on n vertices. If n is divisible by 4, then the number of perfect matchings is at least Fn/4+1 + n/2, otherwise the number of perfect matchings is at least Fpn/4^+1 + 1, where Fn denotes the n-th Fibonacci number.
A little is known about the relationship between the number of perfect matchings of a fullerene graph and the shape of the corresponding molecule.
5.2	Resonance in fullerene graphs
Let M be a perfect matching in a fullerene graph G. A hexagonal face is resonant if it is incident with three edges in M. A set of disjoint resonant hexagons of G is called resonant pattern (also known as sextet pattern). A fullerene graph is k-resonant if any i, 0 < i < k, disjoint hexagons form a resonant pattern.
372
Ars Math. Contemp. 11 (2016) 247-254
Ye et al. [94] showed that every fullerene graph is 1-resonant. Even more, they proved that every fullerene leapfrog graph is 2-resonant. Since every leapfrog fullerene graph is IPR fullerene, they naturally ask if all IPR fullerenes are 2-resonant. Kaiser et al. [67] answered this question.
Theorem 5.3. Every IPR fullerene graph is 2-resonant.
The fullerene graphs in general are not 3-resonant, i.e., only "small" fullerenes are 3-resonant [94].
Theorem 5.4. If a fullerene graph G is 3-resonant, then \V (G)\ < 60.
The maximum size of a set of resonant hexagons in G is called the Clar number of G, and denoted by c(G). Zhang and Ye [98] showed the following.
Theorem 5.5. A Clar number on fullerene graph with n vertices is at most
n - 12 6
They also showed that there are infinitely many fullerene graphs that attain this upper bound; among all 1812 fullerenes on 60 vertices there are exactly 18 whose Clar number is 8 (including the buckminsterfullerene). This upper bound is achieved for C70, and for infinitely many armchair and zig-zag nanotubes.
The sextet polynomial is defined in [64, 85] as BG(x) = J2m=o r(G, k)xk, where r(G, k) is the number of resonant patterns of G of size k, and m is the Clar number of G. Sereni and Stehlik [88] proved a conjecture made by Zhang and He [97] that for every fullerene graph the value BG( 1) is smaller than the number of perfect matchings in the graph.
A k-regular spanning subgraph of a graph G is called k-factor of G. A fullerene that has a 2-factor form by the boundaries of it faces is called fullerene of Clar type. It is known that if a fullerene is of Clar type, then it has isolated pentagons, i.e., it is a IPR fullerene, see Pisanski [86]. It also holds that the number of fullerenes with n vertices is equal to the number of Clar type fullerenes with 3n vertices.
5.3 Saturation number
The last invariant considered here, the saturation number, is also related to matchings. The existence of perfect (and hence maximum) matchings in fullerene graphs has been established long time ago, and there are many papers concerned with their structural and enumerative properties [27, 69, 72]. Another class of matchings, the maximal matchings, have received much less attention so far, in spite of being potentially useful as mathematical models of dimer absorption. A matching M is maximal if it cannot be extended to a larger matching of G. The saturation number of G, denoted by s(G), is the cardinality of any smallest maximal matching of G. The saturation number of fullerene graphs was studied in [27, 36]. Using the lower bound on the diameter the bounds on the saturation number were improved in [2]. Still that was not the best possible bound of the saturation number of the fullerene graphs. In [3] we prove that the saturation number for fullerenes on n vertices is essentially n/3.
Theorem 5.6. Let F be a fullerene graph on n vertices. Then,
n	n
n - 2 < s(F) < - + O(Vn .
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
373
In order to prove the lower bound of this theorem we used the discharging method. For the upper bound we first used Theorem 4.6, and obtained a bipartite graph F'. Later, we established that F' is an induced subgraph of a hexagonal lattice, or an induced subgraph of a hexagonal tube (defined as on Figure 6). Then we defined a maximal matching on F' such that from each hexagon precisely four vertices are covered by the matching.
6	Hamiltonicity of fullerene graphs
A cycle C of a graph G is hamiltonian if C passes through every vertex of G. Tait [91] in 1884 conjectured that every 3-connected planar cubic graph has a Hamiltonian cycle. Later Tutte [92] showed that this conjecture is false. Back in 1974, Griinbaum and Zaks [60] asked whether 3-connected planar graphs with faces of size p and q, q > p are Hamiltonian for any p and q. It was shown that cubic polyhedral graphs with faces of sizes 3 and 6, or faces of size 4 and 6 are hamiltonian [55, 56].
However, Tait's Conjecture still remained open for fullerene graphs. Barnette [9] made a more general conjecture, he conjectured that all cubic polyhedral graphs with maximum face size at most six having no triangles and no two adjacent quadrangles are hamiltonian. He reduced the conjecture to the case of cubic polyhedral graphs with maximum face size at most six with no triangles nor two adjacent quadrangles, are also known as Barnette graphs. In order to attack the hamiltonicity conjecture for fullerene graphs, long cycles in fullerenes were studied [40, 66, 74, 39]. Marusic [82] showed that for every fullerene graph, its leapfrog fullerene contains a hamiltonian path. Kardos [68] on the other side worked on the more general conjecture, Barnette's Conjecture, and proved the following.
Theorem 6.1. Let G be a 3-connected planar cubic graph with faces of size at most 6. Then G is hamiltonian.
This theorem directly implies implies Taits's Conjecture on fullerene graphs. For the proof of this theorem a more general definition of a 2-factor was introduced, in this case a 2-factor is any spanning subgraph F of a Barnette graph G such that each component of F is a connected regular graph of degree 1 or 2, i.e., an isolated edge (considered here as a 2-cycle) or a cycle. The proof has several major steps. First a 2-factor with many resonant hexagons is found. Then the 2-factor is modified in order to have an odd number of cycles if needed. Finally the resonant hexagons are used to glue all the cycles into a single cycle, i.e., to construct a Hamiltonian cycle. In order to achieve this, a computer program was used.
7	Fullerene graphs and topological indices
Topological indices or molecular descriptors are graph invariants than can correlate with a physical or chemical property of a molecule presented as a graph. The first topological index was introduced by Harry Wiener [93], back in 1947, and afterwards a list of descriptors were introduced such as: the Randic index, the Hosoya index, the Estrada index, the Zagreb Indices, the Szeged index, the Balaban index, etc.
Let G be a graph and u e V(G). Then the distance of u is defined as WG(u) = J2vev(G) dG(u,v), where d(u, v) denotes the distance between the vertices u and v. The Wiener index [93] of a graph G, W(G), is the sum of all the distances in G, i.e., W (G) = £ „, vev(G) d(u,v) = 2 ^«ev(G) WG(u). Hua et al. [65] considered a Wiener
374
Ars Math. Contemp. 11 (2016) 247-254
dimension of one type of (0, 6) -nanotubes, and based on the results they made the following conjecture.
Conjecture 7.1. Let G be afullerene with n vertices. Then, the Wiener index of G, W(G), is of order ©(n3).
The bound of the Wiener index for nanotubical fullerenes are determined in [4]. Suppose that {WG(u) | u G V(G)} = {d1; d2,..., }. Assume in addition that G contains ti pairs of vertices on distance di, 1 < i < k. We say that the Wiener dimension dimW(G) of G is k. Alizadeh et al. [1] have shown that the (0, 5)-nanotubical fullerene graph on 10k (k > 3) vertices has the Wiener dimension k. As a consequence the Wiener index of these fullerenes was obtained. This result confirms Conjecture 7.1 for (0,5)-nanotubes.
Another topological index based on the distance is the Balaban index. This index for a graph G is defined [7] as
j(g) = ——— y , 1 =,
m - n + 2 M,vtE(G) VdG(u) • dG(v)
where n and — are the number of vertices and edges, respectively.
Knor et al. [73] studied the Balaban index for cubic graphs, and determined that the Balaban index tends to zero as the number of vertices increases. More precisely, they showed the following.
Theorem 7.2. Let G be a afullerene graph on n vertices, n > 60. Then J(G) < 25/y/n.
The last result means that Balaban index does not distinguish well the fullerene graphs when they are sufficiently large. Determining the distances on an infinite hexagonal tube [5] the authors [4] show that this approach is much faster for nanotubes.
Let G be a fullerene graph and e = uv an edge in G. Let nv (e) be the number of edges closer to v than to the vertex u. Similarly, let n0(e) be the number of equidistant vertices form u and v. The following indices are base on these invariants. The PI index is defined by PI(G) = J2e=uv [nv(e) + n„(e)j. The Szeged index is topological index introduced by Gutman [61], defined as Sz(G) = J2e=uv nv (e)n„(e). Randic [87] modified this topological index in order to find better applications in chemistry, and the new index was named revised Szeged index. This index is defined by Sz*(G) = J2e=uv [nv(e) + n0 (e)/2] • [n„(e)+ n0(e)/2]. Mottaaghi andMehranian [83] studied PI, Szeged and revised Szeged index for a nanotubical IPR fullerenes on 60 + 12n, n G N, vertices, and found that these indices are of order ©(n2), ©(n3) and ©(n3), respectively.
8 Fullerene generating programs
There are several programs available that can generate fullerenes. Buckygen is a program by Brinkmann, McKay and Goedgebeur for the efficient generation of all nonisomorphic fullerenes. It generates triangulations where all vertices have degree 5 or 6, or its dual representation-fullerene graphs. This program can also be used to generate isolated pentagon rule (IPR) fullerenes. SaGe generates fullerene graphs using the Buckygen generator. The algorithms used in the Buckygen generator are described in [16, 53]. Programs for generation of certain types of graphs are Plantri and Fullgen, both created by Brinkmann and McKay. These programs are based on the papers [17, 19, 20]. GaGe [18] is an Open
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
375
Source program implemented in C and Java, that generates graphs of different types. This
program allows to view selected graphs in various ways or save them in several formats.
House of Graphs provides a count lists of fullerene, fullerenes without a spiral starting at
pentagon, and fullerenes without a spiral. These fullerenes are generated with Buckygen
and Fullgen.
References
[1]	Y. Alizadeh, V. Andova, S. Klavzar and R. Skrekovski, Wiener dimension: Fundamental properties and (5, 0)-nanotubical fullerenes, MATCH Commun. Math. Comput. Chem. 72 (2014), 279-294.
[2]	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.
[3]	V. Andova, F. Kardos and R. Skrekovski, Sandwiching saturation number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 73 (2015), 501-518.
[4]	V. Andova, M. Knor and R. Skrekovski, Distance based indices on nanotubical structures, manucsript 2016.
[5]	V. Andova, M. Knor and R. Skrekovski, Distances on nanotubical structures, manuscript 2016.
[6]	V. Andova and R. Skrekovski, Diameter of full icosahedral-symmetry fullerene graphs, MATCH Commun. Math. Comput. Chem. 70 (2013), 205-220.
[7]	A. T. Balaban, Topological indices based on topological distances in molecular graphs, Pure Appl. Chem. 55 (1983), 199-206.
[8]	D. Babic, D. J. Klein and C. H. Sah, Symmetry of fullerenes, Chemical Physics Letters 211 (1993), 235-241.
[9]	D. Barnette, Conjecture 5, Recent Progress in Combinatorics (Ed. W. T. Tutte), Academic Press, New York (1969).
[10]	O. V. Boltalina and N. A. Galeva, Direct fluorination of fullerenes, Russ. Chem. Rev. 69 (2000), 609-621.
[11]	J. Bornhoft, G. Brinkmann and J. Greinus, Pentagonhexagon-patches with short boundaries, European J. Combin. 24 (2003), 517-529.
[12]	G. Brinkmann and A. W. M. Dress, A constructive enumeration of fullerenes, J. Algorithams 23 (1997), 345-358.
[13]	G. Brinkmann, P. W. Fowler, D. E. Manolopoulos, A. H. R. Palser, A census of nanotube caps, Chem. Phys. Lett. 315 (1999), 335-347.
[14]	G. Brinkmann, J. E. Graver and C. Justus, Numbers of faces in disordered patches, J. Math. Chem. 45 (2009), 263-278.
[15]	G. Brinkmann, U. Nathusius and A. H. R. Palser, A constructive enumeration of nanotube caps, Discrete Appl. Math. 116 (2002), 55-71.
[16]	G. Brinkmann, J. Goedgebeur and B. D. McKay, The generation of fullerenes, J. Chem. Inf. Model. 52 (2012), 2910-2918.
[17]	G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), 323-357.
[18]	G. Brinkmann, O. Delgado Friedrichs, S. Lisken, A. Peeters and N. Van Cleemput, CaGe - a Virtual Environment for Studying Some Special Classes of Plane Graphs - an Update, MATCH Commun. Math. Comput. Chem. 63 (2010), 533-552.
376	Ars Math. Contemp. 11 (2016) 247-254
[19]	G. Brinkmann, B. D. McKay, Construction of planar triangulations with minimum degree 5, Discrete Math., 301 (2005), 147-163.
[20]	G. Brinkmann, S. Greenberg, C. Greenhill, B. D. McKay, R. Thomas and P. Wollan, Generation of simple quadrangulations of the sphere, Discrete Math., 305 (2005), 33-54.
[21]	D. L. D. Caspar and A. Klug, Viruses, Nucleic Acids and Cancer, Williams & Wilkins, Baltimore, 1963.
[22]	J. Cioslowski, Note on the Asymptotic Isomer Count of Large Fullerenes, J. Math. Chem. 52 (2014), 1-4.
[23]	H. S. M. Coxeter, Virus macromolecules and geodesic domes, in: J. C. Butcher (Ed.), A Spectrum of Mathematics, Oxford Univ. Press, Oxford, 1971, pp. 98-107.
[24]	D. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs - Theory and Application, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.
[25]	S. M. Daugherty, Independent Sets and Closed-Shell Independent Sets of Fullerenes, Ph. D. thesis, University of Victoria, 2009.
[26]	T. Doslic, On lower bounds of number of perfect matchings in fullerene graphs, J. Math. Chem. 24 (1998), 359-364.
[27]	T. Doslic, On some structural properties of fullerene graphs, J. Math. Chem. 31 (2002), 187195.
[28]	T. Doslic, Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages, J. Math. Chem. 33 (2003), 103-112.
[29]	T. Doslic, Bipartivity of fullerene graphs and fullerene stability, Chem. Phys. Lett. 412 (2005), 336-340.
[30]	T. Doslic, Fullerene graphs with exponentially many perfect matchings, MATCH Commun. Math. Comput. Chem. 66 (2011), 733-742.
[31]	T. Doslic, Saturation number of fullerene graphs, J. Math. Chem. 43 (2008), 647-657.
[32]	T. Doslic, Leapfrog fullerenes have many perfect matchings, J. Math. Chem. 44 (2008), 1-4.
[33]	T. Doslic, Finding more perfect matchings in leapfrog fullerenes, J. Math. Chem. 45 (2009), 1130-11361.
[34]	T. Doslic and T. Reti, Spectral properties of fullerene graphs, MATCH Commun. Math. Comput. Chem. 66 (2011), 733-742.
[35]	T. Doslic and D. Vukicevic, Computing the bipartite edge frustration of fullerene graphs, Discrete Appl. Math. 155 (2007), 1294-1301.
[36]	T. Doslic, The Smallest Eigenvalue of Fullerene Graphs - Closing the Gap, MATCH Commun. Math. Comput. Chem. 70 (2013), 73-78.
[37]	Z. Dvorak, B. Lidicky and R. Skrekovski, Bipartizing fullerenes, European J. Combin. 33 (2012), 1286-1293.
[38]	M. Endo and H. W. Kroto, Formation of carbon nanofibers, J. Phys. Chem. 96 (1992), 69416944.
[39]	R. Erman, F. Kardoss and J. Misskuf, Long cycles in fullerene graphs, J. Math. Chem. 46 (2009), 1103-1111.
[40]	G. Ewald, On shortness exponents of families of graphs, Israel J. Math. 16 (1973), 53-61.
[41]	S. Fajtlowicz, Written on the Wall (A List of Conjectures of Graffiti), (available from the author on request).
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
377
[42]	S. Fajtlowicz and C. E. Larson, Graph-Theoretic Independence as a Predictor of Fullerene Stability, Chem. Phys. Letters 377 (2003), 485-490.
[43]	L. Faria, S. Klein and M. Stehlik, Odd cycle transversals and independent sets in fullerene graphs, S1AMJ. Discrete Math. 26 (2012), 1458-1469.
[44]	P. W. Fowler, S. Daugherty and W. Myrvold, Independence number and fullerene stability, Chem. Phys. Lett. 448 (2007), 75-82.
[45]	P. W. Fowler and D. E. Manolopoulos, An Atlas of Fullerenes, Oxford Univ. Press, Oxford, 1995.
[46]	P. W. Fowler, D. E. Manolopoulos, D. B. Redmond and R. P. Ryan, Possible symmetries of fullerene stuctures, Chem. Phys. Lett. 202 (1993), 371-378.
[47]	P. W. Fowler and D. B. Redmond, Symmetry aspects of bonding in carbon clusters: the leapfrog transformation, Theor. Chim. Acta 83 (1992), 367-375.
[48]	P. W. Fowler and K. M. Rogers, Spiral codes and Goldberg representations of icosahedral fullerenes and octahedral analogues, J. Chem. 1nf. Comput. Sci. 41 (2001), 108-111.
[49]	P. W. Fowler, K. M. Rogers, S. Fajtlowicz, P. Hansen and G. Caporossi, Facts and conjectures about fullerene graphs: leapfrog, cylindrical and Ramanujan fullerenes, 1n: A. Betten, A. Kohn-ert, R. Laue and A. Wassermann, Editors, Algebraic Combinatorics and Applications, Springer, Berlin (2000).
[50]	E. Friedman and R. W. Pratt, New bounds for largest planar graphs with fixed maximum degree and diameter, preprint (1999).
[51]	P. W. Fowler, P. Hansen and D. Stevanovic, A note on the smallest eigenvalue of fullerenes, MATCH Commun. Math. Comput. Chem. 48 (2003), 37-48.
[52]	C. Godsil and G. Royle, Algebraic Graph Theory, Springer, New York, 2001.
[53]	J. Goedgebeur and B. D. McKay, Recursive generation of IPR fullerenes, J. Math. Chem. 53 (2015), 1702-1724.
[54]	M. Goldberg, A class of multi-symmetric polyhedra, Tohoku Math. J. 43 (1939), 104-108.
[55]	P. R. Goodey, A class of hamiltonian polytopes, J. Graph Theory 1 (1977), 181-185.
[56]	P. R. Goodey, Hamiltonian circuits in polytopes with even sided faces, 1srael J. Math. 22 (1975), 52-56.
[57]	J. E. Graver, Catalog of All Fullerenes with Ten or More Symmetries, in: S. Fajtlowicz, P. W. Fowler, P. Hansen, M. F. Janowitz and F. S. Roberts (Eds.), Graphs and Discovery, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 69 (2005), 167-188.
[58]	J. E. Graver, The independence number of fullerenes and benzenoids, European J. Combin. 27 (2006), 850-863.
[59]	B. Grunbaum and T. S. Motzkin, The number of hexagons and the simplicity of geodesics on certain polyhedra, Canadian J. Math. 15 (1963), 744-751.
[60]	B. Grunbaum and J. Zaks, The excistence of certain planar maps, Discrete Math. 10 (1974), 93-115.
[61]	I. Gutman and A. A. Dobrynin, The Szeged index a success story, Graph Theory Notes New York 34 (1998), 37-44.
[62]	M. Hasheminezhad, H. Fleischner and B. D. Mc Kay, A universal set of growth operations for fullerenes, Chem. Phys. Lett. 464 (2008), 118-121.
[63]	C. H. Heckman and R. Thomas, Independent sets in triangle-free cubic planar graphs, J. Com-bin. Theory B 96 (2006), 253-275.
378
Ars Math. Contemp. 11 (2016) 247-254
[64]	H. Hosoya and T. Yamaguchi, Sextet polynomial. A new enumeration and proof technique for the resonance theory applied to the aromatic hydrocarbons, Tetrahedron Lett. 16 (1975), 4659-4662.
[65]	H. Hua, M. Faghani and A. Ashrafi, The Wiener and Wiener Polarity Indices of a Class of Fullerenes with Exactly 12n Carbon Atoms, MATCH Commun. Math. Comput. Chem. 71 (2014), 361-372.
[66]	S. Jendrol and P. J. Owens, Longest cycles in generalized Buckminsterfullerene graphs, J. Math. Chem. 18 (1995), 83-90.
[67]	T. Kaiser, M. Stehlik and R. Skrekovski, On the 2-resonance of fullerenes, SIAM J. Discrete Math. 25 (2011), 1737-1745.
[68]	F. Kardos, A computer-assisted proof of a Barnettes conjecture: Not only fullerene graphs are hamiltonian, arXiv:140 9.244 0v1.
[69]	F. Kardos, D. Kral', J. Miskuf and J.-S. Sereni, Fullerene graphs have exponentially many perfect matchings, J. Math. Chem. 46 (2009), 443-447.
[70]	F. Kardos, M. Krnc, B. LuZar and R. Skrekovski, Cyclic 7-edge-cuts in fullerene graphs, J. Math. Chem. 47 (2010), 771-789.
[71]	F. Kardos and R. Skrekovski, Cyclic edge-cuts in fullerene graphs, J. Math. Chem. 44 (2007), 121-132.
[72]	D. J. Klein and X. Liu, Theorems on carbon cages, J. Math. Chem. 11 (1992), 199-205.
[73]	M. Knor, R. Skrekovski and A. Tepeh, Balaban Index of Cubic Graphs, MATCH Commun. Math. Comput. Chem. 73 (2015), 519-528.
[74]	D. Kral', O. Pangrac, J.-S. Sereni and R. Skrekovski, Long cycles in fullerene graphs, J. Math. Chem. 45 (2009), 1021-1031.
[75]	H. W. Kroto J. R. Heath, S. C. O'Brien, R. F. Curl and R. E. Smalley, CW Buckminsterfullerene, Nature 318 (1985), 162-163.
[76]	H. W. Kroto, The stability of the fullerenes Cn, with n = 24, 28, 32, 36, 50, 60 and 70, Nature 329 (1987), 529-531.
[77]	K. Kutnar and D. Marusic, On cyclic edge-connectivity of fullerenes, Discrete Appl. Math. 156 (2008), 1661-1669.
[78]	J. Malkevitch, Geometrical and combinatorial questions about fullerenes, in: P. Hansen, P. Fowler, M. Zheng (Eds.), Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 51 (2000), pp. 261-266.
[79]	D. E. Manolopoulos and P. W. Fowler, A fullerene without a spiral, Chem. Phys. Lett. 204 (1993), 1-7.
[80]	D. E. Manolopoulos, P. W. Fowler, R. Taylor, H. W. Kroto and D. R. M. Walton, Faraday communications. An end to the search for the ground state of C84? J. Chem. Soc., Faraday Trans., The Royal Society of Chemistry 88 (1992), 3117-3118.
[81]	D. E. Manolopoulos and J. C. May, Theoretical studies of the fullerenes: C34 to C70, Chem. Phys. Lett. 181 (1991), 105-111.
[82]	D. Marusic, Hamilton Cycles and Paths in Fullerenes, J. Chem. Inf. Model. 47 (2007), 732-736.
[83]	A. Mottaaghi and Z. Mehranian, PI, Szeged and Revised Szeged Indices of IPR fullerenes, Iran. J. Math. Chem. 2 (2011), 87-99.
[84]	D. Nicodemos and M. Stehlik, Fullerene graphs of small diameter, manuscript.
V. Andova, F. Kardoss, R. Sskrekovski: Mathematical aspects of fullerenes
379
[85]	N. Ohkami, A. Motoyama, T. Yamaguchi, H. Hosoya and I. Gutman, Graph-theoretical analysis of the Clar's aromatic sextet: Mathematical properties of the set of the Kekule patterns and the sextet polynomial for polycyclic aromatic hydrocarbons, Tetrahedron 37 (1981), 1113-1122.
[86]	T. Pisanski, Fullereni, Obzornik za matematiko infiziko 41 (1994), 1-32.
[87]	M. Randic, On Generalization of Wiener Index for Cyclic Structures, Acta Chem. Slov. 49 (2002), 483-496.
[88]	J. -S. Sereni and M. Stehlik, On the sextet polynomial of fullerenes, J. Math. Chem. 47 (2010), 1121-1128.
[89]	D. Stevanovic and G. Caporossi, On the (1, 2)-spectral spread of fullerenes, in: S. Fajtlowicz, P. W. Fowler, P. Hansen, M. F. Janowitz, F. S. Roberts (Eds.), Graphs and Discovery, American Math. Soc., Providence, 2005, 365-370.
[90]	A. J. Stone and D. J. Wales, Theoretical studies of icosahedral C60 and some related species, Chem. Phys. Lett. 128 (1986), 501-503.
[91]	P. G. Tait, Listing's Topologie, Philosophical Magazine 17 (1884), 30-46.
[92]	W. T. Tutte, On Hamiltonian circuits, J. London Math. Society 21 (1946), 98-101.
[93]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 1 (1947), 17-20.
[94]	D. Ye, Z. Qi and H. Zhang, On k-resonant fullerene graphs, SIAMJ. Discrete Math. 23 (2009), 1023-1044.
[95]	X. Zhao, Y. Liu, S. Inoue, T. Suzuki, R. O. Jones and Y. Ando, Smallest carbon nanotube is 3 A in diameter, Phis. Rev. Lett. 92 (2004), 125502-1.
[96]	Z. Qi and H. Zhang, A note on the cyclical edge-connectivity of fullerene graphs, J. Math. Chem. 43 (2008), 134-140.
[97]	H. Zhang and J. He, A comparison between 1-factor count and resonant pattern count in plane non-bipartite graphs, J. Math. Chem. 38 (2005), 315-324.
[98]	H. Zhang and D. Ye, An upper bound for the Clar number of fullerene graphs, J. Math. Chem. 41 (2007), 123-133.
[99]	H. Zhang and F. Zhang, New lower bound on the number of perfect matchings in fullerene graphs, J. Math Chem. 30 (2001), 343-347.