CHEMICAL GRAPH THEORY OF FIBONACENESIvan Gutmana and Sandi Klavzarb,∗aFaculty of Science, University of Kragujevac, P. O.
Box 60, YU-34000 Kragujevac, Serbia & Montenegro gutman@knez.uis.kg.ac.yu bDepartment of Mathematics and Computer Science
PeF, University of Maribor
Koroska cesta 160, SI-2000 Maribor, Slovenia sandi.klavzar@uni-mb.si
(Received Neverber 99, 2005)
Abstract
Fibonacenes (zig-zag unbranched catacondensed benzenoid
hydrocarbons) are a class of polycyclic conjugated systems whose
molecular graphs possess remarkable properties, often related with
the Fibonacci numbers. This article is a review of the chemical
graph theory of fibonacenes, with emphasis on their
Kekulé-structure-related and Clar-structure-related
properties.
----------------- ∗Supported in part by the Ministry of
Science of Slovenia under the grant P1-0297.
0. FIBONACCI NUMBERS
The sequence of integers F0,F1,F2,F3,… , named after
Leonardo Pisano aka Fibonacci (1170-1250), is defined by means
of the recurrence relation
Fn = Fn−1 + Fn−2
and by means of the initial conditions
F0=0 ; F1=1 .
Thus,
F2=1 , F3=2 , F4=3 , F5=5 , F6=8 , F7=13 ,
F8=21 , F9=34 , F10=55 , etc.
The mathematical theory of Fibonacci numbers is very interesting
and can be found in pertinent books (for instance, in
[1,2]) or in the articles published in the journal
"Fibonacci Quarterly ".1
1. INTRODUCTION
Fibonacenes are unbranched catacondensed benzenoid hydrocarbons in
which all non-terminal hexagons are angularly annelated. Their
structure should be evident already from the examples depicted in
Fig. 1.
Figure 1:
The fibonacenes with four, five, and six hexagons; cf. Fig. 3.
The name fibonacene 2 was proposed by Balaban in 1989
[3], although it seems to be first mentioned somewhat
earlier [4]. The name is due to the (long known
[5,6,7]) fact that the Kekulé structure count
of fibonacenes coincides with the Fibonacci numbers; for details
see below.
In order to define fibonacenes (or more precisely: the molecular
graphs of fibonacenes) in a more precise manner, we need to recall
some basic notions from the theory of benzenoid systems
[8]. In what follows we employ the terminology and
definitions employed in an earlier review [9].
Definition 1. A hexagonal system is a connected
plane graph without cut-vertices in which all inner faces are
hexagons (and all hexagons are faces), such that two hexagons are
either disjoint or have exactly one common edge, and no three
hexagons share a common edge.
Definition 2. A hexagonal system is said to be
simple if it can be embedded into the regular hexagonal
lattice in the plane without overlapping of its vertices.
Hexagonal systems that are not simple are called jammed .
Hexagons sharing a common edge are said to be adjacent or
neighboring . Two hexagons of a hexagonal system may have
either two common vertices (if they are adjacent) or none (if they
are not adjacent). A vertex of a hexagonal system belongs to at
most three hexagons. A vertex shared by three hexagons is called
an internal vertex of the respective hexagonal system.
Definition 3. A hexagonal system is said to be
catacondensed if it does not possess internal vertices. A
hexagonal system is said to be pericondensed if it
possesses at least one internal vertex.
A hexagon of a catacondensed hexagonal system has either one, two,
or three neighboring hexagons. A hexagon having exactly one
neighboring hexagon is said to be terminal . A hexagon
having three neighboring hexagons is said to be branched .
Definition 4. A catacondensed hexagonal system possessing at
least one branched hexagon is said to be a branched
catacondensed hexagonal system . A catacondensed hexagonal
system without branched hexagons is called a hexagonal
chain .
A hexagonal chain with h hexagons, h ≥ 2 , possesses two
terminal hexagons and h−2 hexagons that have two neighbors.
Hexagons being adjacent to exactly two other hexagons are
classified as angularly or linearly annelated. A hexagon adjacent
to exactly two other hexagons possesses two vertices of degree 2.
If these two vertices are adjacent, then the hexagon is
angularly annelated , if these two vertices are not adjacent,
then it is linearly annelated .
Definition 5. A fibonacene is a hexagonal chain
without linearly annelated hexagons.
One should note that fibonacenes may be either simple or jammed.
Among the examples shown in Fig. 1 only the last one (with h=6)
is jammed; it corresponds to the chemical compound called
"hexahelicene". In many graph-theory-based studies (including
those outlined in the present paper) it is convenient to consider
the class of all fibonacenes, including both simple and jammed.
Sometimes, however, jammed systems would be excluded, see e. g.
[8]. Anyway, all properties of fibonacenes discussed in
this review are independent of whether these are or are not
simple.
Throughout this article h always denotes the number of hexagons.
In what follows, for the sake of brevity, a hexagonal chain and a
fibonacene with h hexagons will be referred to as an
h-hexagonal chain and an h-fibonacene, respectively.
2. SYMMETRY AND ENUMERATION OF FIBONACENES
According to symmetry, fibonacenes can be mirror-symmetric (S),
centro-symmetric (C) and asymmetric (A). Characteristic
examples of these symmetry types are shown in Fig. 2.
Figure 2:
Examples (the smallest possible) of a
mirror-symmetric (S), centro-symmetric (C) and asymmetric
(A) fibonacenes. The symmetry axis and the center of symmetry
are indicated in S and C , respectively.
If S(h) , C(h) , and A(h) are, respectively, the number of
mirror-symmetric, centro-symmetric, and asymmetric
h-fibonacenes, then for h ≥ 3 [3],
S(h)
=
2h/2−2
ifhiseven
2(h−1)/2−1
ifhisodd
C(h)
=
2h/2−2
ifhiseven
0
ifhisodd
A(h)
=
2h−4 − 2h/2−2
ifhiseven
2h−4 − 2(h−1)/2−2
ifhisodd
.
The total number of h-fibonacenes is T(h) = S(h) + C(h) + A(h) , and thus
T(h) =
2h−4 + 2h/2−2
ifhiseven
2h−4 + 2(h−1)/2−2
ifhisodd
.
(1)
It is easy to see that
lim h → ∞
A(h)
T(h)
= 1
implying that almost all fibonacenes are asymmetric. (Analogous
results are known also for hexagonal systems in general, as
well as for catacondensed and pericondensed hexagonal systems
[10].)
Denote by J(h) the number of jammed h-fibonacenes. The
J(h)-values were determined by Balaban for the first few values
of h [3]:
h
3
4
5
6
7
8
9
10
J(h)
0
0
0
1
2
5
11
26
T(h)
1
2
3
6
10
20
36
72
Although at the first glance, the J(h)-values appear to be
much smaller than T(h) , in the limit h → ∞ , almost
all h-fibonacenes happen to be jammed.
3. BASIC PROPERTIES OF FIBONACENES
A molecular graph representing any h-fibonacene has 4h+2
vertices, of which 2h+4 are of degree 2 and 2h−2 of degree 3.
This graph has 5h+1 edges, of which h+4 connect two vertices
of degree 2, 2h connect two vertices of degree 3, and 2h−3
connect vertices of degree 2 and 3. For more detail on these
"anatomic" properties see [8].
The Wiener index of hexagonal systems was much investigated
[9], among which also of fibonacenes. Among the
fibonacenes with a fixed number of hexagons three are extremal
with regard to their Wiener indices: the helicene (Hh), the
zig-zag fibonacene (Zh), and the serpent (Sh), see Fig. 3.
Their Wiener indices conform to the expressions:
Figure 3:
Three extremal fibonacenes: helicene (Hh),
zig-zag fibonacene (Zh), and serpent (Sh); see also Fig. 1.
Formulas (2), (3), and (4) seem to have been
first reported in [11], [11], and [12],
respectively. It has been shown [13] that Hh has the
smallest Wiener index among all h-hexagonal chains, whereas
Sh has the smallest Wiener index among all simple h-hexagonal
chains [12]. The system Zh has the greatest Wiener
index among all h-fibonacenes.
The same fibonacene Zh was shown to have maximal energy among
all h-hexagonal chains [14].
A peculiar result was obtained by considering the average Wiener
index Wavr(h) in the set F(h) of all fibonacenes
with h hexagons. By definition,
Wavr(h) =
1
|F(h)|
∑ G ∈ F(h)
W(G) .
It was shown [15] that Wavr(h) is necessarily an
integer, implying that the sum of the Wiener indices of all
h-fibonacenes is divisible by the number T(h) of
h-fibonacenes. (Recall that T(h) is given by Eq. (1).)
Furthermore,
Wavr(h) = 4 h3 + 16 h2 + 6 h + 1 .
4. KEKULÉ STRUCTURES OF FIBONACENES
Denote by K{H} the number of Kekulé structures (or, in the
language of graph theory, the number of perfect matchings) of the
hexagonal system H .
Before formulating the main result of this section, we state
without proof a more general regularity for the number of Kekulé
structures.
Let R be a (molecular) graph and let u and v be its two
adjacent vertices. Let S be another (molecular) graph and x
and y its adjacent vertices. Let the graphs H1,H2,H3,H4 be
obtained by annelating (in an angular manner) the fragments R
and S to a hexagon, as shown in Fig. 4.
Figure 4:
Four different ways in which angular annelation can be done.
Theorem 1. (a) If the fragments R and S have both an
even number of vertices, then K{H1}=K{H2}=K{H3} = K{H4} .
(b) If the fragments R and S have both an odd number of
vertices, then K{H1}=K{H4} and K{H2}=K{H3} , but
K{H1} and K{H2} may differ.
(c) If the fragment R has even and S odd number of vertices
(or vice versa), then K{H1}=K{H2}=K{H3}=K{H4}=0 .
It is immediate to see that part (a) of Theorem 1 is directly
applicable to fibonacenes, implying:
Corollary 1.1. All h-fibonacenes have equal number of
Kekulé structures.
A long-time known [5,6], easy-to-prove, and
frequently used [7,8,17,18,19,20,21,22], result on Kekulé structures is the following:
Theorem 2. The number of Kekulé structures of the zig-zag
fibonacene Zh is equal to the (h+2)-th Fibonacci number,
K{Zh} = Fh+2 , h ≥ 1 .
Corollary 2.1. The number of Kekulé structures of any
h-fibonacene is equal to the (h+2)-th Fibonacci number.
5. CLAR STRUCTURES OF FIBONACENES
Denote the number of Clar structures [8,16] of a
hexagonal system H by C(H) , and its Clar number, that is the
number of aromatic sextets in any of the Clar structures, by
Cl(H) . Recall that the calculation of both C(H) and
Cl(H) is not an easy task, and was the subject of several
earlier studies [23,24,25].
In connection with the Clar structures one can establish results
similar to those for Kekulé structures (but not involving
Fibonacci numbers). First we have an analog of Theorem 1:
Theorem 3. Using the notation employed in Theorem 1 (cf.
Fig. 4), the following holds.
(a) If the fragments R and S have both an even number of
vertices, then C{H1}=C{H2}=C{H3}=C{H4} and
Cl{H1}=Cl{H2}=Cl{H3}=Cl{H4} .
(b) If the fragments R and S have both an odd number of
vertices, then C{H1}=C{H4} , C{H2}=C{H3} , and
Cl{H1}=Cl{H4} , Cl{H2}=Cl{H3} , but
C{H1} and C{H2} as well as Cl{H1} and Cl{H2}
may differ.
(c) If the fragment R has even and S odd number of vertices
(or vice versa), then C{H1}=C{H2}=C{H3}=C{H4}=0 and
Cl{H1}=Cl{H2}=Cl{H3}=Cl{H4}=0 .
Corollary 3.1. All h-fibonacenes have equal number of
Clar structures and equal Clar numbers.
Figure 5:
Clar structures of the zig-zag 4- and
5-fibonacenes. Here C(Z4)=3 , Cl(Z4)=2 and
C(Z5)=1 , Cl(Z5)=3 .
In Fig. 5 are shown the Clar structures of the zig-zag
h-fibonacenes for h=4 and h=5 . By inspection of this
figure one easily reaches the following general conclusion:
Theorem 4. The zig-zag fibonacene Zh has h/2 aromatic sextets. If h is odd, it has a unique Clar
structure. If h is even, it has h/2+1 distinct Clar
structures.
Corollary 4.1. The number of Clar structures of any
h-fibonacene is equal to 1 (if h is odd) or to h/2+1 (if h
is even). The Clar number of any h-fibonacene is h/2 .
The fact that the modes of cyclic conjugation and the distribution
of π-electrons, as represented by the Clar structures, are
significantly different in fibonacenes with odd and even number of
hexagons attracted some attention [26,27,28]. However,
no significant difference between the stability and
"aromaticity" of odd and even fibonacenes could be envisaged by
any of the theoretical approaches, in harmony with the existing
experimental data [29,30].
6. FIBONACENES AS MAXIMUM CYCLE RESONANT
HEXAGONAL CHAINS
In this section we show that fibonacenes can be characterized among
hexagonal chains using a concept from the resonance theory. To
state and prove the result, some preparation is needed.
Disjoint cycles of a graph G are called mutually resonant
if there exists a Kekulé structure M of G such that any of
the given cycles in M-alternating. G is k-cycle
resonant if it contains at least k disjoint cycles and any r
disjoint cycles, where 1 ≤ r ≤ k, are mutually resonant.
Let H be a hexagonal system and let P be a path whose
endvertices are of degree three in H and all the other vertices
are of degree two in H. Then we say that P is a
3,3-boundary path of H .
Then we have the following nice characterization of 2-cycle
resonant hexagonal systems proved by Gou and Zhang in [31].
Theorem 5.
Let H be a hexagonal system with at least two disjoint hexagons.
Then H is 2-cycle resonant if and only if H is a catacondensed
hexagonal system with no 3,3-boundary path of even length.
In fact, 2-cycle resonance is critical when considering higher
cycle resonance, as the next result from [31] asserts.
Theorem 6.
Let H be a 2-cycle resonant hexagonal system and let k be the
maximum number of disjoint cycles in H. Then H is k-cycle
resonant.
Combining Theorems 5
and 6 we obtain the following result that
characterizes fibonacenes among hexagonal chains. Call a hexagonal
system Hmaximum cycle resonant if H is k-cycle
resonant, where k is the maximum number of disjoint cycles of
H. Then:
Theorem 7.
Let H be a hexagonal chain. Then H is a fibonacene if and only
if H is maximum cycle resonant.
Proof.
If a hexagonal chain H consists of one or two hexagons, the
theorem is clear. Suppose H contains at least three hexagons.
Then we easily see that H contains no 3,3-boundary
path of even length if and only if H is a fibonacene. Then
Theorem 5 implies that H is 2-cycle
resonant if and only if H is a fibonacene and
Theorem 6 completes the argument.
\square
Theorem 7 has been first stated
explicitly by Shiu, Lam, and Zhang in [32]. Their
somewhat more complicated proof also uses results
of [31]. In [32] two extremal properties
concerning the number of matchings and the number of independent
sets are also proved for fibonacenes.
We also add that in [33] the theory of cycle resonance is
further developed. In particular, an algorithm is proposed that
determines whether a planar 2-connected bipartite graph is 1-cycle
resonant.
7. FIBONACENES AS FIBONACCI CUBES
We continue with the role of fibonacenes in the resonance theory.
In this section we demonstrate a surprising connection between
fibonacenes and graphs that were introduced in theoretical computer
science as a model for interconnection networks.
Let H be a hexagonal system. Then the vertex set of the
resonance graphR(H) of H consists of all Kekulé
structures of H, where two Kekulé structures are adjacent
whenever their symmetric difference is the edge set of a hexagon
of H ; an example of a fibonacene and its resonance graph is
shown on Fig. 6.
Figure 6:
The Kekulé structures of Z4 and the resonance graph
R(Z4) .
Resonance graphs have been independently introduced in the
chemical literature [34,35,36] as well as in the
mathematical literature [37]. For more result
on the resonance graphs
see [38,39,40,41,42].
Consider now the following seemingly unrelated concept that has
been introduced in [43,44] as a model for
interconnection networks, see also [45,46,47,48].
The vertex set of the
Fibonacci cube Γn, n ≥ 1 , is the set of all
binary strings b1b2…bn containing no two consecutive
ones. Two vertices are adjacent in Γn if they differ in
precisely one bit, cf. Fig. 7 where the first four
Fibonacci cubes are shown.
Figure 7:
The Fibonacci cubes Γ1, Γ2, Γ3, and Γ4 .
Compare Figures 6 and 7 to note that Γ4 is just the resonance graph
of Z4, that is, Γ4 = R(Z4). This is not a coincidence, as
our final theorem from [49] asserts.
Theorem 8.
Let H be an arbitrary fibonacene with n hexagons. Then
R(H) = Γn .
A. T. Balaban, Chemical graphs. L. Symmetry and
enumeration of fibonacenes (unbranched catacondensed
benzenoids isoarithmic with helicenes and zigzag
catafusenes), MATCH Commun. Math. Chem. 24
(1989) 29-38.
P. G. Anderson, Fibonaccene, in: A. N. Philippou,
G. E. Bergum, A. F. Horadam (Eds.), Fibonacci Numbers
and Their Applications , Reidel, Dordrecht, 1986, pp.
1-8.
A. T. Balaban, I. Tomescu, Chemical graphs. XL.
Three relations between the Fibonacci sequence and the
number of Kekulé structures for non-branched
cata-condensed polycyclic aromatic hydrocarbons,
Croat. Chem. Acta 57 (1984) 391-404.
A. T. Balaban, I. Tomescu, Chemical graphs. XLI.
Numbers of conjugated circuits and Kekulé structures for
zigzag catafusenes and (j,k)-hexes; generalized
Fibonacci numbers, MATCH Commun. Math. Chem. 17 (1985) 91-120.
H. Abeledo, G. Atkinson, The Clar and Fries
problems for benzenoid hydrocarbons are linear programs,
in: P. Hansen, P. Fowler, M. Zheng (Eds.), Discrete
Mathematical Chemistry , Am. Math. Soc., Providence,
2000, pp. 1-8.
M. Randi\'c, A. T. Balaban, Partitioning of
π-electrons in rings of polycyclic conjugated
hydrocarbons. Part 1: Catacondensed benzenoids,
Polyc. Arom. Comp. 24 (2004) 173-193.
S. El-Basil, Generation of lattice graphs. An equivalence
relation on Kekulé counts of catacondensed benzenoid
hydrocarbons, J. Mol. Struct.(Theochem) 288
(1993) 67-84.
S. Klavzar, A. Vesel, P. Zigert, On resonance graphs
of catacondensed hexagonal graphs: structure, coding, and
Hamilton path algorithm, MATCH Commun. Math. Comput.
Chem. 49 (2003) 99-116.
S. Klavzar, P. Zigert,
Fibonacci cubes are the resonance graphs of fibonaccenes,
Fibonacci Quart. 43 (2005) 269-276.
Footnotes:
1When reading a book or
an article in which Fibonacci numbers are encountered, one should
always check the way in which these are defined. Some authors use
the initial conditions F0=F1=1 , and thus their "Fibonacci
numbers" are shifted by one relative to the present ones.
2In view of some recent
disputes concerning the spelling of the name, it may be useful to
repeat Balaban's original words from [3]: We are
aware that fibonaccenes would be etymologically more suitable but
we suppressed one c for the simplicity and for similarity with the
established name "acenes".
File translated from
TEX
by
TTH,
version 3.35. On 05 Sep 2005, 09:49.