IMFM
Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA
Preprint series Vol. 48 (2010), 1114
ISSN 2232-2094
ON THE 2-RESONANCE OF FULLERENES
Tomas Kaiser Matej Stehlik Riste Skrekovski
Ljubljana, February 26, 2010
On the 2-resonance of fullerenes*
Tomas Kaiser^ Matej Stehllk Riste Skrekovski
§
vo
u &
February 24, 2010
Abstract
We show that every pair of hexagons in a fullerene graph satisfying the isolated pentagon rule (IPR) forms a resonant pattern. This solves a problem raised by Ye et al. [SIAM J. Discrete Math. 23(2):2009, p. 1023-1044].
1 Introduction
Fullerenes are cage polyhedral carbon molecules such that all faces are pentagons and hexagons. The icosahedral Ceo, known as the buckminster-fullerene, was predicted by Osawa [14], and discovered by Kroto et al. [10]. A fullerene with no adjacent pentagons is said to satisfy the isolated pentagon rule (IPR), and is called an IPR fullerene. The buckminsterfullerene is the smallest IPR fullerene, and all the stable fullerenes are IPR fullerenes.
CO
Various properties of fullerene molecules can be studied using mathematical tools and results. Thus, fullerene graphs were defined as 3-connected cubic plane graphs with all faces of size 5 or 6. Such graphs are suitable models for fullerene molecules: carbon atoms are represented by vertices of the graph, whereas edges represent bonds between adjacent atoms. It is known that there exists a fullerene graph on n vertices for every even
* Research supported by the bilateral Czech-Slovenian project MEB090805.
^Institute for Theoretical Computer Science (ITI) and Department of Mathematics, University of West Bohemia, Univerzitni 8, 306 14 Plzen, Czech Republic. E-mail: kaisert@kma.zcu.cz. Supported by project 1M0545 of the Czech Ministry of Education and project GACR 201/09/0197 of the Czech Science Foundation.
*CNRS, Laboratoire G-SCOP, 46, avenue Felix Viallet, 38031 Grenoble Cedex 1, France. E-mail: stehlik@kam.mff.cuni.cz.
^Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia.
CSI t
rO
CD
n > 20, n = 22. See the monograph of Fowler and Manolopoulos [4] for more vO	information on fullerenes.
Since carbon atoms in stable molecules are tetravalent, one of the three a-bonds of every atom in a fullerene molecule should be augmented by a n-bond to create a carbon-carbon double bond. A Lewis structure that localises the a- and n-bonds to at most two atoms per bond is called a Kekule structure. It corresponds to the notion of perfect matchings in fullerene graphs: a perfect matching M in a graph G is a set of edges of G such that every vertex of G is incident with precisely one edge of M. It has been shown [1, 7] that fullerene graphs have exponentially many perfect matchings.
Let M be a perfect matching in a fullerene graph G. An even cycle of G is M-alternating if exactly half its edges are in M. A set of disjoint M-alternating hexagons of G is called a resonant pattern. A fullerene graph is k-resonant if any i disjoint hexagons form a resonant pattern, for 0 < i < k.
Ye et al. [17] proved that every fullerene graph is 1-resonant, and that every leapfrog fullerene graph is 2-resonant (see [17] for the definition). The class of leapfrog fullerene graphs satisfies the IPR; this led Ye et al. [17, Open Problem 3.5] to ask whether every IPR fullerene graph is 2-resonant. Here we answer this question in the affirmative by proving the following result.
Theorem 1. Every IPR fullerene graph is 2-resonant.
The theorem is best possible in the sense that no fullerene graph on more than sixty vertices is 3-resonant, as pointed out by Ye et al. [17].
C^
2 Notation and preliminary results
Given a graph G, we let V(G) and E(G) be its vertex set and edge set, respectively. For H C V(G) U E(G), we let G — H be the graph obtained from G by removing the elements in H. Let X, X' C V(G). We define G[X] to be the subgraph of G induced by the vertices in X. We let d(X) be the set of edges of G with exactly one end-vertex in X; if F = G[X] we may also write d(F) for d(X). We denote by E(X,Y) the set of edges with one endvertex in X and the other endvertex in Y; if X = Y we simply write E(X). We denote |E(X, Y)| and |E(X)| by e(X, Y) and e(X), respectively. We say that two faces of a plane embedding of G are adjacent if they
m
CD
share an edge. Vertices and edges contained in the boundary of a face F are said to belong to F or to be on F. Pentagonal and hexagonal faces are referred to simply as pentagons and hexagons.
A graph G is factor-critical if G — v has a perfect matching, for every vertex v E V(G). It is easy to see that every factor-critical graph is connected,
CD
has an odd number of vertices, and has minimum degree two unless it con-
sists of a single vertex. Lovasz [12] characterised factor-critical graphs as those having an 'odd ear decomposition' (see also [13, 15]). The definition of factor-criticality implies that a factor-critical graph is 2-edge-connected. Using the fact that fullerenes are cubic graphs, we obtain the following slightly stronger conclusion:
U
Observation 2. Every non-trivial factor-critical subgraph of a fullerene graph
CD
is 2-connected.

