ISSN 2590-9770
The Art of Discrete and Applied Mathematics 2 (2019) #P1.09
https://doi.org/10.26493/2590-9770.1228.eb5
(Also available at http://adam-journal.eu)
Infinite benzenoids
Nino Bašić ∗
FAMNIT, University of Primorska, Glagoljaška 8, 6000 Koper, Slovenia
IAM, University of Primorska, Muzejski trg 2, 6000 Koper, Slovenia
IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
Received 6 December 2017, accepted 28 January 2019, published online 30 December 2019
Abstract
A family of benzenoids, called convex benzenoids, was introduced in 2012 by Cruz,
Gutman and Rada. In a later paper by the present author et al., several equivalent charac-
terisations of convex benzenoids have been given and their equivalence was proved. Along
the way an infinite benzenoid called the half-plane was used for the purpose of theoretical
reasoning. In this short paper, some properties of infinite benzenoids are discussed. It is
proved that their boundary consists of countably many connected components. Convex in-
finite benzenoids are classified and it is proved that there are only countably many convex
infinite benzenoids, whilst there are uncountably many infinite (non-convex) benzenoids.
We also show that there are countably many infinite benzenoids which have a finite number
of 1s in their boundary-edges code.
Keywords: Infinite benzenoid, hexagonal system, convex benzenoid, boundary-edges code, half-plane,
countable set.
Math. Subj. Class.: 05C10, 92E10, 03E75
1 Introduction
Benzenoids are important compounds in chemistry and have been extensively studied dur-
ing the past few decades. For an exhaustive treatment of the topic see the classical reference
by Cyvin and Gutman [9]. The reader may want to consult references [5, 6] and [7] for ad-
vanced treatments. In the present paper, we study their associated benzenoid graphs from
a purely mathematical viewpoint. Hereinafter, the word benzenoid is used as a synonym
for benzenoid graph. We build upon theoretical treatment of benzenoids from [2]. The
framework of [2] allows for generalisation to structures called infinite benzenoids. In 2012
∗The author has been supported in part by ARRS Slovenia (projects P1-0294 and N1-0032). The author would
like to thank Tomaž Pisanski for fruitful discussions during the preparation of the manuscript.
E-mail address: nino.basic@famnit.upr.si (Nino Bašić)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 2 (2019) #P1.09
a family of convex benzenoids was introduced by Cruz, Gutman and Rada [4]. In a recent
work [3], we presented several alternative characterisations of convex benzenoids. In this
work, we study properties of convex infinite benzenoids. We assume that the reader is fa-
miliar with results of elementary set theory (e.g., the union of countably many countable
sets is countable). For definitions of set-theoretic terms such as countable set and uncount-
able set, consult a standard reference such as [10] or [12]. This paper further develops
several ideas already present in the PhD thesis of the author [1].
2 The hexagonal grid
Let us consider the infinite cubic plane graph H, called the hexagonal grid. (For an intro-
duction to infinite graphs, consult Chapter 8 of [8].) It comprises infinitely many hexagonal
faces each of which is incident with 6 edges and 6 vertices. We say that faces a, b ∈ F (H)
are adjacent if they are different and share an edge. The faces of H will be simply called
hexagons. Two hexagons are neighbours if they have exactly one edge in common. Some-
times, it is convenient to introduce a coordinate system on the hexagonal gridH, as shown
in Figure 1. Let h ∈ H. Then ξ(h) and η(h) will denote the first and second coordinate
(−3, 2) (−2, 2) (−1, 2) (0, 2) (1, 2)
(−2, 1) (−1, 1) (0, 1) (1, 1) (2, 1)
(−2, 0) (−1, 0) (0, 0) (1, 0) (2, 0)
(−1,−1) (0,−1) (1,−1) (2,−1) (3,−1)
(−1,−2) (0,−2) (1,−2) (2,−2) (3,−2)
η = 2
η = 1
η = 0
η = −1
η = −2
ξ
=
3
ξ
=
2
ξ
=
1
ξ
=
0
ξ
=
−1
ζ
=
3
ζ
=
2
ζ
=
1
ζ
=
0
ζ
=
−
1
Figure 1: Coordinate system onH.
of h as shown in Figure 1. We may introduce yet another coordinate ζ(h), but it is not
independent of the previous two since ζ(h) = ξ(h) + η(h). For a detailed description of
the coordinate system onH, see [1] or [3].
N. Bašić: Infinite benzenoids 3
3 Hexagonal systems and benzenoids
An arbitrary subset of faces K ⊆ F (H), together with all vertices and edges that are
incident with at least one member of K, is called a hexagonal system. We will denote
the corresponding hexagonal system simply by K, even though it is formally a subset of
faces. Two hexagonal systems are isomorphic if one can be obtained from the other by an
isometry of the plane that leaves H invariant. Hexagons a ∈ K and b ∈ K belong to the
same connected component of the hexagonal system if there exists a sequence of hexagons
h1 = a, h2, . . . , hn = b such that hi and hi+1 are adjacent for each i = 1, . . . , n − 1 and
{h1, . . . , hn} ⊆ K. When all hexagons of the sequence are pairwise distinct, it is called a
path between a and b in K. The interval between a and b in K, denoted IK(a, b), is the set
of hexagons which are contained on any of the shortest paths between a and b. A hexagonal
system is connected if it has a single connected component. A subset of faces K ⊆ F (H)
gives rise to two hexagonal systems: K and its complement K{.
We define a benzenoid in the following way:
Definition 3.1. A benzenoid is a connected hexagonal system K, such that each connected
component of the complement K{ is infinite.
A benzenoid is finite if it has a finite number of hexagons. Otherwise, it is called an
infinite benzenoid.
Example 3.2. Let k ∈ Z. Infinite hexagonal systems
Ξk = {h ∈ H | ξ(h) = k},
Hk = {h ∈ H | η(h) = k}, and
Zk = {h ∈ H | ζ(h) = k}
will be called lines. They are all benzenoids and they are all isomorphic to each other.
The hexagonal system K1 on Figure 2 is defined as
K1 = {h ∈ H | η(h) ≡ 0 (mod 2)} =
⋃
k∈Z
H2k.
K1 is not a benzenoid, because it is not connected. K1 consists of infinitely many disjoint
K1 K2 K3
Figure 2: Infinite hexagonal systems K1, K2 and K3.
lines and is isomorphic to its complement K{1 .
K2 is obtained from K1 by adding another line (with a different slope), i.e., K2 =
K1 ∪ Z0. The hexagonal system K2 is a benzenoid.
4 Art Discrete Appl. Math. 2 (2019) #P1.09
Hexagonal system K3 is defined as
K3 = {h ∈ H | η(h) ≥ 0}.
We call it a convex half-plane. In the present work, we will simply call it a half-plane, since
we will not consider other types of (non-convex) half-planes. It is an infinite benzenoid that
is isomorphic to its complement K{3 . ♦
The following theorem tells us that there are as many (non-isomorphic) infinite ben-
zenoids out there as there are real numbers.
Theorem 3.3. There exist uncountably many mutually non-isomorphic infinite benzenoids.
Proof. The interval [0, 1) has the cardinality of the continuum. Each number x ∈ [0, 1)
can be written in its binary representation
0.x1x2x3x4 . . . (3.1)
Note that xi ∈ {0, 1} for each i ∈ N and that
x =
∞∑
i=1
xi · 2−i. (3.2)
The sequence {xi}∞i=1 is uniquely determined if we require that for each n ∈ N there exists
an integer m > n such that xm 6= 1. For example, the number 1116 can be written in binary
representation as 0.1011.
Figure 3: Infinite benzenoid P 11
16
.
We will assign an infinite benzenoid to every such sequence {xi}∞i=1. Define
Px = {h ∈ H | η(h) ≤ 0} \ ({(−2, 0), (−1, 0)} ∪ {(2i− 1, 0) | i ∈ N ∧ xi = 1}) .
The infinite benzenoid Px is obtained from the half-plane P = {h ∈ H | η(h) ≤ 0} by
removing hexagons (−2, 0), (−1, 0) and all hexagon (2i− 1, 0) where i ∈ N and xi = 1.
For example, the infinite benzenoid that corresponds to number 1116 is shown in Figure 3.
It is not hard to see that Px  Py if and only if x 6= y. We constructed an injective
mapping from the set [0, 1) to the class of infinite benzenoids. Therefore, the class of all
infinite benzenoids is uncountable.
The boundary of a hexagonal system K consists of all edges and all vertices that are
indicent to (at least) one hexagon of K and (at lest) one hexagon of K{. Those vertices and
edges are called boundary vertices and boundary edges, respectively.
The boundary of a finite benzenoid is isomorphic to a cycle graph. The boundary of
an infinite benzenoid is a disjoint union of one or more infinite paths. The boundary of K3
in Figure 2 is a single infinite path. The boundary of K2 in Figure 2 consists of infinitely
many connected components (that are all infinite paths).
N. Bašić: Infinite benzenoids 5
Proposition 3.4. Let B be an arbitrary benzenoid. The boundary of B consists of countably
many connected components.
Proof. The edges ofH can be labeled with natural numbers in a spiral fashion as shown in
Figure 4. Let us define a mapping from the set of connected components of the boundary
12
3
4 5
6
7
8
9
10
11
12
13
14
15
16
17181920
21
22
23
24
25
. . .
Figure 4: “Spiral” labeling of edges ofH.
of B to natural numbers. Each connected component is mapped to the minimum among
all labels of the edges that belong to the component. This mapping to natural numbers is
injective and the result follows.
3.1 The boundary-edges code
Several combinatorial descriptions of finite benzenoids are readily available. In [11], Han-
sen et al. presented the boundary-edges code (abbreviated as BEC). The boundary of a
finite benzenoid (which is a cycle graph) is described as a cyclic sequence of numbers,
each of which counts the number of edges between two consecutive boundary vertices of
degree 3. All those numbers are from the set {1, 2, 3, 4, 5}. The only exception here is
benzene, which has BEC 6. In Figure 5, there are several finite benzenoids together with
their BECs. The boundary-edges code of B is denoted BEC(B).
The code BEC(B3) = 424242 of B3 from Figure 5 can also be written as (42)3, where
sk stands for ss . . . s︸ ︷︷ ︸
k
.
It is possible to generalise the definition of the BEC to infinite benzenoids. Each con-
nected component of the boundary will be assigned its own BEC. Since a connected com-
ponent of the boundary of an infinite benzenoid is an infinite path, the BEC can be formally
defined as a mapping Z→ {1, 2, 3, 4, 5}, i.e. a doubly infinite sequences.
Example 3.5. The boundary of a half-plane has a single connected component with the
BEC . . . 22222 . . ., which can simply be written as 2∞.
The boundary of benzenoid K2 in Figure 2 has infinitely many connected components.
They all have the same BEC, namely 2∞132∞.
The boundary of benzenoid P 11
16
in Figure 3 has a single connected component with
BEC 2∞31214123231241232∞. ♦
6 Art Discrete Appl. Math. 2 (2019) #P1.09
(a) B1, BEC(B1) = 6 (b) B2, BEC(B2) = 5252
(c) B3, BEC(B3) = 424242 (d) B4, BEC(B4) = 533113513311
Figure 5: Examples of finite benzenoids together with their BECs.
Infinite benzenoids can be classified with respect to the number of connected compo-
nents of the boundary.
Proposition 3.6. Let n ∈ N ∪ {0,∞}. There exists an infinite benzenoid B with n con-
nected components in the boundary of B. Symbol ∞ means that the boundary of B has
(countably) infinitely many connected components.
Proof. The benzenoid H, i.e. the one that contains all hexagons of the infinite hexagonal
grid, is the only one with 0 connected components in the boundary. The boundary of half-
plane P = {h ∈ H | η(h) ≥ 0} has exactly 1 connected component.
Let
Bk = P ∪ Ξ0 ∪ Ξ2 ∪ Ξ4 ∪ · · · ∪ Ξ2k.
It is easy to see that the boundary ofBk has k+2 connected components. In other words, for
every natural number n ≥ 2 there exist an infinite benzenoid, namely Bn−2, with exactly
n connected components in its boundary.
For the case n =∞, take K2 from Figure 2.
4 Convex (infinite) benzenoids
Let us recall the metric definition of a convex hexagonal system from [3]:
Definition 4.1. A hexagonal system K is convex if for any pair of its hexagons a and b the
whole interval IH(a, b) is contained in K.
Theorem 3.3 means that one cannot describe all of the infinite benzenoids algorithmi-
cally. This means that there exist infinite benzenoids for which there does not exist a finite
computer program for constructing them (even if the program runs infinitely long).
Let us consider convex infinite benzenoids. The whole hexagonal gridH and the empty
set ∅ are clearly convex. A half-plane is also convex. Each half-plane has a normal which
is pointing out of the half-plane (see Figure 6). There are exactly 6 possible directions of
N. Bašić: Infinite benzenoids 7
half-planes. We will denote them as follows:
HP+ξ (n) = {h ∈ H | ξ(h) ≥ n}, (4.1)
HP−ξ (n) = {h ∈ H | ξ(h) ≤ n}, (4.2)
HP+η (n) = {h ∈ H | η(h) ≥ n}, (4.3)
HP−η (n) = {h ∈ H | η(h) ≤ n}, (4.4)
HP+ζ (n) = {h ∈ H | ζ(h) ≥ n}, (4.5)
HP−ζ (n) = {h ∈ H | ζ(h) ≤ n}. (4.6)
(a) HP−η (n) (b) HP
−
ζ (n) (c) HP
−
ξ (n) (d) HP
+
η (n)
(e) HP+ζ (n) (f) HP
+
ξ (n)
Figure 6: The normal of a hexagonal half-plane can point in 6 different directions.
Note that the intersection of two half-planes with the same normal is equal to one of
the two. In other words, one is a sub-benzenoid of the other. For example,
HP+ξ (3) ∩HP
+
ξ (5) = HP
+
ξ (5).
Therefore, the interection of any number of half-planes is equal to an intersection of at most
6 of those half-planes. For each direction of the normal that is present in the list, we select
the half-plane that is contained in all other half-planes that have the same direction. Also,
note that all half-planes (4.1) – (4.6) are isomorphic to each other.
Definition 4.2. Let B be a benzenoid (finite or infinite). The smallest convex benzenoid
containing B is called the convex closure of B and is denoted Conv(B).
In [3], the following proposition was proved.
Proposition 4.3. Any intersection of convex (finite or infinite) benzenoids is a convex ben-
zenoid. 
8 Art Discrete Appl. Math. 2 (2019) #P1.09
Note that the empty set ∅ can also be considered as a convex benzenoid. To a chemist,
this means nothing concrete. To a mathematician, it is clear that every two members of an
empty set satisfy the condition in Definition 4.1, i.e., this condition is void.
(a) half-plane, HP (b) anvil, AN (c) wedge, WE
n
(d) strip, ST (n)
n
(e) chomped wedge, CW(n)
n
(f) knife, KN (n)
n
m
(g) sword, SW(n,m)
Figure 7: Families of convex infinite benzenoids.
In addition to the hexagonal grid H, the empty set ∅ and half-plane HP , we introduce
the following families of infinite benzenoids (see Figure 7):
(a) The benzenoid AN in Figure 7(b) is called anvil and is uniquely determined (up to
isomorphism) by BEC(AN ) = 2∞32∞.
(b) The benzenoidWE in Figure 7(c) is called wedge and is uniquely determined (up to
isomorphism) by BEC(WE) = 2∞42∞.
(c) A member of the one-parametric family of benzenoids ST (n), n ≥ 1, in Figure 7(d)
is called a strip (of width n) and cannot be uniquely determined by the BEC. How-
ever, ST (n) ∼= HP+ξ (0) ∩HP
−
ξ (n). Note that ST (1) is called a line.
(d) A member of the one-parametric family of benzenoids CW(n), n ≥ 2, in Fig-
ure 7(e) is called a chomped wedge and is uniquely determined (up to isomorphism)
by BEC(CW(n)) = 2∞32n−232∞.
N. Bašić: Infinite benzenoids 9
(e) A member of the one-parametric family of benzenoidsKN (n), n ≥ 1, in Figure 7(f)
is called a knife (of width n) and is uniquely determined (up to isomorphism) by
BEC(KN (n)) =
{
2∞32n−242∞ if n ≥ 2,
2∞52∞ if n = 1.
The benzenoid KN (1) will also be called a needle.
(f) A member of the two-parametric family of benzenoids SW(n,m), m ≥ n ≥ 2,
in Figure 7(g) is called a sword and is uniquely determined (up to isomorphism) by
BEC(SW(n)) = 2∞32n−232m−232∞.
All benzenoids on the above list can be obtaned as intersections of half-planes and are
therefore convex by Proposition 4.3.
In [3], the following proposition was proved.
Proposition 4.4. A finite benzenoid B is convex if and only if it can be obtained as an
intersection of half-planes, i.e., if there exist integers n+ξ , n
−
ξ , n
+
η , n
−
η , n
+
ζ and n
−
ζ , such
that
B = HP+ξ (n
+
ξ ) ∩HP
−
ξ (n
−
ξ ) ∩HP
+
η (n
+
η ) ∩HP
−
η (n
−
η ) ∩HP
+
ζ (n
+
ζ ) ∩HP
−
ζ (n
−
ζ ). 
Let B be a benzenoid. We define
η+ = max
h∈B
η(h) and η− = min
h∈B
η(h).
If the set {η(h) | h ∈ B} is not bounded from above, we write η+ = ∞. Similarly, if the
set {η(h) | h ∈ B} is not bounded from below, we write η− = −∞. Analogously, we
define
ξ+ = max
h∈B
ξ(h), ξ− = min
h∈B
ξ(h), ζ+ = max
h∈B
ζ(h) and ζ− = min
h∈B
ζ(h).
Lemma 4.5. Let B be a convex benzenoid. Then the following statements hold:
(1) If η+ <∞ and ξ+ <∞ then ζ+ <∞.
(2) If η− > −∞ and ξ− > −∞ then ζ− > −∞.
(3) If ξ+ <∞ and ζ− > −∞ then η− > −∞.
(4) If ξ− > −∞ and ζ+ <∞ then η+ <∞.
(5) If η+ <∞ and ζ− > −∞ then ξ− > −∞.
(6) If η− > −∞ and ζ+ <∞ then ξ+ <∞.
Proof. It is enough to prove statement (1) of the lemma. Other statements will results from
the fact that we may use a rotational symmetry of the hexagonal gridH.
Suppose that η+ <∞ and ξ+ <∞. This implies B ⊆ HP−η (η+) and B ⊆ HP
−
ξ (ξ
+).
Moreover, B ⊆ HP−η (η+) ∩HP
−
ξ (ξ
+). ButHP−η (η+) ∩HP
−
ξ (ξ
+) is a wedge in which
hexagon (ξ+, η+) obtains the maximal value of ζ coordinate. Therefore, ζ+ <∞.
10 Art Discrete Appl. Math. 2 (2019) #P1.09
The next result generalises Proposition 4.4 to infinite benzenoids.
Proposition 4.6. An benzenoid B (finite or infinite) is convex if and only if it can be ob-
tained as an intersection of half-planes.
Proof. The proof technique used here is similar to the one used in [3] to prove Proposi-
tion 4.4. If a benzenoid B is obtained as an intersection of half-planes then it is convex by
Proposition 4.3.
Now let B be a convex benzenoid. There are several cases to consider, depending on
the values of ξ+, ξ−, η+, η−, ζ+ and ζ−.
Suppose that ξ− > −∞, η− > −∞ and ζ+ < ∞. Statements (2), (4) and (6) of
Lemma 4.5 imply that ζ− > −∞, η+ <∞ and ξ+ <∞, respectively. This means that B
is finite and the result follows from Proposition 4.4.
We need to consider several more cases:
(i) ξ− = −∞, η− > −∞ and ζ+ <∞;
(ii) ξ− = −∞, η− = −∞ and ζ+ <∞;
(iii) ξ− = −∞, η− = −∞ and ζ+ =∞.
Note that because of the symmetry, there are only 3 cases to consider and not 23. We
provide the proof of case (i). The proofs of (ii) and (iii) are very similar and use the same
type of arguments.
(i): Suppose that ξ− = −∞, η− > −∞ and ζ+ < ∞. Statements (6) of Lemma 4.5
implies that ξ+ < ∞. Now consider ζ− and η+. If ζ− > −∞ and η+ < ∞ then by
statement (5) of Lemma 4.5 we obtain ξ− > −∞, a contradiction. We have two subcases:
(i.1) ζ− = −∞ and η+ =∞;
(i.2) ζ− = −∞ and η+ <∞.
Again, by the symmetry argument, we do not need to consider the case ζ− > −∞ and
η+ =∞. We will now consider case (i.1). The case (i.2) is analogous.
(i.1): From η− > −∞ it follows that there exists a hexagon hη− ∈ B such that
η(hη−) = η
−. From ζ+ < ∞ it follows that there exists a hexagon hζ+ ∈ B such
that ζ(hζ+) = ζ+. And from ξ+ < ∞ it follows that there exists a hexagon hξ+ ∈ B
such that ξ(hξ+) = ξ+. See Figure 8 for an illustration. Let h1, h2 ∈ H such that
η(h1) = η
−, ξ(h1) = ξ+, ζ(h2) = ζ+ and ξ(h2) = ξ+. Because h1 ∈ IH(hη−, hξ+) and
h2 ∈ IH(hξ+ , hζ+), it follows that h1, h2 ∈ B.
Let n be an arbitrary large integer. From ζ− = −∞ it follow that there exists a hexagon
h′ ∈ B such that ζ(h′) = −n. Let h′′ ∈ H be the hexagon with ζ(h′′) = −n and
η(h′′) = η−. Since h′′ ∈ IH(h′, h1) it follow that h′′ ∈ B. This means that B contains
the needle {h ∈ H | η(h) = η− ∧ ξ(h) ≤ ξ+}. Similarly, η+ = ∞ implies that B also
contains the needle {h ∈ H | ζ(h) = ζ+ ∧ ξ(h) ≤ ξ+}. The line segment between h1 and
h2 is also contained in B.
This means that all boundary hexagons of HP+η (η−) ∩ HP
−
ξ (ξ
+) ∩ HP−ζ (ζ+) are
contained in B. But B ⊆ HP+η (η−) ∩HP
−
ξ (ξ
+) ∩HP−ζ (ζ+) and therefore
B = HP+η (η−) ∩HP
−
ξ (ξ
+) ∩HP−ζ (ζ
+).
The remaining cases can be proved using the same approach.
N. Bašić: Infinite benzenoids 11
hζ+
hξ+
hη− h1
h2
h′
h′′
Figure 8: The case (i.1).
We are now able to prove the following theorem.
Theorem 4.7. An infinite benzenoid is convex if and only if it is isomorphic to one of the
following:
(a) the hexagonal gridH,
(b) the half-planeHP ,
(c) the anvil AN ,
(d) the wedgeWE ,
(e) a strip ST (n) for some n ≥ 1,
(f) a chomped wedge CW(n) for some n ≥ 2,
(g) a knife KN (n) for some n ≥ 1,
(h) a sword SW(n,m) for some m ≥ n ≥ 2.
Moreover, all benzenoids from the above list are pairwise non-isomorphic.
Proof. We already know that all infinite benzenoids listed in the statement of the theorem
are convex. It is not hard to see that they are also pairwise non-isomorphic.
Suppose that B is a convex infinite benzenoid. From Proposition 4.6 it follows that
it can be obtained as an intersection of half-planes. We can analyse (case by case) all
possibilities for the intersection of (any subset) of the 6 half-planes. In this analysis, we
either obtain a finite convex benzenoid (they were classified in [3]), which contradicts the
assumption that B is infinite, or one of the above.
Let FO be the class of all such infinite benzenoids B with the property that the total
number of 1s in BECs of all connected components of the boundary of B is finite.
12 Art Discrete Appl. Math. 2 (2019) #P1.09
Theorem 4.8. There are countably many benzenoids in the class FO.
Proof. Let On, n ≥ 0, be the finite benzenoid defined by BEC(On) = (32n)6.
Let B be any benzenoid of the class FO (see Figure 9 for an example). Because there
Figure 9: A benzenoid B ∈ FO.
are finitely many 1s in BECs of B, there exists some O′ = On for n large enough, such
that O′ contains all edges that correspond to 1s in BECs of B as internal edges (see Fig-
ure 10(a)). Then B \ O′ is a hexagonal system that comprises finitely many finite ben-
zenoids and finitely many infinite benzenoids. (In the example in Figure 10(a), there is 1
finite benzenoid and 2 infinite benzenoids.)
O′
(a)
O′′
(b)
Figure 10: A benzenoid B ∈ FO with O′ and O′′.
We can choose a (possibly larger) number m ≥ n, such that O′′ = Om contains O′
and all finite connected components of B \ O′ (see Figure 10(b)). If we remove all edges
of O′′ from the boundary of B, we obtain an even number of semi-infinite paths. No edge
on those semi-infinite paths is an edge that corresponds to a 1s in BECs of B, because such
N. Bašić: Infinite benzenoids 13
edges are all contained in O′. The subsequence of a BEC that corresponds to such a semi-
infinite path contains infinitely many 2s, but only a finite number of 3s, 4s and 5s. Those
numbers cause bends in the boundary and too many bends would result in a collision of the
boundary (see Figure 11), which is impossible. To encode the benzenoid B, we need the
collision
Figure 11: Collision of the boundary of B.
following information:
(i) the number m, which determines the O′′ (we have countably many choices),
(ii) the subset of hexagons of O′′ that determine B ∩ O′′ (there are finitely many such
subsets),
(iii) vetices on the boundary ofO′′ that are starting vertices of semi-infinite paths (finitely
many choices),
(iv) positions and types of bends on each semi-infinite path (there are finitely many bends
and each type and position can be encoded by a natural number).
From the above encoding of B it follows that there are countably many different benzenoids
in the class FO.
Corollary 4.9. There exist countably many mutually non-isomorphic convex infinite ben-
zenoids.
Proof. By Theorem 4.7, a convex infinite benzenoid is isomorphic to one of those listed in
the statement of Theorem 4.7. None of them has a 1 in the boundary-edges code of any
connected component of the boundary. Therefore, the class of convex infinite benzenoids
is a subclass of FO and the results follows by Theorem 4.8.
References
[1] N. Bašić, Algebraic Approach to Several Families of Chemical Graphs, Ph.D. thesis, University
of Ljubljana, 2016.
[2] N. Bašić, P. W. Fowler and T. Pisanski, Coronoids, patches and generalised altans, J. Math.
Chem. 54 (2016), 977–1009, doi:10.1007/s10910-016-0599-6.
14 Art Discrete Appl. Math. 2 (2019) #P1.09
[3] N. Bašić, P. W. Fowler and T. Pisanski, Stratified enumeration of convex benzenoids, MATCH
Commun. Math. Comput. Chem. 80 (2018), 153–172, http://match.pmf.kg.ac.rs/
electronic_versions/Match80/n1/match80n1_153-172.pdf.
[4] R. Cruz, I. Gutman and J. Rada, Convex hexagonal systems and their topological indices,
MATCH Commun. Math. Comput. Chem. 68 (2012), 97–108, http://www.pmf.kg.ac.
rs/match/electronic_versions/match68/n1/match68n1_97-108.pdf.
[5] S. J. Cyvin, J. Brunvoll and B. N. Cyvin, Theory of Coronoid Hydrocarbons, volume 54 of
Lecture Notes in Chemistry, Springer-Verlag, Berlin, 1991, doi:10.1007/978-3-642-51110-3.
[6] S. J. Cyvin, J. Brunvoll, B. N. Cyvin, R. S. Chen and F. J. Zhang, Theory of Coronoid Hy-
drocarbons II, volume 62 of Lecture Notes in Chemistry, Springer-Verlag, Berlin, 1994, doi:
10.1007/978-3-642-50157-9.
[7] S. J. Cyvin and I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons, volume 46 of Lecture
Notes in Chemistry, Springer-Verlag, Berlin, 1988, doi:10.1007/978-3-662-00892-8.
[8] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer, Berlin, 5th
edition, 2017, doi:10.1007/978-3-662-53622-3.
[9] I. Gutman and S. J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbons, Springer-
Verlag, 1989, doi:10.1007/978-3-642-87143-6.
[10] P. R. Halmos, Naive Set Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New
York, 1st edition, 1974, doi:10.1007/978-1-4757-1645-0.
[11] P. Hansen, C. Lebatteux and M. Zheng, The boundary-edges code for polyhexes, J. Mol. Struct.
(THEOCHEM) 363 (1996), 237–247, doi:10.1016/0166-1280(95)04139-7.
[12] T. Jech, Set Theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003, doi:
10.1007/3-540-44761-x.