ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 337-350
Saturation number of nanotubes
Niko Tratnik
Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, Maribor, Slovenia
Petra Žigert Pleteršek
Faculty of Chemistry and Chemical Engineering, University of Maribor, Smetanova ulica 17, Maribor, Slovenia Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, Maribor, Slovenia
Received 8 March 2016, accepted 23 June 2016, published online 30 January 2017
In the present paper we are interested in the saturation number of closed benzenoid chains and certain families of nanotubes. The saturation number of a graph is the cardinality of a smallest maximal matching in the graph. The problem of determining the saturation number is related to the edge dominating sets and efficient edge dominating sets in a graph. We establish the saturation number of some closed benzenoid chains and C4C6-tubes. Further, upper and lower bounds for the saturation number of armchair, zig-zag, TUC4C8(S) and TUC4C8(R) nanotubes are calculated.
Keywords: Saturation number, maximal matching, edge domination number, efficient edge dominating set, closed benzenoid chain, armchair nanotube, zig-zag nanotube, tubulene, TUC4C8(S) nan-otube, TUC4C8(R) nanotube.
Math. Subj. Class.: 92E10, 05C70, 05C69
1 Introduction
The saturation number s(G) of a graph G is the cardinality of a smallest maximal matching in G. Maximal matchings serve as models of adsorption of dimers (those that occupy two adjacent atoms) to a molecule. It can occur that the double bonds in a molecule are not efficiently saturated by dimers, and therefore, their number is below the theoretical maximum. Hence, the saturation number provides an information on the worst possible
E-mail addresses: niko.tratnik@gmail.com (Niko Tratnik), petra.zigert@um.si (Petra Zigert Pletersek)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
338
Ars Math. Contemp. 12 (2017) 383-413
case of adsorption. Besides in chemistry the saturation number has a list of interesting applications in engineering and networks.
A lot of work has been done on enumeration problems of different matchings in some chemical graphs, for example see [4, 5], but not much has been done on the smallest maximal matchings. Previous work on the saturation number includes research on benzenoid systems [8] and fullerenes [6, 1,2]. Recent results on related concepts can be found in [3,7].
The saturation number is closely related to the edge dominating sets. Actually, for any graph, the saturation number equals the edge domination number. The problem of determining the saturation number of a graph is NP-complete [13].
In this paper we show how to use an efficient edge dominating set in a graph to determine its saturation number. Also, the saturation number is established for certain closed benzenoid chains. Further, some bounds for the saturation number of different families of nanotubes are calculated.
2 Preliminaries
A matching M in a graph G is a set of edges of G such that no two edges from M share a vertex. A matching M is a maximum matching if there is no matching in G with greater cardinality. The cardinality of any maximum matching in G is denoted by v (G) and called the matching number of G. If every vertex of G is incident with an edge of M, the matching M is called a perfect matching (in chemistry perfect matchings are known as Kekule structures).
A matching M in a graph G is maximal if it cannot be extended to a larger matching in G. Obviously, every maximum matching is also maximal, but the opposite is generally not true. A matching M is a smallest maximal matching if there is no maximal matching in G with smaller cardinality. The cardinality of any smallest maximal matching in G is the
saturation number of G.
The following lemma is very useful for proving lower bounds for the saturation number. The proof can be found online, but for the sake of completeness we provide it.
Lemma 2.1. Let G be a graph and let A and B be maximal matchings in G. Then | A| > ^ and |B| > ^.
Proof. First note that each edge in B \ A can be adjacent to at most two edges in A \ B since A is a matching. Moreover, each edge in A \ B is adjacent to an edge in B \ A by maximality of B. Therefore,
|A \ B|< 2|B \ A|.
Hence, we obtain
|A| = |A n B| + |A \ B| < 2|B n A| + 2|B \ A| = 2|B|. The other inequality can be proven analogously.	□
An independent set is a set of vertices in a graph G, no two of which are adjacent. A maximum independent set is an independent set of largest possible cardinality for a given graph G. This cardinality is called the independence number of G, and denoted a(G). It is obvious that if M is a maximal matching and A is the set of endpoints of edges in
N. Tratnik and P. Zigert Pletersek: Saturation number ofnanotubes
339
M, then the set of vertices in V(G) - A is an independent set of vertices in G. Therefore, a(G) > |V (G)|-2s(G). Hence, we obtain another lower bound for the saturation number:
s(G) > |V(G)|; a(G).
Another graph invariant closely related to the saturation number is the edge domination number. An edge dominating set for a graph G is a subset D C E(G) such that every edge not in D is incident to at least one edge in D. An independent edge dominating set is an edge dominating set in which no two elements are adjacent. An independent edge dominating set is in fact a maximal matching and a smallest independent edge dominating set is a smallest maximal matching, i.e. the cardinality of a smallest independent edge dominating set is the saturation number. The edge domination number of a graph G, 7' (G), is the smallest cardinality taken over all edge dominating sets of G. If M is a smallest maximal matching of G, then M is also an edge dominating set, therefore y'(G) < s(G). For the contrary, if D is a smallest edge dominating set with k elements, we can construct a maximal matching of cardinality k (for the details see [13]). Therefore, s(G) < 7'(G). Hence, for every graph G it holds
s(G) = 7 '(G).	(2.1)
Figure 1: Illustration of a (4, -3)-type tubulene.
Since the paper focuses on nanotubes, we will formally define open-ended carbon nan-otubes, also called tubulenes (see [11]). Choose any lattice point in the hexagonal lattice as the origin O. Let at and 02 be the two basic lattice vectors. Choose a vector OA = not + ma2 such that n and m are two integers and |n| + |m| > 1, nm = -1. Draw two straight lines Lt and L2 passing through O and A perpendicular to OA, respectively. By rolling up the hexagonal strip between Lt and L2 and gluing Lt and L2 such that A and O superimpose, we can obtain a hexagonal tessellation HT of the cylinder. Lt and L2 indicate the direction of the axis of the cylinder. Using the terminology of graph theory, a tubulene T is defined to be the finite graph induced by all the hexagons of HT that lie between ct and c2, where ct and c2 are two vertex-disjoint cycles of HT encircling the
340
Ars Math. Contemp. 12 (2017) 383-413
axis of the cylinder. The vector OA is called the chiral vector of T and the cycles c1 and c2 are the two open-ends of T.
For any tubulene T, if its chiral vector is not + ma2, T will be called an (n, m)-type tubulene (see Figure 1). A tubulene T is called zig-zag if n = 0 or m = 0 and armchair if
n = m.
3 Graphs with an efficient edge dominating set
One other concept is also very useful in studying the saturation number. A matching D of a graph G is called an efficient edge dominating set if for each edge e G E(G) \ D there is exactly one edge f in D such that e and f are incident (this concept is equivalent to the efficient dominating set in the line graph of G, for the details see [10]). Using the following theorem we can exactly determine the saturation number for some graphs.
Theorem 3.1. If a graph G has an efficient edge dominating set D, then
s(G) = |D|.
Proof. It follows from Equation 2.1 that s(G) = y'(G). Hence it is enough to show that Y'(G) = |D| (see [9]).
Obviously, if D is an efficient edge dominating set then D is also an edge dominating set. Therefore, y'(G) < |D|. Conversely, let P be a smallest edge dominating set and let e G D. It follows that either e G P or there is an edge f G P such that e and f are incident. Therefore, for an edge e G D there always exists fe G P such that e = fe or e and fe are incident. It is also clear that since D is an efficient edge dominating set, for given edges e and e' in D, e = e', it follows that fe = fe. Hence, |D| < |P| = y'(G). The proof is complete.	□
Example 3.2. One infinite family of graphs with an efficient edge dominating set are C4C6-tubes, which are constructed of cycles C4 and C6 - see Figure 2. Let T(p, q) be a C4 C6-tube with p layers of hexagons and with q hexagons in every layer. The set of double edges in Figure 2 is obviously an efficient edge dominating set of cardinality pq = 15. Therefore, by Theorem 3.1, the saturation number of T(p, q) is s(T(p, q)) = pq.
Figure 2: A C4C6-tube T(3,5). Edges e^ e2 and e3 are joined with edges e'x, e'2 and e^, respectively.
For example, polyacenes and closed polyacenes are also such graphs (see Section 4). However, not many graphs posses an efficient edge dominating set.
N. Tratnik and P. Zigert Pletersek: Saturation number ofnanotubes
341
4 Closed benzenoid chains
Recall that benzenoid graphs are 2-connected subgraphs of the hexagonal lattice such that every bounded face is a hexagon. The vertices lying on the border of the non-hexagonal face of a benzenoid graph are called external; other vertices, if any, are called internal. A benzenoid graph without internal vertices is called catacondensed. If no hexagon in a catacondensed benzenoid is adjacent to three other hexagons, we say that the benzenoid is a chain. In each benzenoid chain there are exactly two hexagons adjacent to one other hexagon; those two hexagons are called terminal, while any other hexagons are called interior. An interior hexagon is called straight if the two edges it shares with other hexagons are parallel, i.e., opposite to each other. If the shared edges are not parallel, the hexagon is called kinky. If all interior hexagons of a benzenoid chain are straight, we call the chain a polyacene.
Let B be a benzenoid chain with terminal hexagons h and h'. Let e = uv and e' = w'v' be edges of h and h', respectively, such that vertices w, v, w', v' have degree 2 in B. Furthermore, suppose that there exist a path from w to w' in the perimeter of B, which does not contain neither v nor v'. A graph obtained by identifying edges e and e' is called a closed benzenoid chain. For example see Figure 3.
Figure 3: A closed benzenoid chain. Edges e and e' are joined together.
Similar as before, a hexagon of a closed benzenoid chain is called straight if the two edges it shares with other hexagons are opposite to each other. If the shared edges are not parallel, the hexagon is called kinky.
Remark 4.1. Note that not every closed benzenoid chain is a tubulene in the sense of the definition in the preliminaries. In fact, if we consider benzenoid chain embedded in the hexagonal lattice, it is not difficult to see that a closed benzenoid chain is a tubulene if and only if the distance from u to u' in the hexagonal lattice is an even number and the edge e is parallel to e'.
In this section we compute the saturation number of some closed benzenoid chains. The following lemma claims that every closed benzenoid chain has a perfect matching.
Lemma 4.2. Let B be a closed benzenoid chain. Then B has a perfect matching.
Proof. Let G be a benzenoid chain from which B is obtained by identifying edges e and e'. Since every internal hexagon in G has exactly 4 edges on the perimeter and both terminal hexagons have 5 edges on the perimeter, there is always an even number of edges on the perimeter of G. Therefore, let M be a perfect matching of the perimeter of G such that e € M. Obviously, M is a perfect matching of G. Now we consider two cases:
342
Ars Math. Contemp. 12 (2017) 383-413
1.	If e' G M, then after identifying e and e' into the new edge f, the set (M \ {e, e'}) U {f} is a perfect matching of B.
2.	If e' G M, then after identifying e and e', the set M \ {e} is a perfect matching of B.
Hence, we have seen that B has a perfect matching.	□
In the next proposition we prove a lower bound for the saturation number of closed ben-zenoid chains.
Proposition 4.3. Let B be a closed benzenoid chain with h hexagons. Then s(B) > h.
Proof. Let M be a perfect matching of B. Since there is 4h vertices in B and every edge in M covers exactly 2 vertices, perfect matching M contains 2h edges. Therefore, by Lemma 2.1, any maximal matching contains at least half of the number of edges in M. Hence,
s(B) > = h.	□
A closed benzenoid chain B is called a closedpolyacene (or a hexagonal belt) if it does not contain kinky hexagons (see Figure 4).
Figure 4: A maximal matching of a closed polyacene with 5 hexagons.
Proposition 4.4. Let B be a closed polyacene with h hexagons. Then s(B) = h.
Proof. Obviously, the set of vertical edges of B (see the edges in matching M from Figure 4) is an efficient edge dominating set and |M| = h. Therefore, by Theorem 3.1 it follows
s(B) = h.	□
The following theorem completely characterizes closed polyacenes among closed ben-zenoid chains according to saturation number.
Theorem 4.5. Let B be a closed benzenoid chain with h hexagons. Then s(B) = h if and only if B is a closed polyacene.
Proof. Let B be a closed polyacene with h hexagons. It follows from Proposition 4.4 that
s(B) = h.
For the converse suppose that B is a closed benzenoid chain with h hexagons and s(B) = h. Let M be a maximal matching with h edges. Those edges cover exactly 2h vertices. Let A be the set of vertices that are not covered by edges in M. Since B has 4h vertices, there are 2h vertices in A. Since M is a maximal matching, no two vertices in A are adjacent. Let A' be the set of edges that are incident to vertices in A. Since the degree of every vertex in B is at least 2, it follows |A' | > 4h. But A' C E(B) \ M and therefore, |A'| < 5h — h = 4h. Hence, every vertex in A has degree 2 and every hexagon contains exactly two elements of A. Therefore, every hexagon of B has 2 non-adjacent vertices of degree 2. It follows that B is a closed polyacene.	□
N. Tratnik and P. Zigert Pletersek: Saturation number ofnanotubes
343
In the next theorem we compute the saturation number of closed benzenoid chains with exactly one kinky hexagon. However, such closed benzenoid chain is never a tubulene since the distance between u and u' is odd.
Theorem 4.6. Let B be a closed benzenoid chain with h hexagons such that exactly one of them is a kinky hexagon. Then s(B) = h + 1.
Proof. Let M be the set of edges in B that lie on exactly two hexagons. Moreover, let one other edge of the kinky hexagon be in M. Then it is easy to see that M is a maximal matching and therefore, s(B) < h + 1.
Since B is not a closed polyacene, s(B) > h + 1 and the proof is complete.	□
Proposition 4.7. Let B be a closed benzenoid chain with exactly two kinky hexagons which are consecutive. Then s(B) = h +1.
Proof. Let M be a maximal matching with h+1 edges from Figure 5. Hence, s(B) < h+1.
Figure 5: A closed benzenoid chain with two consecutive kinky hexagons and its maximal matching.
Since B is not a closed polyacene, s(B) > h + 1 and the proof is complete.	□
5 Zig-zag tubulenes
Figure 6: Zig-zag tubulene ZT(3,4).
Let T be a zig-zag tubulene such that c1, c2 are the shortest possible cycles encircling the axis of the cylinder (see Figure 6). If T has n layers of hexagons, each containing
344
Ars Math. Contemp. 12 (2017) 383-413
exactly h hexagons, then we denote it by ZT(n, h). Note that ZT(n, h) is a (0, h) or (h, 0)-type tubulene. First we show an upper bound for the saturation number of ZT(n, h), which is essentially of order .
Theorem 5.1. Let ZT(n, h) be a zig-zag tubulene. Then
, 3 | n
s(ZT(n, h)) < { M2"^, 3 | n - 1
3
h( 2w+2) 3
3 1 n- 2.
Proof. Let ZT(n, h) be drawn in a plane such that some edges are vertical and such that cycles c1 and c2 lie on the bottom and on the top. To show an upper bound, we construct a maximal matching of ZT(n, h). This maximal matching is obtained by alternating two different layers of edges - vertical and non-vertical. We start with vertical edges in the first layer (at the bottom of a tubulene) and we need 2 layers of edges for every 3 layers of hexagons. Obviously we have exactly h edges in every layer. Now consider three different cases.
Figure 7: A maximal matching of zig-zag tubulenes. Lines L1 and L2 are joined together.
1.	If 3 | n: then we need 2" layers of edges and one additional layer at the top of a tubulene. Hence, we obtain ^^^^ edges in M. See Figure 7(a).
2.	If 3 | n - 1: in this case we need 2("-1) layers of edges and we have to add one vertical layer. Hence, |M| = fe(2"+1). See Figure 7(b).
N. Tratnik and P. Zigert Pletersek: Saturation number ofnanotubes
345
3. If 3 | n - 2: in this case we have 2("3 2) layers of edges and we have to add 2 additional layers (one vertical and one non-vertical) to obtain a maximal matching. Hence, |M| = h(2"+2). See Figure 7(c).
It is obvious that in such a way we always obtain a maximal matching. Therefore, the proof is complete.	□
In the next lemma we prove a lower bound.
Lemma 5.2. Let ZT(n, h) be a zig-zag tubulene. Then
(n + 1)h
s(ZT(n, h)) >
2
Proof. Obviously ZT(n, h) has a perfect matching with (n + 1)h edges. Therefore, by Lemma 2.1, any maximal matching contains at least ("+1)h edges.	□
Theorem 5.1 and Lemma 5.2 together imply the following corollary.
Corollary 5.3. Let ZT(n, h) be a zig-zag tubulene. Then
{h(2"+3), 3 | n
^^ 3 1 n - 1 , 3 | n - 2.
6 Armchair tubulenes
Let T be an armchair tubulene such that c1 and c2 are the shortest possible cycles encircling the axis of the cylinder and such that there is the same number of hexagons in every column of hexagons (see Figure 8). If T has n vertical layers of hexagons, each containing exactly p hexagons, then we denote it by AT(n,p). Obviously, n must be an even number. Note that AT(n, p) is a (", " )-type tubulene. In the following theorem we prove an upper bound for the saturation number of AT(n, p).
Theorem 6.1. Let AT(n,p) be an armchair tubulene. Then
^ni^ti), 3 | n s(AT(n,p)) <4 (2"+1j(p+1), 3 | n - 1 2("+2)(p+1) , 3 | n - 2.
Proof. Let AT(n, p) be drawn in a plane such that some edges are horizontal and such that cycles c1 and c2 lie on the bottom and on the top. To show an upper bound, we construct a maximal matching of AT(n,p). This maximal matching is obtained by alternating two different columns of edges - horizontal and non-horizontal. We start with horizontal edges in the first column (at the left side of a tubulene) and we need 2 columns of edges for every 3 columns of hexagons. Obviously we have exactly p + 1 edges in every column. Now consider three different cases.
1. If 3 | n: then we need 2" columns of edges to obtain a maximal matching. Hence, we obtain 2"(P+1) edges in M. See Figure 8.
346
Ars Math. Contemp. 12 (2017) 383-413
Figure 8: A maximal matching of armchair tubulene AT(6,4). Curves L1 and L2 are joined together.
2.	If 3 | n - 1: in this case we need 2("3-1) columns of edges and we have to add one horizontal column. Hence, |M| = (2"+1j(p+1).
3.	If 3 | n - 2: in this case we have 2("3-2) columns of edges and we have to add 2 additional horizontal layers of edges to obtain a maximal matching. Hence, |M | =
2("+2.)(p+1) .See Figure 9.
Figure 9: A maximal matching of armchair tubulene AT(8,4). Curves L1 and L2 are joined together.
It is obvious that in such a way we always obtain a maximal matching. Therefore, the proof is complete.	□
In the next lemma we prove a lower bound.
Lemma 6.2. Let AT(n,p) be an armchair tubulene. Then
n(p + 1)
s(AT(n,p)) >
2
Proof. Obviously AT(n,p) has a perfect matching with n(p + 1) edges (we can put all horizontal edges in a perfect matching). Therefore, by Lemma 2.1, any maximal matching contains at least "(p2+1) edges.	□
N. Tratnik and P. Zigert Pletersek: Saturation number ofnanotubes
347
Theorem 6.1 and Lemma 6.2 together imply the following corollary.
Corollary 6.3. Let AT(n, h) be an armchair tubulene. Then
2n(p+l) ,	3 | n
n(p +1) < s(AT(n,p)) <J (2"+1j(p+1), 3 1 n - 1
2 —	v>f)) — \	3
2	1 2(n+2)(p+1)
3	'
3 1 n- 2.
7 TUC4C8(S) nanotubes
A C4C8 net is a trivalent pattern made by alternating squares C4 and octagons C8. Identifying some edges in such a lattice we obtain a TUC4C8(S) nanotube (see Figure 10). Such nanotubes could appear by successive low energy Stone-Wales edge flipping [12] in polyhex nanotubes. In this section we prove an upper and a lower bound for the saturation number of TUC4C8(S) nanotubes. We denote nanotube with q layers and p squares (or octagons) in every layer with TS(p, q).
Figure 10: TS(4,4) with a maximal matching.
Theorem 7.1. Let TS(p, q) be a TUC4C8(S) nanotube. Then
[	3 | p
s(TS(p, q)) < { ^^, 3 | p - 1 [ (ip+i)l, 3 | p - 2.
Proof. To prove the theorem we construct a maximal matching for nanotube TS(p, q). In every layer we put every third edge in the matching M. In layer with k = 1 we put the first edge in M and in layer with k = 2 we start with the second edge (see Figure 10). Next, in the third layer, we repeat the first layer. Now consider the following cases:
1.	If 3 | p, then we have 4|q edges in M.
2.	If 3 | p - 1: in this case we have 4(p^1)g edges and we have to add 2 additional edges in every layer to obtain a maximal matching. Hence, |M | = 4(p^1)g +2q = (4p+2)q.
3.	If 3 | p - 2: in this case we have 4(p^2)g edges and we have to add 3 additional edges in every layer to obtain a maximal matching. Hence, |M | = 4(p^2)g +3q = (4p+1)q.
348
Ars Math. Contemp. 12 (2017) 383-413
In the next proposition we prove a lower bound.
Lemma 7.2. Let TS(p, q) be a TUC4C8(S) nanotube. Then s(TS(p, q)) > pq.
Proof. First notice that TS(p, q) always has a perfect matching. For example, we can take every second edge in every layer. Since the number of vertices in TS(p, q) is 4pq, a perfect matching of TS(p, q) contains 2pq edges, since every edge covers two vertices. Now it follows from Lemma 2.1 that every maximal matching contains at least pq edges. Hence,
s(TS(p, q)) > pq.	□
Theorem 7.1 and Lemma 7.2 together imply the next corollary.
Corollary 7.3. Let TS(p, q) be a TUC4C8 nanotube. Then
[	31 p
pq < s(TS(p,q)) < {	, 3 | p - 1
[ (ip+ik, 3 | p - 2.
8 TUC4C8(R) nanotubes
Again we begin with a C4C8 net, but this time squares are not in the horizontal position. Identifying some edges in such a lattice we obtain a TUC4C8(R) nanotube (see Figure 11). In this section we prove an upper and a lower bound for the saturation number of TUC4C8(R) nanotubes. We denote a nanotube with p octagons in every layer and q octagons in every column with TR(p, q).
Figure 11: TR(4, 3) with a maximal matching. Left and right side are joined.
Theorem 8.1. Let TR(p, q) be a TUC4C8 (R) nanotube. Then
i 4f + p,	3 | q
s(TR(p,q)) < { fc^ +3p, 3 | q - 1 1 ^ +4p, 3 | q - 2.
N. Tratnik and P. Zigert Pletersek: Saturation number ofnanotubes
349
Proof. We construct a maximal matching M for nanotube TR(p, q). For every 3 rows of octagons we put 4 layers of edges in the matching M. Of course, every layer contains exactly p edges. See Figure 11.
Now consider the following cases:
1.	If 3 | q: in this case we have edges in M and we need one additional layer of horizontal edges at the top - see Figure 11.
2.	If 3 | q -1: in this case we have 4(q-1)p edges and we have to add 3 additional layers of edges to obtain a maximal matching. Hence, |M| = 4(q^1)p + 3p.
3.	If 3 | q - 2: in this case we have 4(q^2)p edges and we have to add 4 additional layers of edges to obtain a maximal matching. Hence, |M| = 4(q^2)p + 4p.
In the next lemma we prove a lower bound.
Lemma 8.2. Let TR(p, q) be a TUC4C8R nanotube. Then s(TR(p, q)) > p(q + 1).
Proof. First notice that TR(p, q) always has a perfect matching. Since the number of vertices in TR(p, q) is 4p(q +1), a perfect matching of TR(p, q) contains 2p(q +1) edges, since every edge covers two vertices. Now it follows from Lemma 2.1 that every maximal matching contains at least p(q + 1) edges. Hence, s(TR(p, q)) > p(q + 1).	□
Theorem 8.1 and Lemma 8.2 together imply the next corollary.
Corollary 8.3. Let TR(p, q) be a TUC4C8(R) nanotube. Then
Concluding remarks
In the paper we have established some bounds for the saturation number of certain families of nanotubes. However, the exact values are unknown. There are still many open problems regarding the saturation number of molecular graphs, for example coronenes, coronoids, polyomino chains, etc.
Acknowledgment
Supported in part by the Ministry of Science of Slovenia under grant P1 - 0297. References
[1]	V. Andova, T. Doslic, M. Krnc, B. Luzar and R. Skrekovski, On the diameter and some related invariants of fullerene graphs, MATCH Commun. Math. Comput. Chem. 68 (2012), 109-130.
[2]	V. Andova, F. Kardos and R. Skrekovski, Sandwiching saturation number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 73 (2015), 501-518.
[3]	A. Behmaram, T. Doslic and S. Friedland, Matchings in m-generalized fullerene graphs, Ars Math. Contemp. 11 (2016), 301-313.
□
350
Ars Math. Contemp. 12 (2017) 383-413
[4]	S. J. Cyvin and I. Gutman, Kekule Structures in Benzenoid Hydrocarbons, Springer, Berlin, 1988.
[5]	T. Doslic, Fullerene graphs with exponentially many perfect matchings, J. Math. Chem. 41 (2007), 183-192.
[6]	T. Doslic, Saturation number of fullerene graphs, J. Math. Chem. 43 (2008), 647-657.
[7]	T. Doslic and I. Zubac, Counting maximal matchings in linear polymers, Ars Math. Contemp. 11 (2016), 255-276.
[8]	T. Doslic and I. Zubac, Saturation number of benzenoid graphs, MATCH Commun. Math. Com-put. Chem. 73 (2015), 491-500.
[9]	J. P. Georges, M. D. Halsey, A. M. Sanaulla and M. A. Whittlesey, Edge domination and graph structure, Congr. Numer. 76 (1990), 127-144.
[10]	D. L. Grinstead, P. J. Slater, N. A. Sherwani and N. D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (1993), 221-228.
[11]	H. Sachs, P. Hansen and M. Zheng, Kekule count in tubular hydrocarbons, MATCH Commun. Math. Comput. Chem. 33 (1996), 169-241.
[12]	A. J. Stone and D. J. Wales, Theoretical studies of icosahedral C60 and some related species, Chem. Phys. Lett. 128 (1986), 501-506.
[13]	M. Yannakakis and F. Gavril, Edge dominating sets in graphs, Siam J. Appl. Math. 38 (1980), 364-372.