The following theorem may be viewed as a strengthening of Tutte's 1-factor theorem [16]. It is a simple corollary of the Gallai-Edmonds decomposition theorem [3, 5, 6] (see also [13, 15]).
Theorem 3. A graph G has no perfect matching if and only if there exists a subset A C V(G) such that:
0
(i) every component of G — A has a perfect matching or is factor-critical, and
(ii) at least |A| + 1 components of G — A are factor-critical.
A k-edge-cut of G is a set Y of k edges of G for which there exists a set X C V(G) such that Y = d(X). A k-edge-cut Y is cyclic if at least two components of G — Y contain a cycle. The graph G is cyclically k-edge-connected if |E(G)| > k, and it contains no cyclic edge-cuts consisting of fewer than k edges.
Doslic [2] proved that fullerene graphs are cyclically 5-edge connected. Kardos and Skrekovski [9] characterised the cyclic 5- and 6-edge-cuts in fullerene graphs; the cyclic 5-edge-cuts were characterised independently by Kutnar and Marusic [11]. Furthermore, Kardos et al. [8] characterised the cyclic 7-edge-cuts in fullerene graphs. The characterisations together imply the following three lemmas (see Figures 1-3 for illustrations). The proofs are omitted, as they amount to verifying which configurations satisfy the IPR and are factor-critical, resp. have a perfect matching. For a subgraph F of a graph G, the symbol Fc stands for G — V(F).
Lemma 4. Let F be a factor-critical subgraph of an IPR fullerene graph. Then one of the following assertions holds.
(i) |d(F)| = 3 and F or Fc consists of a single vertex;
1	i
(ii) |d(F)| = 5 and F or Fc is a pentagon;
• i
(iii) |d(F)| = 7 and F or Fc consists of a pentagon and an adjacent hexagon;
CD
VD
u
CD
X
Figure 1: Cases (i)-(iii) in Lemma 4.

0 o
1
CO ^
CO CO
CO CD
Jh
CD CO


