ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.05
https://doi.org/10.26493/1855-3974.2631.be0
(Also available at http://amc-journal.eu)
The fullerene graphs with a perfect star packing*
Lingjuan Shi †
School of Software, Northwestern Polytechnical University,
Xi’an, Shaanxi 710072, P. R. China
Received 15 May 2021, accepted 23 March 2022, published online 29 September 2022
Abstract
Fullerene graph G is a connected plane cubic graph with only pentagonal and hexagonal
faces, which is the molecular graph of carbon fullerene. A spanning subgraph of G is called
a perfect star packing in G if its each component is isomorphic to K1,3. For an independent
set D ⊆ V (G), if each vertex in V (G) \D has exactly one neighbor in D, then D is called
an efficient dominating set of G. In this paper we show that the number of vertices of a
fullerene graph admitting a perfect star packing must be divisible by 8. This answers an
open problem asked by Došlić et al. and also shows that a fullerene graph with an efficient
dominating set has 8n vertices. In addition, we find some counterexamples for the necessity
of Theorem 14 of paper of Došlić et al. from 2020 and list some subgraphs that preclude
the existence of a perfect star packing of type P0.
Keywords: Fullerene graph, perfect star packing, efficient dominating set.
Math. Subj. Class. (2020): 05C70, 05C92
1 Introduction
A chemical graph is a simple finite graph in which vertices denote the atoms and edges
denote the chemical bonds in underlying chemical structure. Perfect matchings of a chemi-
cal graph correspond to Kekulé structures of the molecule, which feature in the calculation
of molecular energies associated with benzenoid hydrocarbon molecules [20]. Alternat-
ing sextet faces (sextet patterns) also play a meaningful role in the prediction of molecular
stability, in particular, but not only, in benzenoid compounds. Although for fullerenes,
the above two structures do not play the same role as in benzenoid compounds, they have
received considerable attention in recent years, see [1, 4, 8, 13, 17, 21, 32, 33] etc..
*This work was supported in part by the National Natural Science Foundation of China (grant no. 11901458
and 11871256) and by the Fundamental Research Funds for the Central Universities (grant no. D5000200199).
†The author is very grateful to Wuyang Sun and the anonymous referees for their careful reading and valuable
comments, which greatly improved this paper.
E-mail address: shilj18@nwpu.edu.cn (Lingjuan Shi)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P1.05
A perfect matching in a graph G may be viewed as a collection of subgraphs of G,
each of which is isomorphic to K2, whose vertex sets partition the vertex set of G. This is
naturally generalized by replacing K2 by an arbitrary graph H . For a given graph H , an
H-packing of G is the set of some vertex disjoint subgraphs, each of which is isomorphic
to H . From the optimization point of view, the maximum H-packing problem is to find
the maximum number of vertex disjoint copies of H in G called the packing number. An
H-packing in G is called perfect if it covers all the vertices of G. If H is isomorphic to
K2, the maximum (perfect) H-packing problem becomes the familiar maximum (perfect)
matching problem. If H is the cycle C6 of length 6, for a fullerene or a hexagonal system
G, the packing number is related to the Clar number (the maximum number of mutually
disjoint sextet patterns) of G. If H is the star graph K1,3, it is the maximum star packing
problem. If a K1,3-packing covers all the vertices of G, we call it being a perfect star
packing. For a given family F of graphs, an H-packing concept can also be generalized to
an F-packing (we refer the reader to [29] for the definition).
Packing in graphs is an effective tool as it has lots of applications in applied sciences.
H-packing, is of practical interest in the areas of scheduling [5], wireless sensor tracking
[6], wiring-board design, code optimization [23] and many others. Packing problems were
already studied for carbon nanotubes [2]. Packing lines in a hypercube had been studied
in [15]. H-packing was determined for honeycomb [29] and hexagonal network [28]. For
representing chemical compounds or to problems of pattern recognition and image pro-
cessing, P3-packing has some applications in chemistry [30]. Packing stars in fullerene
graph have been investigated in [14] by Doslić et al.. For any integer n ≥ 5, they found
a fullerene graph of order 8n which has a perfect star packing. So they raised an open
problem “Is there a fullerene on 8n+ 4 vertices with a perfect star packing?”.
In the following section we introduce necessary preliminaries and characterize the clas-
sical fullerenes which have a perfect star packing. Section 3 gives a negative answer to the
open problem asked by Doslić et al. [14]. This implies that a fullerene graph with an effi-
cient dominating set must has 8n vertices. In Section 4, we generalize the Proposition 1 in
reference [14] and give three counterexamples for the necessity of Theorem 14 in the same
paper. We also list some subgraphs that preclude the existence of a perfect star packing of
type P0.
2 Characterization of fullerenes with a perfect star packing
A fullerene graph (simply fullerene) is a cubic 3-connected plane graph with only pen-
tagonal and hexagonal faces. By the Euler formula, each fullerene graph has exactly 12
pentagons. Such graphs are suitable models for carbon fullerene molecules: carbon atoms
are represented by vertices, whereas edges represent chemical bonds between two atoms
(see [16, 26]). For all even n ≥ 24 and n = 20, Grünbaum and Motzkin [19] showed that
there exists a fullerene graph with n vertices. Using a similar approach, Klein and Liu [24]
proved that a fullerene graph with isolated pentagons of order n exists for n = 60 and for
each even n ≥ 70. We refer the reader to the reference [16] for more details on fullerene
graphs.
A cycle of a fullerene graph G is a facial cycle if it is the boundary of a face in G,
otherwise, it is a non-facial cycle. Clearly, each pentagon and hexagon in G is a facial
cycle since G is 3-connected and any 3-edge-cut is trivial [31]. In paper [14], the authors
obtained the following basic conclusions.
L. Shi: The fullerene graphs with a perfect star packing 3
Proposition 2.1 ([14]). Let S be a perfect star packing of fullerene graph G. Then each
pentagon of G can contain at most one center of a star in S.
Lemma 2.2 ([14]). Let S be a perfect star packing of fullerene graph G. Then a vertex
shared by two pentagons of G cannot be the center of a star in S.
Recall that a vertex set X of a graph G is said to be independent if any two vertices in X
are not adjacent in G. A cycle C = v1v2 · · · vkv1 in G is called induced if vi has only two
adjacent vertices vi+1 and vi−1 around the k vertices v1, v2, · · · , vk (note that i + 1 := 1
if i = k, and i − 1 := k if i = 1). Otherwise, there exists some i and j /∈ {i − 1, i + 1}
such that vi and vj are adjacent in G, the edge vivj is a chord of C and C is not induced.
A subgraph R of a graph G is spanning if R covers all the vertices of G. For a vertex v of
a graph G, we call vertex u being a neighbor of v in G if u is adjacent to v in G.
Theorem 2.3. Let G be a fullerene graph. Then G has a perfect star packing if and only
if G has an independent vertex set S∗ such that each component of G − S∗ is an induced
cycle in G.
Proof. If G has a perfect star packing S, then S is a spanning subgraph of G and any
component in S is isomorphic to a star graph K1,3. Let S∗ be the set of all 3-degree
vertices in S. Clearly, S∗ is an independent vertex set in G and any vertex in G − S∗ has
degree 2. So each component of G− S∗ is an induced cycle in G.
Let S∗ be an independent vertex set of G such that each component of G − S∗ is an
induced cycle in G. Clearly, each vertex in S∗ and its three neighbors induce a star graph
K1,3. We collect all these star graphs and denote this set by H. For any vertex x on a cycle
C in G−S∗, x has exactly one neighbor in S∗ since G is 3-regular and induced cycle C is
a component of G− S∗. So H is a spanning subgraph of G and each component of H is a
star graph K1,3, that is, H is a perfect star packing of G.
We note that star graph K1,3 has exactly one center (the vertex of degree 3) and three
leaves. For a perfect star packing S of fullerene graph G, each 1-degree vertex in S is a
leaf. In the following, we denote by C(S) the set of all the centers of stars in S.
Remark 2.4. Let S be a perfect star packing of fullerene graph G. Then
(1) C(S) is an independent vertex set in G.
(2) Any leaf in S has exactly one neighbor belonging to C(S) and has exactly two neigh-
bors being leaves in S.
(3) Each cycle in G− C(S) does not have a chord.
Proposition 2.5. Each hexagon can contain at most two centers of a perfect star packing
of fullerene graph G. If a hexagon h contains two such centers, then they are antipodal
points on the hexagon h.
Proof. Let h be a hexagon in G. We denote the six vertices of h by v1, v2, . . . , v6 in the
clockwise direction. If vertex v1 is the center of a star H in a perfect star packing S of G,
then v2 and v6 are two leaves in H . Hence both v3 and v5 are leaves in S by Remark 2.4(2).
Clearly, v4 could be the center of a star in S. Hence h has at most two centers of S and if
h contains two such centers, then they are antipodal points on h.
4 Ars Math. Contemp. 23 (2023) #P1.05
3 The order of fullerenes with a perfect star packing
To show the main conclusion, we need to prepare as follows.
(a) ( )b ( )c
x
1x
2x
3x
1v
2v
3v
1u
2u
3u1w
2w
3w
x
1x
2x
3x
2f
1f1v
2v
3v
1u
2u
3u1w
2w
3w
1y
2y
x
1x
4x
2x
3x
2u
1u
1f 2f
1v
2v
3v
3u1
w
2w
3w
f
Figure 1: (a) Type 1; (b) Type 2; (c) Type 3.
Lemma 3.1. Let S be a perfect star packing of fullerene graph G. Then for any vertex
x ∈ C(S), all the vertices on the three faces sharing x are covered by S as Type 1, Type 2
or Type 3 (see Figure 1, S are depicted in bold lines).
Proof. By the Lemma 2.2, at most one of the three faces sharing x is a pentagon since
x ∈ C(S). There are two cases as follows.
Case 1: The three faces sharing x are all hexagons.
Clearly, x has three antipodal points on the three hexagons sharing x, denoted by x1,
x2 and x3 respectively as depicted in Figure 1(a). By Remark 2.4(2), the two neighbors v1
and v3 of v2 are leaves in S. Similarly, u1, u3, w1 and w3 are also leaves in S. We claim
that at least two of x1, x2 and x3 are centers of stars in S. If x1 is not the center of a star
in S, then x1 is a leaf in S. So the third neighbor of v1, say y1, is the center of a star in S
(see Figure 1(b)). Similarly, the third neighbor of w3, say y2, is also the center of a star in
S. Since the three vertices v1, v2 and v3 are leaves in S and y1 ∈ C(S), the face f1 has
only one center of S by Propositions 2.5 and 2.1. Hence the two neighbors of v3 on f1 are
leaves. By Remark 2.4(2), x3 is the center of a star in S, that is, x3 ∈ C(S). Similarly,
w1 is a leaf in S and the two neighbors of w1 on f2 are all leaves in S. Hence x2 ∈ C(S).
So at least two of x1, x2 and x3 belong to C(S). If exactly two of x1, x2 and x3 belong
to C(S), without loss of generality, we suppose that x2, x3 ∈ C(S), then all the vertices
on the three faces sharing x are covered by S as Type 2. If all the three vertices x1, x2 and
x3 belong to C(S) (see Figure 1(a)), then all the vertices on the three faces sharing x are
covered by S as Type 1.
Case 2: Exactly one of the three faces sharing x is a pentagon.
By Proposition 2.1, w1 and u3 are leaves in S (see Figure 1(c)). Hence x4, x3 ∈ C(S)
and f is a hexagon by Remark 2.4(2) and Proposition 2.5. By Remark 2.4(2), the neighbor
w3 of w2 is a leaf in S since the neighbor x of w2 belongs to C(S). Hence the other vertices
on f1 except for x4 are all leaves in S by Propositions 2.1 and 2.5. This follows that the
neighbor x1 of w3 is the center of a star in S by Remark 2.4(2). Similarly, we can show
L. Shi: The fullerene graphs with a perfect star packing 5
x2 ∈ C(S). Hence all the vertices on the three faces sharing x are covered by S as Type 3
(see Figure 1(c)).
Corollary 3.2. Let S be a perfect star packing of fullerene graph G. If a pentagon P of G
has a vertex x ∈ C(S), then G − C(S) has a non-facial cycle C of G such that the path
P − x is a subgraph of C.
Proof. By Proposition 2.2, x is shared by this pentagon P and two hexagons. So all the
vertices on the three faces sharing x are covered by S as Type 3 (see Figure 1(c)). Clearly,
the path P − x is a subgraph of a cycle C in G − C(S) and C is a non-facial cycle of
G.
We note that 3-connected graphs have only one embedding up to equivalence [12]. If
we embed a fullerene graph G in the plane, then any non-facial cycle C of G as a Jordan
curve separates the plane into two regions, denoted by R∗1 and R
∗
2, each of which has the
entire C as its frontier. We denote the subgraph of G induced by the vertices lying in the
interior of R∗i by Gi, i = 1, 2. Here we note that {V (G1), V (G2), V (C)} is a partition of
all the vertices of G. We say that C divide the graph G into two sides G1 and G2.
Theorem 3.3. Let S be a perfect star packing of fullerene graph G and C be a cycle in
G− C(S). Then C(S) does not have a vertex which has three neighbors on C.
x
1x
2x 3
x
1v
kv
1u tu
h
1C
2C
3C
(a) (b)
x
1x
2x 3
x
1v
kv
1u tu
h
1C
2C
3C
y
'y
1kv -
2kv -
2u
'h
f
Figure 2: x ∈ C(S) has three neighbors on C.
Proof. If C is a facial cycle of G, then C is a pentagon or a hexagon. The conclusion
clearly holds. Now, let C be a non-facial cycle of G. Then C divides G into two sides,
denoted by H1 and H2 respectively. We note that all vertices on C are leaves in S since
C is a cycle in G − C(S). On the contrary, we suppose that there is a vertex x ∈ C(S)
which has three neighbors on C, denoted by x1, x2 and x3 respectively. Without loss of
generality, we suppose that x ∈ V (H1) (see Figure 2(a)). The three vertices separate the
circle C into three sections, denoted by C1, C2 and C3 respectively, each of which is a
path with xi and xi+1 as two terminal ends, i = 1, 2, 3 (if i = 3, then i + 1 := 1). From
Lemma 3.1 we know that at most one of x1C1x2x, x2C2x3x and x3C3x1x is a facial cycle
of G since C is a cycle in G − C(S). Next, we suppose that x1C1x2x and x2C2x3x are
non-facial cycles of G. Let C1 = x1v1v2 · · · vkx2, C2 = x2u1u2 · · ·utx3. So k ≥ 5 and
6 Ars Math. Contemp. 23 (2023) #P1.05
t ≥ 5 since any non-facial cycle of G has length at least 8. By Remark 2.4(3), C does not
have a chord. So v1vk /∈ E(G) and u1ut /∈ E(G). This implies that h is a hexagon face
of G, and x1, x, x2 and v1, vk are five vertices on h. We denote the sixth vertex of h by y.
Clearly, y ∈ V (H1) by the planarity of G (see Figure 2(b)). Similarly, both u1 and ut have
a common neighbor in H1.
Since S is a perfect star packing of G and the two neighbors x1 and v2 of v1 are leaves
in S, y is the center of a star in S. If the third neighbor of y is on C, then it is on C1,
denoted it by vr. The three neighbors of y separate the circle C into three sections, two of
which are subgraphs of C1, denoted by C11 and C
2
1 respectively. As the above discussion,
we know that one of v1C11vry and vrC
2
1vky is a non-facial cycle of G. By the recursive
process and the finiteness of the order of G, we can suppose that the third neighbor of y is
not on C, and denoted it by y′.
See Figure 2(b), the five vertices vk−1, vk, x2, u1, u2 belong to a common facial cycle
h′ of G. Since C does not have a chord by Remark 2.4(3), vk−1 and u2 are not adjacent
in G. So h′ is a hexagon. By the planarity of G, vk−1 and u2 have a common neighbor
in H2. so vk−2, vk−1, vk, y and y′ are on a face of G, say f . If f is a pentagon, then
vk−2 is adjacent to y′. So all the three neighbors of vk−2 are leaves in S. This implies
a contradiction since vk−2 is also a leaf in S. If f is a hexagon, then vk−2 and y′ have
a common neighbor, denoted by z. Clearly, z is vk−3 or not. For z = vk−3, the three
neighbors of vk−3 are all leaves in S, a contradiction. For z ̸= vk−3, by Remark 2.4(2),
z is a leaf in S since y′ has a neighbor y ∈ C(S). So the three neighbors of vk−2 are
all leaves in S, a contradiction. All these contradictions imply that C(S) does not have a
vertex which has three neighbors on C.
Let S be a perfect star packing of fullerene graph G and C be a cycle in G − C(S)
which is a non-facial cycle of G. C divides G into two sides, denoted by H1 and H2
respectively. Set Ci be the set of all the vertices on C each of which has a neighbor in Hi,
i = 1, 2. Clearly, {C1, C2} is a partition of V (C). G[Ci] is a vertex induced subgraph of
G which has vertex set Ci and any two vertices of Ci are adjacent if and only if they are
adjacent in G. See Figure 4, G[C1] is depicted as red and G[C2] is depicted as blue. In the
following, we use these symbols no longer explaining.
Lemma 3.4. For i = 1, 2, if a vertex x on C has a neighbor in Hi, then the component of
the induced subgraph G[Ci] which contains x is a path with 2 or 3 vertices.
Proof. We suppose that x on C has a neighhbor in H1. For the convenience of the following
description, set C := xv1v2 · · · vkx. Since C is a cycle in G− C(S) which is a non-facial
cycle of G, the length of C is at least 8. So k ≥ 7. There are three cases for the two
neighbors v1 and vk of x on C.
Case 1: Both v1 and vk have neighbors in H2.
In this case, the three vertices v1, x and vk lie on the same face f of G (see Figure 3(a)).
Since all the vertices on C are leaves in S, the other neighbor of v1 (resp. vk) which is not
on C is the center of a star in S. So f has two vertices in C(S) which are the centers of
two stars in S covered v1 and vk, respectively. So f is a hexagon by Proposition 2.1. But
the case cannot hold by Propositions 2.5.
Case 2: Both v1 and vk have neighbors in H1.
In this case, the five vertices v2, v1, x, vk, vk−1 belong to a facial cycle h of G (see
Figure 3(b)). We claim that both v2 and vk−1 have neighbors in H2. Otherwise, at least
L. Shi: The fullerene graphs with a perfect star packing 7
x
1v
2v
3v 1kv -
kvg
4v
2kv -
1H
2H
x
1v
2v
3v
1kv -
kv
h
4v
2kv -
1H
2H
3kv -
( )c( )b(a)
x
1v
2v
1kv -k
v
f
2kv -
1H
2H
Figure 3: (a) v1 and vk have neighbors in H2; (b) v1 and vk have neighbors in H1; (c) v1
has a neighbor in H1, vk has one in H2.
one of v2 and vk−1 has a neighbor in H1. If v2 has a neighbor in H1 and vk−1 has a
neighbor in H2, then the six vertices v3, v2, v1, x, vk, vk−1 lie on a face h of G. So h is a
hexagon and C has a chord v3vk−1, a contradiction. For v2 having a neighbor in H2 and
vk−1 having a neighbor in H1, we can also obtain a chord of C, a contradiction. If both v2
and vk−1 have neighbors in H1, then the seven vertices v3, v2, v1, x, vk, vk−1, vk−2 belong
to a common face h of G. This implies that G has a facial cycle of length at least 7, a
contradiction. So both v2 and vk−1 have neighbors in H2, and v2, v1, x, vk, vk−1 lie on
a hexagon h of G (see Figure 3(b)). Since C does not have a chord, the path v1xvk is a
connected component of the induced subgraph G[C1].
Case 3: v1 has a neighbor in H1 and vk has a neighbor in H2, or v1 has a neighbor in
H2 and vk has a neighbor in H1.
By symmetry, it is sufficient to consider that v1 has a neighbor in H1 and vk has a
neighbor in H2. If v2 has a neighbor in H1, then v3 must have a neighbor in H2, otherwise,
C has a chord or G has a facial cycle of length at least seven, a contradiction. As the proof
of Case 2, v3, v2, v1, x, vk lie on a hexagonal facial cycle. So the path v2v1x is a connected
component of the induced subgraph G[C1]. Now, we suppose that v2 has a neighbor in H2.
Then the four vertices vk, x, v1, v2 lie on the same face g of G. Since vk, x, v1, v2 are all
leaves in S, g is a pentagon and v2, vk have a common neighbor in H2 which is the center
of a star in S (see Figure 3(c)). So the path xv1 is a connected component of the induced
subgraph G[C1].
In summary, the component of the induced subgraph G[C1] which contains x is a path
with 2 or 3 vertices since C does not have a chord.
In addition, we have the following Lemma.
Lemma 3.5. Each component of G[Ci] is a path with 2 or 3 vertices, i = 1, 2.
Proof. For any vertex x on C, x must have exactly one neighbor in H1 or H2 since G is
3-regular and C does not have a chord. Without loss of generality, we suppose that x has
exactly one neighbor in H1. By Lemma 3.4, the component of the induced subgraph G[C1]
which contains x is a path with 2 or 3 vertices. We note that the choice of x is arbitrary. So
the conclusion holds.
8 Ars Math. Contemp. 23 (2023) #P1.05
1f
2f
3f
4f
5f
(a) ( )b
1H
2H
1H
2H
Figure 4: (a) A cycle C of length 25; (b) A cycle C of length 30. (G[C1] is red and G[C2]
is blue.)
Proposition 3.6. Let C = v0v1 · · · vk−1 be a non-facial cycle in G−C(S) (In the follow-
ing, the subscript is modulo k).
(i) If both vi and vi+1 have neighbors in H1 (resp. H2) and vi−1 and vi+2 have neigh-
bors in H2 (resp. H1), then the four vertices vi−1, vi, vi+1 and vi+2 lie on a pen-
tagon of G.
(ii) If vi, vi+1, vi+2 have neighbors in H1 (resp. H2) and vi−1 and vi+3 have neighbors
in H2 (resp. H1), then the five vertices vi−1, vi, vi+1, vi+2 and vi+3 lie on a hexagon
of G.
(iii) For j = 1, 2, if both vi and vi+1 have neighbors in Hj (we denote the two edges
incident to vi and vi+1 not lie in C by ei and ei+1, respectively), then the facial
cycle containing both ei and ei+1 is a hexagon, and two antipodal points on this
hexagon are centers of two stars in the perfect star packing S.
Proof. Cases (i) and (ii) can be easily obtained from the proof of the Cases 2 and 3 of
Lemma 3.4 (see Figure 3). Since all the vertices on C are leaves in the perfect star packing
S, the other end of ei (resp. ei+1) which is not on C, denoted by ui (resp. ui+1), is the
center of a star in S. We know that any facial cycle of G is a pentagon or a hexagon. So ui
and ui+1 are distinct. By Lemmas 2.1 and 2.5, the facial cycle containing both ei and ei+1
is a hexagon, and ui and ui+1 are antipodal points on this hexagon.
For example, in Figure 4, except for fi, i ∈ {1, 2, 3, 4, 5} the other faces sharing edges
L. Shi: The fullerene graphs with a perfect star packing 9
with C are all hexagons. Moreover, how the vertices on C being covered by S is deter-
mined.
We recall that the union of two graphs G1 and G2 is denoted by G1 ∪ G2, which has
vertex set V (G1) ∪ V (G2) and edge set E(G1) ∪ E(G2). Let n3 be the number of the
components of G[C1]∪G[C2] each of which is isomorphic to a path with 3 vertices. Sim-
ilarly, n2 is the number of the components of G[C1] ∪G[C2] each of which is isomorphic
to a path with 2 vertices. For example, n3 = n2 = 5 in Figure 4(a) and n3 = 10, n2 = 0
in Figure 4(b).
Observation 1. n2 + n3 is even.
Proposition 3.7. Let S be a perfect star packing of fullerene graph G and C a cycle in
G − C(S) which is a non-facial cycle of G. Then the length of C is 3n3 + 2n2, and the
length of C has the the same parity with n2 and n3.
Proof. Clearly, the length of C is 3n3 + 2n2 by Lemma 3.5. So n3 is odd if and only if
the length of C is odd. Since n2 + n3 is even by Observation 1, the parity of n2 and n3 are
same. Then we are done.
Theorem 3.8. Let S be a perfect star packing of fullerene graph G. Then G − C(S) has
even number of odd cycles.
Proof. If G − C(S) does not have a non-facial cycle of G, then any pentagon of G does
not have a vertex in C(S) by Corollary 3.2. So all the vertices on pentagons are leaves in
S. It implies that G − C(S) has exactly twelve odd cycles, each of which is a pentagon.
Next, we suppose that G− C(S) has a non-facial cycle of G, denoted by C.
Claim 1: If C is an even cycle, then G has even number of pentagons which share
edges with C. If C is an odd cycle, then G has odd number of pentagons which share
edges with C.
By Proposition 3.6, the number of pentagons which share edges with C is equal to n2.
By Proposition 3.7, n2 and the length of C have the same parity. So the Claim holds.
Claim 2: Any pentagon of G shares edges with at most one non-facial cycle in
G− C(S).
Let P be a pentagon of G. By Proposition 2.1, P has at most one vertex which is the
center of a star in S. If P does not have a vertex in C(S), then P is a cycle in G − C(S).
By Theorem 2.3, each component of G − C(S) is an induced cycle of G. So P does not
share edges with any non-facial cycle in G − C(S). If P has a vertex x ∈ C(S), then by
Corollary 3.2 P − x is a subgraph of a non-facial cycle in G − C(S). So P shares edges
with exactly one non-facial cycle in G− C(S).
Now, we consider the following two cases for the non-facial cycles in G− C(S).
Case 1: G− C(S) does not have a non-facial cycle of odd length.
Then any non-facial cycle C in G−C(S) is of even length. By the above Claims, there
are even number of pentagons in G such that they share edges with C. Since G has exactly
twelve pentagons, there are even number of pentagons in G each of which does not share
edges with non-facial cycles in G − C(S). These pentagons must be cycles in G − C(S)
by Corollary 3.2. Hence G− C(S) has even number of odd cycles.
Case 2: G− C(S) has some non-facial cycle of odd length.
Suppose that G − C(S) has exactly k non-facial cycles of odd length. We denote the
number of pentagons in G each of which does not share edges with non-facial cycles in
10 Ars Math. Contemp. 23 (2023) #P1.05
G − C(S) by p. These p pentagons must be cycles in G − C(S) by Corollary 3.2. So
G − C(S) has p + k odd length cycles. Next, we show that p and k have the same parity.
If p is odd, then G has odd number of pentagons each of which share edges with exactly
one non-facial cycle in G−C(S) since G has exactly 12 pentagons. By the above Claims,
for each even length non-facial cycle in G−C(S), G has even number of pentagons which
share edges with the cycle, and for each odd length non-facial cycle in G − C(S), G has
odd number of pentagons which share edges with the cycle. So G−C(S) has odd number
of non-facial cycles of odd length. This means that k is odd. For p being even, we can
similarly show that k is even. So k and p have the same parity and p+ k is even.
Clearly, for a fullerene graph G with a perfect star packing, its order must be divisible
by 4. So the order of G is 8k or 8k+4 for some positive integer k. Now, we can obtain the
following main theorem which illustrates that the order of G can not be 8k + 4.
Theorem 3.9. If fullerene graph G has a perfect star packing, then the order of G is
divisible by 8.
Proof. We suppose that S is a perfect star packing of G and Co and Ce are the collections of
all the odd cycles and even cycles in G− C(S), respectively. Then we have the following
equation.
|V (G)| = |C(S)|+
∑
C∈Co
|C|+
∑
C∈Ce
|C|
=
|V (G)|
4
+
∑
C∈Co
|C|+ even.
(3.1)
By Theorem 3.8, Co has even number of elements. Combining the above equation, we
know that |V (G)|4 × 3 is even. Hence
|V (G)|
4 is even, that is, the order of G is divisible by
8.
This theorem is equivalent to the following corollary.
Corollary 3.10. A fullerene graph with order 8n+4 does not have a perfect star packing.
We recall that a dominating set of a graph G is a set D of vertices such that each vertex
in V (G)−D is adjacent to a vertex in D. Moreover, if each vertex in V (G)−D is adjacent
to exactly one vertex in D and D is an independent vertex set, then D is called efficient.
The problem of determining the existence of efficient dominating sets in some families of
graphs was first investigated by Biggs [7] and Kratochvil [25]. Later Livingston and Stout
[27] studied the existence and construction of efficient dominating sets in families of graphs
arising from the interconnection networks of parallel computers. It is algorithmically hard
to find an efficient dominating set [3]. For more results and some historical background
regarding efficient dominating set, we refer the reader to [9, 10, 11, 22] etc..
From the definitions of the efficient dominating set and the perfect star packing of a
fullerene graph, the following proposition is a natural result.
Proposition 3.11 ([14]). A fullerene graph G with n vertices has a perfect star packing if
and only if G has an efficient dominating set of cardinality n4 .
Combining Theorem 3.9 and Proposition 3.11, we get the following theorem.
Theorem 3.12. The order of a fullerene graph with an efficient dominating set is 8n.
L. Shi: The fullerene graphs with a perfect star packing 11
4 Some other conclusions
Došlić et al. gave the following necessary condition in terms of graph spectra.
Proposition 4.1 ([14]). If a fullerene graph G has a perfect star packing, then −1 must be
an eigenvalue of the adjacency matrix of G.
The proof of this Theorem can be translate to a simple r-regular graph. Here for com-
pleteness, we prove as follows. For the definition of eigenvalues of the adjacency matrix of
a graph, we refer the reader to [18].
Theorem 4.2. If a simple r-regular graph G has a perfect K1,r-packing S, then −1 must
be an eigenvalue of the adjacency matrix of G.
Proof. Let C(S) be the set of centers of stars K1,r in S. We define the characteristic vector−→c ∈ R|V (G)| of C(S) as follows: ci = 1 if i ∈ C(S), otherwise ci = 0. Since G is a
r-regular graph, we have A−→u = r−→u , where A is the adjacency matrix of G and −→u is the
all one vectors. Let −→w = −→u − (r + 1)−→c . As A−→c = −→u −−→c , we have
A−→w = A−→u − (r+1)A−→c = r−→u − (r+1)−→u +(r+1)−→c = (r+1)−→c −−→u = −−→w (4.1)
This means that −1 is an eigenvalue of A.
For a perfect star packing S of fullerene graph G, if for each center x ∈ C(S), all the
three faces of G sharing x are hexagons, then we call S being type P0. For such perfect
star packing, the following corollary holds.
Corollary 4.3. If a fullerene graph G has a perfect star packing S of type P0, then G −
C(S) does not have a non-facial cycle of odd length.
Proof. By the contrary, we suppose that G−C(S) has a non-facial cycle C of odd length.
By the Claim 1 of Theorem 3.8, G has a pentagon P which share edges with C. This
implies that P contains the center y of a star in S. So one of the three faces of G sharing
y is not a hexagon. This contradicts that S is of type P0. So G − C(S) does not have a
non-facial cycle of odd length.
In the above Corollary, we note that G − C(S) may have non-facial cycles of even
lengths (see Figure 5, the blue cycle in C120).
Now, we point out the flaw of the Theorem 14 in [14].
Theorem 4.4 ([14]). A fullerene graph on 8n vertices has a perfect star packing of type
P0 if and only if it arises from some other fullerene via the chamfer transformation.
Readers can consult reference [14] to see the chamfer transformation. Here for com-
pleteness, we introduce it as follows. Let F be a fullerene graph. In each face g of F , we
draw a polygon with the same number of sides as g. For each vertex v ∈ V (F ), we connect
v with three new vertices each of which is inside exactly one face of F incident with v (see
Figure 6, the vertices of original fullerene C20 are black, the new vertices are blue, each
black vertex are connected to three blue vertices). We notice that each new vertex must be
adjacent to exactly one vertex of F in this process, and the edges do not intersect inside.
Finally, we remove all the edges of F . The resulting graph is called arising from F via the
chamfer transformation. For example, (see Figure 6) the graph C80(Ih) arises from C20
12 Ars Math. Contemp. 23 (2023) #P1.05
120
C
144
C
384
C
Figure 5: Each of C120, C144, C384 has a unique perfect star packing of type P0 which is
depicted in bold edges.
L. Shi: The fullerene graphs with a perfect star packing 13
Figure 6: C20 is drawn in black line, C80(Ih) is drawn in red line.
via the chamfer transformation, and all the black vertices are the centers of stars in a perfect
star packing of type P0 of C80(Ih).
For a perfect star packing S of type P0 in fullerene graph G, we construct a new graph
with respect to S, and denoted it by GS . V (GS) := C(S) and any two vertices in V (GS)
are adjacent if and only if they belong to the same hexagon of G. In the proof of the
necessity of the Theorem 4.4, there exist the following problem. GS is planar, but does
not have to be 3-regular, 3-connected and have only pentagonal and hexagonal faces. For
example, it is easy to check that the fullerene graph C120 (resp. C144, C384) has a unique
perfect star packing S1 (resp. S2, S3) of type P0 (as depicted in bold edges in Figure 5).
CS1120, C
S2
144 and C
S3
384 are planar and not connected (the red dashed line in Figure 5 is the
CS1120, and here we omit the C
S2
144 and C
S3
384). In fact, we have Lemma 4.5.
I would like to thank Tomislav Došlić for conversations and email exchanges related to
the contents of this paragraph.
Lemma 4.5. The three fullerene graphs C120, C144 and C384 as depicted in Figure 5 can-
not arise from some other fullerene via the chamfer transformation.
Proof. On the contrary, we suppose that C120 can arise from some fullerene F via the
chamfer transformation. Then C120 has a perfect star packing S of type P0 which corre-
sponds to the chamfer transformation of F , that is, all the vertices of F are the centers of
stars in S. This means that CS120 = F .
We can check that C120 has a unique perfect star packing of type P0, denoted by S1
(as depicted in bold edges in Figure 5). So S1 = S. However, CS1120 is not connected (as
depicted by red dotted lines in Figure 5). So S1 ̸= S, a contradiction.
For the other two fullerenes C144 and C384, we can also check that each of them has a
unique perfect star packing of type P0 (as depicted in bold edges in Figure 5). As the above
proof, they also cannot arise from any fullerene graphs via the chamfer transformations.
From Lemma 4.5 we know that the necessity of Theorem 4.4 does not hold, however,
its sufficiency is right. So it can be corrected as follows.
14 Ars Math. Contemp. 23 (2023) #P1.05
Theorem 4.6. A fullerene graph that arises from some other fullerene via the chamfer
transformation must have a perfect star packing of type P0.
If fullerene graph G has two pentagons sharing an edge xy, then x (resp. y) can not be
center of a star in a perfect star packing of G by Lemma 2.2. Since all the three neighbors
of x belong to pentagons of G, G does not have a perfect star packing of type P0. Hence if
a fullerene graph has a perfect star packing of type P0, then all its pentagons are isolated.
Next we list some other forbidden subgraphs for guaranteeing a fullerene graph to own a
perfect star packing of type P0.
1PP 3PP 4PP
1
v1v 2v2v 1
v
2
v
1
x
2
x
3
x
Figure 7: Three forbidden configurations.
Proposition 4.7. If a fullerene graph G contains a subgraph PP1, PP3 or PP4 (see
Figure 7), then it cannot have a perfect star packing of type P0.
Proof. By the contrary, we suppose that G has a perfect star packing of type P0, denoted
by S. Clearly, the vertices v1 and v2 (see Figure 7) are leaves in S. If PP4 is a subgraph
of G, then x1 is the center of a star in S since all vertices on a pentagon are leaves in S. So
x2 is a leaf in S. By Remark 2.4(2), the neighbor x3 of x2 is also a leaf in S. This implies
that all the three neighbors of v2 are leaves in S, a contradiction. For subgraphs PP1 and
PP3, we can similarly show that v1 or v2 have all its three neighbors being leaves in S, a
contradiction.
ORCID iDs
Lingjuan Shi https://orcid.org/0000-0001-9440-4660
References
[1] M. B. Ahmadi, E. Farhadi and V. A. Khorasani, On computing the Clar number
of a fullerene using optimization techniques, MATCH Commun. Math. Comput. Chem.
75 (2016), 695–701, https://match.pmf.kg.ac.rs/electronic_versions/
Match75/n3/match75n3_695-701.pdf.
[2] A. Al Mutairi, B. Ali and P. Manuel, Packing in carbon nanotubes, J. Comb. Math. Comb.
Comput. 92 (2015), 195–206.
[3] J. Alber, M. R. Fellows and R. Niedermeier, Polynomial-time data reduction for dominating set,
J. ACM 51 (2004), 363–384, doi:10.1145/990308.990309, https://doi.org/10.1145/
990308.990309.
[4] S. J. Austin, P. W. Fowler, P. Hansen, D. E. Manolopoulos and M. Zheng, Fullerene isomers
of C60: Kekulé counts versus stability, Chem. Phys. Lett. 228 (1994), 478–484, doi:10.1016/
0009-2614(94)00965-1, https://doi.org/10.1016/0009-2614(94)00965-1.
L. Shi: The fullerene graphs with a perfect star packing 15
[5] R. Bar-Yehuda, M. M. Halldórsson, J. Naor, H. Shachnai and I. Shapira, Scheduling split
intervals, SIAM J. Comput. 36 (2006), 1–15, doi:10.1137/s0097539703437843, https:
//doi.org/10.1137/s0097539703437843.
[6] R. Bejar, B. Krishnamachari, C. Gomes and B. Selman, Distributed constraint satisfaction in a
wireless sensor tracking system, in: Workshop on Distributed Constraint Reasoning, Interna-
tional Joint Conference on Artiffcial Intelligence, 2001 .
[7] N. Biggs, Perfect codes in graphs, J. Comb. Theory Ser. B 15 (1973), 289–296, doi:10.1016/
0095-8956(73)90042-7, https://doi.org/10.1016/0095-8956(73)90042-7.
[8] J. A. Carr, X. Wang and D. Ye, Packing resonant hexagons in fullerenes, Discrete Optim.
13 (2014), 49–54, doi:10.1016/j.disopt.2014.05.002, https://doi.org/10.1016/j.
disopt.2014.05.002.
[9] I. J. Dejter, Worst-case efficient dominating sets in digraphs, Discrete Appl. Math.
161 (2013), 944–952, doi:10.1016/j.dam.2012.11.016, https://doi.org/10.1016/j.
dam.2012.11.016.
[10] I. J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129
(2003), 319–328, doi:10.1016/s0166-218x(02)00573-5, https://doi.org/10.1016/
s0166-218x(02)00573-5.
[11] Y.-P. Deng, Y.-Q. Sun, Q. Liu and H.-C. Wang, Efficient dominating sets in circulant graphs,
Discrete Math. 340 (2017), 1503–1507, doi:10.1016/j.disc.2017.02.014, https://doi.
org/10.1016/j.disc.2017.02.014.
[12] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer-Verlag,
Berlin, 3rd edition, 2005.
[13] T. Došlić, On lower bounds of number of perfect matchings in fullerene graphs, J. Math. Chem.
24 (1998), 359–364, doi:10.1023/a:1019195324778, https://doi.org/10.1023/a:
1019195324778.
[14] T. Došlić, M. Taheri-Dehkordi and G. H. Fath-Tabar, Packing stars in fullerenes, J. Math.
Chem. 58 (2020), 2223–2244, doi:10.1007/s10910-020-01177-4, https://doi.org/10.
1007/s10910-020-01177-4.
[15] A. Felzenbaum, R. Holzman and D. J. Kleitman, Packing lines in a hypercube, Discrete
Math. 117 (1993), 107–112, doi:10.1016/0012-365x(93)90327-p, https://doi.org/10.
1016/0012-365x(93)90327-p.
[16] P. Fowler and D. Manolopoulos, An Atlas of Fullerenes, Dover books on chemistry, Dover
Publications, 2006.
[17] Y. Gao, Q. Li and H. Zhang, Fullerenes with the maximum Clar number, Discrete Appl. Math.
202 (2016), 58–69, doi:10.1016/j.dam.2015.08.007, https://doi.org/10.1016/j.
dam.2015.08.007.
[18] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathe-
matics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9, https://doi.
org/10.1007/978-1-4613-0163-9.
[19] B. Grünbaum and T. S. Motzkin, The number of hexagons and the simplicity of geodesics on
certain polyhedra, Can. J. Math. 15 (1963), 744–751, doi:10.4153/cjm-1963-071-3, https:
//doi.org/10.4153/cjm-1963-071-3.
[20] I. Gutman, J. W. Kennedy and L. V. Quintas, Perfect matchings in random hexagonal chain
graphs, J. Math. Chem. 6 (1991), 377–383, doi:10.1007/bf01192592, https://doi.org/
10.1007/bf01192592.
16 Ars Math. Contemp. 23 (2023) #P1.05
[21] E. Hartung, Fullerenes with complete Clar structure, Discrete Appl. Math. 161 (2013), 2952–
2957, doi:10.1016/j.dam.2013.06.009, https://doi.org/10.1016/j.dam.2013.
06.009.
[22] J. Huang and J.-M. Xu, The bondage numbers and efficient dominations of vertex-transitive
graphs, Discrete Math. 308 (2008), 571–582, doi:10.1016/j.disc.2007.03.027, https://
doi.org/10.1016/j.disc.2007.03.027.
[23] D. Kirkpatrick and P. Hell, On the complexity of a generalized matching problem, in: Proceed-
ings of the Tenth Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 1978 pp. 309–314.
[24] D. J. Klein and X. Liu, Theorems for carbon cages, J. Math. Chem. 11 (1992), 199–205, doi:
10.1007/bf01164204, https://doi.org/10.1007/bf01164204.
[25] J. Kratochvı́l, Perfect codes over graphs, J. Comb. Theory Ser. B 40 (1986), 224–228,
doi:10.1016/0095-8956(86)90079-1, https://doi.org/10.1016/0095-8956(86)
90079-1.
[26] H. Li and H. Zhang, The isolated-pentagon rule and nice substructures in fullerenes, Ars
Math. Contemp. 15 (2018), 487–497, doi:10.26493/1855-3974.1359.b33, https://doi.
org/10.26493/1855-3974.1359.b33.
[27] M. Livingston and Q. F. Stout, Perfect dominating sets, in: Proceedings of the Twenty-first
Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL,
1990), volume 79, 1990 pp. 187–203.
[28] A. Muthumalai, I. Rajasingh and A. S. Shanthi, Packing of hexagonal networks, J. Comb. Math.
Comb. Comput. 79 (2011), 121–127.
[29] I. Rajasingh, A. Muthumalai, R. Bharati and A. S. Shanthi, Packing in honeycomb networks,
J. Math. Chem. 50 (2012), 1200–1209, doi:10.1007/s10910-011-9962-9, https://doi.
org/10.1007/s10910-011-9962-9.
[30] H. Siddiqui and M. Imran, Computation of metric dimension and partition dimension of nan-
otubes, J. Comput. Theor. Nanosci. 12 (2015), 199–203, doi:10.1166/jctn.2015.3717, https:
//doi.org/10.1166/jctn.2015.3717.
[31] Q. Yang, H. Zhang and Y. Lin, On the anti-forcing number of fullerene graphs, MATCH
Commun. Math. Comput. Chem. 74 (2015), 673–692, https://match.pmf.kg.ac.rs/
electronic_versions/Match74/n3/match74n3_673-692.pdf.
[32] H. Zhang and D. Ye, An upper bound for the Clar number of fullerene graphs, J. Math.
Chem. 41 (2007), 123–133, doi:10.1007/s10910-006-9061-5, https://doi.org/10.
1007/s10910-006-9061-5.
[33] H. Zhang and F. Zhang, New lower bound on the number of perfect matchings in fullerene
graphs, J. Math. Chem. 30 (2001), 343–347, doi:10.1023/a:1015131912706, https://doi.
org/10.1023/a:1015131912706.