Figure 2: Case (i) and the three subcases of case (ii) in Lemma 5. (iv) |d(F)| > 9.
Lemma 5. Let F be a subgraph with a perfect matching of an IPR fullerene graph. Then one of the following assertions holds.
(i) |d(F)| = 4 and F or Fc is isomorphic to K2;
(ii) |d(F)| = 6 and F or Fc is a path of length 3, a hexagon, or a pentagon with a pendant edge;
(iii) |d(F)| > 8.
We will also need to extend the characterisations of Lemmas 4 and 5 to subgraphs F with |d(F)| < 6 that are not necessarily factor-critical and may have no perfect matching. There are only two additional cases (cf. Figure 3):
Lemma 6. Let F be a subgraph of an IPR fullerene with |d(F)| < 6. Then F or Fc is either a path of length at most 3, a K13, a cycle of length 5 or 6, or a pentagon with a pendant edge.
U
a
CD U
HH	YY
Figure 3: The two new cases in Lemma 6. The remaining possibilities are the first two graphs in Figure 1 and the graphs in Figure 2.
CD fc
3 The proof of Theorem 1
Before embarking on the proof of Theorem 1, let us give a brief outline of the main argument. Using Theorem 3, we show that deleting any pair of disjoint hexagons from a fullerene graph results in a graph which is 'almost bipartite', in the sense that deleting a prescribed set of vertices and edges gives a bipartite graph. Then, using Lemmas 4 and 5 we show that, apart from one special case, there is always at least one pentagon which does not intersect this prescribed set; a contradiction. The remainder of the proof is then dedicated to ruling out the special case.
Proof of Theorem 1. Let G be an IPR fullerene graph, let Hi and H2 be two disjoint hexagons of G, and set H := V(Hi U H2). Suppose G — H does not have a perfect matching. Then Theorem 3 guarantees the existence of a set A of vertices of G — H such that G — (H U A) contains more than |A| factor-critical components, and all other components of G — (H U A) have a perfect matching. We denote the factor-critical components of G — (H U A) by D, and the components of G — (H U A) with a perfect matching by C. The subset of non-trivial factor-critical components of G — (H U A) is denoted by D*. The union of the vertex sets of the components of C, D and D* is denoted by C, D and D*, respectively, and we set D0 := D — D* (see Figure 4).
The number of vertices of G being even, |D| and |A| have the same parity. Since |D| > |A|, we deduce that
|D|>|A| + 2.	(1)
cn
The number of edges leaving A U H may be expressed as
• i
|d(A U H)| = |d(H)| + 31A| — 2e(A, H) — 2e(A).	(2)
m
Now set
s(D) := £(|d(F)| — 3)/2 f ev
a
CD
r5
fc
VD
u
CD
H
C
>—<
A
X X >—<
D
D0
A
0
a
o
1
00 ^
CO CO
CO CD
Jh
CD CO
and
Figure 4: The partition of V(G) into H, A, C, D* and D0.
s(C) := £(|d(F)| — 4)/2. f ec
By Lemmas 4 and 5, the number of edges leaving C U D may be expressed
|d(C U D)| = 3|D| + 4|C| + 2(s(C) + s(D)).	(3)
Since d(A U H) = d(C U D), (1), (2) and (3) imply that
2|C| + e(A, H) + e(A) + s(C) + s(D) < 1 |d(H)| — 3 < 3. (4)
Let P be the set of pentagons of G; it follows from Euler's formula that |P| = 12. If X C V (G) and Y C E (G), let p(X) := |{P eP| V (P) n X = 0}| and p(Y) := |{P G P | E(P) n Y = 0}|.
Observe that every edge of the graph G — (H U C U D* U E(A)) has one endvertex in A and the other in D0; in particular, G — (HU CU D* U E(A)) is bipartite. This means that all twelve pentagons of G must contain a vertex in H U C U D* or an edge in E(A). By the IPR, p(H) < 6, so at least six pentagons disjoint from H must have a vertex in CU D* or an edge in E(A). In particular,
p(E(A))+ p(C)+ p(D*) > 6.	(5)
U
a
CD U
Claim 1. There exists a component F* G D* such that |d(F*)| = 9.
£
Figure 5: A link of size 3. The hexagons Hi and H2 are drawn bold, the
2 U
CD
i
CSI 00
£
CO CO
edges of the link are dashed.
By (4), |C| < 1. If |C| = 1, then e(A) + s(V) + s(C) < 1 by (4). By the IPR, p(E(A)) < e(A) < 1. As s(V) < 1, Lemma 4 and the IPR imply that p(D*) < 1. Finally, by Lemma 5 and the IPR, p(C) < s(C) + 2 < 3. Hence p(E(A)) + p(C) + p(D*) < e(A) + s(V) + s(C) + 2 < 6, contradicting (5).
Hence we may assume that C = 0. In particular, p(C) = s(C) = 0, and by (4) e(A) + s(V) < 3. This implies that |d(F)| < 9 for every F E V*. If |d(F)| < 9 for every F E V*, then by Lemma 4 and the IPR, p(D*) < s(V) + 1. Hence p(E(A)) + p(C) + p(D*) < e(A) + s(V) + 1 < 6, contradicting (5). Therefore |d(F*)| = 9 for some component F* E V*, as claimed.	A
By (4), F* is the unique non-trivial component of V, C = 0, e(A) = 0 (so A is an independent set), e(A, H) = 0 and |d(H)| = 12 (in particular, there are no edges between the hexagons Hi and H2). As F* is non-trivial and factor-critical, it is 2-connected by Observation 2. In particular, it has minimum degree 2.
Let us now fix a planar embedding of G. If e, f are edges of G, we will say that e is opposite f if they both belong to the boundary of some hexagonal face and no edge of this boundary is incident with both e and f. A link is a sequence L = (ei,..., ek) of edges, where
(1)	ei+i is opposite e^ for i = 1,..., k — 1,
(2)	ei belongs to Hi and ek belongs to H2.
(See Figure 5 for an illustration.) The size |L| of such a link is defined as k. The following observation is immediate:
Observation 7. Any two links in G are disjoint.
CD
We continue with a simple structural lemma.
5H
Lemma 8. G contains no two links Li,L2 with |Li| + |L2| < 6.
Proof. Suppose such Li and L2 exist. We claim that their union (as sets) forms an edge-cut of G. This is easy to see from the duality between edge-cuts in G and cycles in the dual graph. For a direct argument, note that one
ft
CD
VD
u
CD fc
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
$H
a
CD U
0
111
1 1
1 i 2 2 1 1
M—<
2
0
2
2
Figure 6: The values of £(F) in the proof of Lemma 8 (shown as the numbers inside the faces adjacent to Gi).
can draw a closed curve C in the plane which only intersects the edges in L1U L2 (connecting each pair of opposite edges by a line segment through the face containing them, and proceeding similarly on H1 and H2). In addition, the subgraphs G1 and G2 into which G is divided by C can easily be seen to be connected, which shows that L1 U L2 is an edge-cut.
Lemma 6 gives us the possibilities for G1 or G2. Let us assume that G1 is one of the subgraphs listed in the lemma. Let N be the set of faces of G which intersect both G1 and G2. For each face F in N, let £(F) be the number of edges of G1 that belong to F. By the definition of a link, we have £(F) = 2 for each F e N \ (H1 U H2). However, considering the possibilities for G 1 of Lemma 6 (with two different embeddings in the case of the path of length 3) we find that in each case, at least three values of £(F) are different from 2. See Figure 6 for an illustration. This contradiction concludes the proof.	□
The following lemma is the core of our argument.
Lemma 9. Let j E {1, 2}. Assume that a,b are adjacent vertices of Hj and M is the face of G whose boundary includes the edge ab and which is different from Hj. Let a',b' be the neighbours of a and b (respectively) not in Hj. If neither aa' nor bb' is an edge of d(F*), then M is either a pentagonal face,
0
0
0
0
0
0
0
0
0
1
1
1
1
or a hexagonal face intersecting both Hi and H2.
vO
Proof. Suppose that M has length 6, so its boundary is a'abb'xy, where x,y G V(G). Since a' and b' belong neither to A U V(Hi U H2) nor to F* (by assumption), we have a',b' G D0. Thus, x and y are contained in A U V(Hi U H2). Since E(A U V(Hi) U V(H2)) = E(V(Hi)) U E(V(H2), both x and y must be contained in the same hexagon Hk (for some k = 1, 2). However, if x,y G V(Hj), then it is easy to find a cycle of length at most 4 CD	in G, contradicting the fact that G is cyclically 5-edge-connected. Thus, M
intersects both Hi and H2 which proves the claim.	□
We want to be able to bound the number of edges of d(F*) 'near' Hi and H2. We will make use of the following lemma.
Lemma 10. Let F be a face of G incident with Hj (j = 1, 2). Then the intersection of d(F*) with the boundary of F is either empty, or it is a matching of size 2 which does not form a pair of opposite edges. If, in addition, F is a pentagon, then both edges of the matching have one endvertex on Hj.
Proof. If the intersection of d(F*) with the boundary of F is non-empty, then it has to be a matching {vw,xy}, by Observation 2 and the fact that
5H
fc
o
the intersection of a cycle and an edge cut is even. If both vw and xy have a vertex in V(Hj), then uv,xy are not opposite, as required.
So suppose now that one of the edges vw,xy has no vertex in V(Hj); without loss of generality say it is vw. If v is adjacent to a vertex of Hj, then v G D0 and w G D*, contradicting the fact that there are no edges between D0 and D*. Similarly for w. Therefore v, w are not adjacent to any vertex of V(Hj), so M is a hexagon and vw,xy are not opposite.	□
1
CSI 00 CSI
CO
CO	A cluster at Hj (j = 1, 2) is a sequence Q = (ei,..., ek) such that:
•	each ej is in d(F*),
•	ej and ei+i are on the same face (1 < i < k — 1),
•	for 2 < i < k — 1, each has exactly one endvertex on Hj, while ei and ek are not incident with H,.
m	j
Examples of clusters are shown in Figure 7. The size |Q| of Q is the number of its edges. Observe that |Q| > 3.
Lemma 11.
(i) Clusters at Hj are pairwise disjoint (for j = 1, 2).
CD
VD
u
CD fc
Figure 7: Examples of clusters at H1. Left: a cluster of size 3. Right: a cluster of size 5. The edges of the clusters are shown as zigzag lines, those of H1 are drawn bold. Squares represent the vertices of F*.
0 o
1
CO ^
CO CO
CO CD
Jh
CD CO
u
a
CD U
(ii) G contains at most one edge e that is contained in a cluster at H1 and a cluster at H2. If e exists, then it is contained in a link of size 3.
Proof. (i) If an edge e belongs to two distinct clusters C, C at Hj, then it is clearly not incident with Hj. We may thus assume that C and C are of the form C = (e, e2,..., ek) and C = (e, e'2,... ,e'f). By the definition of a cluster and Lemma 10, e belongs to hexagonal faces M and M' whose boundaries contain e2 and e'2, respectively. However, e belongs to the boundary of only one face adjacent to Hj, so M = M' and this face boundary contains e, e2 and e2, a contradiction to Lemma 10.
(ii) Assume an edge e is contained in a cluster C1 at H1 and C2 at H2. By Lemma 10 and the fact that there are no edges between H1 and H2, it is easy to check that e is incident with neither H1 nor H2. By Lemma 10 e is opposite an edge of H1 and opposite an edge of H2, so it is contained in a link of size 3. The uniqueness of e follows by Lemma 8.	□
We shall now use Lemma 9 to lower-bound the number of edges of d (F*) incident with each Hj. Let us call an edge e of G free if e E d(F*).
Lemma 12. Let j E {1, 2}.
(i)	d(Hj) does not contain five free edges.
(ii)	If d(Hj) contains three consecutive1 free edges, then there is a link of size 2 in G.
(iii)	There is exactly one cluster at Hj, and its size is 4 or 5.
Proof. (i) Any set of five free edges in d(Hj) contains four consecutive pairs of free edges. By Lemma 9, each of these pairs belongs to the boundary
1'Consecutive' refers to the natural clockwise ordering of d(Hj).
VD
u
CD
	P2 j
	i-<
Figure 8: An illustration to the final argument in the proof of Theorem 1 (the case when Q is adjacent to Pi). The conventions for the vertices and edges are the same as in Figure 7.
0 o
1
CO
£ CO CO
CO CD
u
CD CO
a
CD U
of either a pentagonal face, or a hexagonal face incident with Hi and H2. Lemma 8 implies that only one of the four pairs is of the latter type. It follows that d(Hj) contains three edges e,e',e" such that each of the pairs e, e' and e', e'' belongs to a pentagon. Since this would violate the IPR, d(Hj) does not contain five free edges.
(ii)	This is a direct consequence of Lemma 9 and the IPR.
(iii)	Suppose that d(Hj) C d(F*), or that Hj is incident with two or more clusters. In both cases there are at most three edges of d(F*) left for the clusters at H3-j. Hence there is only one cluster (of size 3) at H3-j- and five edges of d(H3-j-) are free, contradicting (i). The claim follows.	□
We now use Lemma 12(iii) to conclude the analysis. Assume first that there is a cluster of size 5 at both Hi and H2. These clusters have nonempty intersection as |d(F*)| is only 9. By Lemma 11(ii), G contains a link of size 3. On the other hand, observe that the set d(Hi) contains three consecutive free edges, which by Lemma 12(ii) is only possible if there is a link of size 2 in G. The existence of these two links contradicts Lemma 8.
We may thus assume that the cluster at Hi has size 4. Since there are four consecutive free edges ei,..., e4 E d(Hi), Lemma 12(ii) implies the existence of a link L of size 2 in G. Figure 8 depicts the situation. Let M be the (hexagonal) face whose boundary contains both edges of L. Lemma 8 and the fact that there are no edges between the hexagons Hi and H2 implies that M is the unique face intersecting both Hi and H2. Therefore, by Lemma 9 and the IPR, e2 and e3 belong to M, while the pairs ei, e2 and e3, e4 belong to pentagonal faces (Pi and P2, respectively) adjacent to Hi and M.
The cluster at H2 has size 4 or 5, which means that d (H2) contains at least three consecutive free edges. By another application of Lemma 9 and
VD
u
CD
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
the IPR, two of them must belong to a pentagonal face Q adjacent to M and H2. However, it is easy to see that Q is adjacent to either Pi or P2. This contradiction to the IPR completes the proof of Theorem 1.	□
References
[1]	M. Chudnovsky and P. Seymour. Perfect matchings in planar cubic graphs. Combinatorica. To appear.
[2]	T. Doslic. Cyclical edge-connectivity of fullerene graphs and (k, 6)-cages. J. Math. Chem., 33(2):103-112, 2003.
[3]	J. Edmonds. Paths, trees, and flowers. Canad. J. Math., 17:449-467, 1965.
[4]	P. W. Fowler and D. E. Manolopoulos. An Atlas of Fullerenes. Oxford University Press, Oxford, 1995.
[5]	T. Gallai. Kritische Graphen. II. Magyar Tud. Akad. Mat. Kutato Int. Kozl., 8:373-395, 1963.
[6]	T. Gallai. Maximale Systeme unabhangiger Kanten. Magyar Tud. Akad. Mat. Kutato Int. Kozl, 9:401-413, 1964.
[7]	F. Kardos, D. Km!, D. Miskuf, and J.-S. Sereni. Fullerene graphs have exponentially many perfect matchings. J. Math. Chem., 46(2):443-477, 2009.
[8]	F. Kardos, M. Krnc, B. Luzar, and R. Skrekovski. Cyclic 7-edge-cuts in fullerene graphs. J. Math. Chem., 47(2):771-789, 2010.
[9]	F. Kardos and R. Skrekovski. Cyclic edge-cuts in fullerene graphs. J. Math. Chem., 44(1):121-132, 2008.
[10]	H. W. Kroto, J. R. Heath, S. C. O'Brien, R. F. Curl, and R. E. Smalley. C60: Buckminsterfullerene. Nature, 318:162-163, 1985.
[11]	K. Kutnar and D. Marusic. On cyclic edge-connectivity of fullerenes. Discrete Applied Math., 156(10):1661-1669, 2008.
[12]	L. Lovasz. A note on factor-critical graphs. Studia Sci. Math. Hungar., 7:279-280, 1972.
U
a
CD U
[13] L. Lovasz and M. D. Plummer. Matching theory, volume 121 of North-
Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29.
£ ctf
[14] E. Osawa. Superaromaticity. Kagaku (Kyoto), 25:854-863, 1970.
[15]	A. Schrijver. Combinatorial optimization: Polyhedra and efficiency, volume 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2003.
CD
[16]	W. T. Tutte. The factorization of linear graphs. J. London Math. Soc., 22:107-111, 1947.
[17]	D. Ye, Z. Qi, and H. Zhang. On k-resonant fullerene graphs. SIAM J. Discrete Math, 23(2):1023-1044, 2009.
0 o
1
CO
£ CO CO
CO CD
Jh
CD CO
u
a
CD