ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 191-204
https://doi.org/10.26493/1855-3974.1279.bce
(Also available at http://amc-journal.eu)
Saturation number of lattice animals
Tomislav Doslic *
Faculty of Civil Engineering, University of Zagreb, Kaciceva 26, Zagreb, Croatia
4=
Niko Tratnik t
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 and Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, Maribor, Slovenia
Received 7 January 2017, accepted 24 October 2017, published online 19 June 2018
A matching M in a graph G is maximal if no other matching of G has M as a proper subset. The saturation number of G is the cardinality of any smallest maximal matching in G. In this paper we investigate saturation number for several classes of square and hexagonal lattice animals.
Keywords: Maximal matching, saturation number, lattice animal, polyomino graph, benzenoid graph, coronene.
Math. Subj. Class.: 92E10, 05C70, 05C35, 05C90
*	Partially supported by the Croatian Science Foundation via research projects BioAmpMode (Grant no. 8481) and LightMol (Grant no. IP-2016-06-1142) and by Croatian Ministry of Science, Education and Sports (Croatian-Slovenian bilateral project "Modeling adsorption on nanostructures: Graph-theoretic approach").
t Supported by the Slovenian Research Agency.
*	Supported in part by the Slovenian Research Agency under grant P1-0297.
E-mail addresses: doslic@grad.unizg.hr (Tomislav Doslic), niko.tratnik@um.si (Niko Tratnik), petra.zigert@um.si (Petra Zigert Pletersek)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/3.0/
192
Ars Math. Contemp. 15 (2018) 147-160
1 Introduction
A lattice animal is any bounded subset of a regular lattice in the plane whose boundary is made of simple closed curve following lattice edges. In this paper we study the saturation number of hexagonal and square lattice animals.
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 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 case of adsorption. Besides in chemistry the saturation number has a number of interesting applications in engineering and networks. The problem of determining the saturation number is equivalent to the problem of finding the edge domination number in a graph. Moreover, if a graph G has an efficient edge dominating set D, it holds s(G) = |D| (see [7]). Previous work on the saturation number includes research on random graphs [8, 9], on benzenoid systems [5], fullerenes [1, 2, 4], and nanotubes [7]. Recent results on related concepts can be found in [3, 6].
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, denoted by s(G).
The following lemma is very useful for proving lower bounds for the saturation number. The proof can be found in [7]. See also [8, 9].
Lemma 2.1. Let G be a graph and let A and B be maximal matchings in G. Then | A| > ^ and |B| > ^.
This result implies the lower bound s(G) > ^^. In particular, in graphs with perfect matchings the saturation number cannot be smaller than one quarter of the number of vertices, s(G) > n.
A polyomino system consists of a cycle C in the infinite square lattice together with all squares inside C. A polyomino graph is the underlying graph of a polyomino system.
A benzenoid system consists of a cycle C in the regular infinite hexagonal lattice together with all hexagons inside C. A benzenoid graph is the underlying graph of a benzenoid system.
Let G be a benzenoid graph or a polyomino graph. The vertices lying on the outer face of G are called external; other vertices, if any, are called internal. Graph G without internal vertices is called catacondensed. If no inner face in a catacondensed graph G is adjacent to more than two other inner faces, we say that graph G is unbranched or that it is a chain.
T. Doslic et al.: Saturation number of lattice animals
193
In each chain G there are exactly two inner faces adjacent to one other inner face; those two inner faces are called terminal, while any other inner faces are called interior. The number of inner faces in chain G is called its length. An interior inner face is called straight if the two edges it shares with other inner faces are parallel, i.e. opposite to each other. If the shared edges are not parallel, the inner face is called kinky. If all interior inner faces of a chain G are straight, the chain is called linear.
There is also another terminology, calling straight inner faces linear, and kinky inner faces angular. By introducing abbreviations L and A, respectively, for linear and angular inner faces, each chain can be represented as a word over the alphabet {L, A}, with the restriction that the first and the last letter are always L. Such a word is called the LA-sequence of the chain.
A fullerene F is a 3-connected 3-regular plane graph such that every face is bounded by either a pentagon or a hexagon. By Euler's formula, it follows that the number of pentagonal faces of a fullerene is exactly 12.
The Cartesian product G □ H of graphs G and H is the graph with the vertex set V(G) x V(H) and (a, x)(b, y) e E(G □ H) whenever ab e E(G) and x = y, or, if a = b and xy e E(H).
3 Polyomino chains and grid graphs
In this section we prove some results regarding the saturation number of polyomino chains and rectangular grids. We start with the linear chain Ln, where n denotes the number of squares. Such chain can be obtained as Cartesian product of the path Pn of length n and K2. Here Pn is the path on n edges so that Ln = Pn □ K2. Alternatively, Ln = Pn □ Pi. We draw Ln so that the edges of both copies of Pn are horizontal, see Figure 1.
Figure 1: Linear polyomino chain L6 = P6 □ K2.
We start by quoting two facts about the saturation number and the structure of smallest matchings in paths.
Proposition 3.1 ([6]). Let Pn be a path of length n. Then s(Pn) = [n]. More precisely,
r n, 31 n
s(Pn)= r , 3 | (n - 1) [ n±l, 3 | (n - 2).
Proposition 3.2. Let Pn be a path of length n. Then Pn has a smallest maximal matching that leaves at least one of the end-vertices unsaturated.
Proof. Let n be divisible by 3. We form groups of three consecutive edges and construct a matching M by taking the middle edge of each group. M is obviously a smallest maximal matching and leaves unsaturated both end-vertices of Pn. If n = 3k +1, again consider groups of 3 consecutive edges, take the middle edge in each group and add the sole edge that does not belong to any group. Again the constructed matching is a smallest maximal
194
Ars Math. Contemp. 15 (2018) 147-160
matching. Finally, when n = 3k + 2, construct a matching in the same way by taking the middle edge from each of k groups of three consecutive edges and adding the edge saturating the rightmost vertex.	□
Next we show that we can construct a smallest maximal matching in Ln without using vertical edges. This result will enable us to reduce the problem of finding the saturation number of Ln to known results about s(Pn ).
Proposition 3.3. Let M be a maximal matching in Ln containing k > 0 vertical edges. Then there is another maximal matching M' in Ln containing k' < k vertical edges such that |M'| < |M|.
Proof. We label the vertices in the upper copy of Pn with w0, u1,..., un, from left to right, and vertices in the lower copy with v0, v1,..., vn, in the same direction. There are n +1 vertical edges, each of the form «.¿vj for some 0 < i < n. See Figure 2.
	
>„ -, V. ,	
Figure 2: Linear polyomino chain Ln.
Let M be a maximal matching in Ln with k > 0 vertical edges and let the leftmost vertical edge in M be the edge um vm. Obviously, m cannot be equal to 1.
We consider first the case m = 0. If uivi is also in M, we construct a matching M' as M' = M - {w0v0, u1v1} U {u0u1, v0v1}. Obviously, M' is a maximal matching of the same cardinality as M containing k - 2 vertical edges.
Let now both neighbors u1 and v1 of end-vertices of u0v0 be saturated by horizontal edges. Hence, both m1m2 and v1v2 are in M. Then at least one of u3 and v3 must be saturated by an edge of M. Let u3 be saturated. Then we can construct a matching M' as M' = M — {u0v0, u1 u2} U {m0m1}. Again, M' is a maximal matching, |M= |M| — 1 and k' = k — 1. The case of saturated v3 follows by symmetry.
The last case to consider for m = 0 is the one in which only one of u1, v1 is saturated by a, necessarily horizontal, edge of M. Let it be u1. Hence, m1m2 g M and v1v2 G M. Then v3 must be saturated and M' = M — {u0v0} U {v0v1} is a maximal matching of the same cardinality as M but with one vertical edge less. Hence, the claim holds if the leftmost vertical edge in M is u0v0. This case is depicted in Figure 3.
2
M
"2 M'
Figure 3: The case when m = 0 and only one of u1,v1 is saturated by M.
Let now the leftmost vertical edge in M be u2v2. Then both m0m1 and v0v1 must be in M, and at least one of vertices u3 and v3 must be saturated by an edge of M. Let it be
T. Doslic et al.: Saturation number of lattice animals
195
u3. Then the matching M' constructed as M' = M - {u2v2, v0vi} U {viv2} will be a maximal matching with smaller cardinality and with one vertical edge less than M.
Similar constructions apply when the leftmost vertical edge of M is near the right end of the chain. The simplest is the case m = n - 1, when also the rightmost edge unvn must be in M. Then by switching the edges on the rightmost square one readily obtains a maximal matching of the same size as M but without vertical edges. The case m = n - 2 forces both horizontal edges Mn-1Mn and vn-1vn to be in M. Then at least one of u„_3 and vn_3 must be saturated. Let it be vn_3. Then the matching M' = M - {«n-2vn-2,«n-1Mn} U {«„-2Mn-1j is a maximal matching of smaller size than M without vertical edges. Remains the case when unvn is the leftmost (and hence the only) vertical edge in M. If only one of Mn-1, vn-1 is saturated, let us say Mn-1, it suffices to switch unvn and vn-1vn to obtain a maximal matching M' of the same size without vertical edges. If both wn-1, vn-1 are saturated, they must be saturated by horizontal edges m„_2«„_1 and vn-2vn-1, respectively. Also, at least one of m„_3 and vn_3 must be saturated. Let it be vn_3. Then M' = M - {unvn, v„_2vn-1} U {vn-1vn} is a maximal matching of smaller size than M but without vertical edges.
Now we can look at the remaining cases in a unified manner. So, let umvm, 3 < m < n - 3, be the leftmost vertical edge in a maximal matching M. If um+1vm+1 is also in M, we construct M' by switching the edges on the square um, um+1, vm+1, vm, obtaining a maximal matching of the same size but with two vertical edges less. Hence, we can suppose that «m+1vm+1 ^ M.
If both wm-1 and um+1 are unsaturated, then both vm-1 and vm+1 must be saturated, necessarily by horizontal edges vm-2vm-1 and vm+1vm+2, respectively. Further, both um_2 and um+2 must be saturated, again by horizontal edges. The situation is shown in Figure 4.
					
Vm-2 Vm_! Vm Vm+1 Vm+2					
M
v
m—2	Vm V„
M'
Figure 4: The case when wm-1 and wm+1 are both unsaturated.
We construct M' as M' = M - {«mvm} U {wmwm+1}. Obviously, M' is a maximal matching of the same size as M and with one vertical edge less. The situation in which both vm-1 and vm+1 are unsaturated follows by symmetry.
It remains to consider the case when at least one of «m-1, wm+1 and at least one of vm-1, vm+1 are saturated. We construct a new matching M'' by keeping the part of M to the left of «mvm, shifting all edges of M that were right of «mvm one place to the left (hence, mimi+1 goes to ui-1ui, to vl_1v; and to ui-1vi-1 for m < l < n) and moving umvm to unvn. Obviously, M'' is a maximal matching of the same size as M and with the same number of vertical edges, but with the leftmost vertical edge at some place l > m. Let us look at the situation on the right-hand side of Ln.
If un_1vn_1 is in M'', then M' with the desired properties can be obtained by switching edges on the rightmost square of Ln. If un_1vn_1 is not in M'', then also un_2vn_2 cannot be in M, and M' can be constructed in exactly the same manner as when unvn is the only vertical edge in M.
196
Ars Math. Contemp. 15 (2018) 147-160
Hence, no matter where in M the leftmost vertical edge appears, we can always construct a maximal matching of the same or smaller size with strictly smaller number of vertical edges.	□
Corollary 3.4. There is a maximal matching in Ln of cardinality s(Ln) without vertical edges.
Corollary 3.5. 2s(P„) < s(L„) < 2s(P„) + 1.
Proof. We know that there is a smallest maximal matching M in Ln (i.e., of the size equal to s(Ln)) without vertical edges. Hence all edges of M are horizontal, and each edge belongs to one of two copies of Pn in Ln. If the cardinality of M is smaller than 2s(Pn), then at least one of two copies of Pn will contain two adjacent unsaturated vertices. This proves the left inequality.
To prove the right inequality, let us take a smallest maximal matching Mu in the upper copy of Pn. If Mu saturates exactly one end-vertex of Pn, let us take it so that it saturates u0. Let Mv be a smallest maximal matching in the lower copy of Pn obtained by taking the edges corresponding to the edges of Mu and shifting them one place to the right. Then Mv saturates the vertices in the lower copy of Pn adjacent to the vertices of the upper copy of Pn left unsaturated by Mu. Hence M = Mu U Mv is a maximal matching in Ln of size 2s(Pn ).
It remains to consider the case when all smallest maximal matchings in Pn leave both end-vertices unsaturated. In that case, take two smallest maximal matchings Mu and Mv in upper and lower copy of Pn, respectively, and shift Mv one place to the right so that it saturates the neighbors of the vertices left unsaturated by Mu. That leaves unsaturated both end-vertices of v0vi. By adding that edge to the maximal matching constructed from Mu and shifted Mv we obtain a maximal matching of size 2s(Pn) + 1.	□
From this we can get the exact expression for the saturation number of the linear poly-omino chain.
Theorem 3.6. Let Ln be the linear polyomino chain. Then
'2r + 1, 3 | n s(L„) = <( , 3 | (n - 1) ^^, 3 | (n - 2).
Proof. If 3 | (n — 1) or 3 | (n — 2) there is a smallest maximal matching M for Pn such that M saturates exactly one end-vertex of Pn. Therefore, it follows from the proof of Corollary 3.5 that s(Ln) = 2s(Pn) and we are done. If 3 | n, the smallest maximal matching of Pn is uniquely defined and it leaves both end-vertices unsaturated. Hence, in this case we obtain s(Ln) > 2s(Pn) and therefore, s(Ln) = 2s(Pn) + 1.
Examples of smallest maximal matchings in Ln for all classes of divisibility of the chain length by 3 are given in the Figure 5.	□
The above approach can be successfully applied also to obtain non-trivial upper bounds on the saturation number of grid graphs that arise as Cartesian products of two (or more) paths. By taking smallest maximal matchings in all horizontal (or in all vertical) copies of paths in Pm □ Pn, shifting them and adjusting by adding an edge where necessary, and using symmetry, we can obtain following upper bound on s(Pm □ Pn).
T. Doslic et al.: Saturation number of lattice animals
197

(b)
(c)
Figure 5: Linear polyomino chains with maximal matchings.
Proposition 3.7. s(Pm □ Pn) < min{(m + 1)[s(Pn) + 1], (n + 1)[s(Pm) + 1]}.
This upper bound can be improved a bit by exploiting particular relationships between parities and remainders modulo 3 of m and n. See Figure 6 for an example. We believe, however, that our upper bounds capture the asymptotic behavior of the saturation number of rectangular grids.
Figure 6: Graph P8 □ P3 with a maximal matching.
Now we go back to polyomino chains. In the following theorem we give the exact closed formulas for the saturation number of polyomino chains where all internal squares are kinky.
Theorem 3.8. Let Sk be a polyomino chain with k squares such that all internal squares are kinky. Then
k
KSfc) =
2
+ 1.
Proof. We consider two cases.
1.	Let k be even. Since the number of vertices in Sk is 2k+2, a perfect matching (which always exists) has k +1 edges. Using Lemma 2.1 we obtain that s(Sk) > . Since k is even, we obtain s(Sk) > [|] +1. To show the upper bound, we construct a maximal matching M from Figure 7.
Obviously, |M| = f + 1 = [f] + 1. Hence, s(Sk) = [f] + 1.
2.	If k is odd, let M' be a maximal matching from Figure 8.
Obviously, |M= f++1 + 1 and therefore, s(Sk) < + 1 = [f] +1. Now suppose that there is a maximal matching N for Sk such that | N | < . It is easy to see that at least one of edges ei, e2, and e3 must be in N. Consider the following cases.
198
Ars Math. Contemp. 15 (2018) 147-160
Figure 7: Polyomino chain Sk (k even) with maximal matching M.
				J	
					
				V	
				/2	/3
					e3
e2
Figure 8: Polyomino chain Sk (k odd) with maximal matching M.
(a)	If e1 G N, then also e3 G N or f3 G N. Therefore, for the graph Sk-3 (see Figure 8) it must hold s(Sk-3) < f-3, which is a contradiction with Case 1.
(b)	If e2 G N, then for the graph Sk-1 (see Figure 8) it must hold s(Sk-1) < , which is a contradiction with Case 1.
(c)	If e3 e N, then also one of the edges e1, f1, f2 must be in N. If e1 e N or f1 G N, then for the graph Sk-3 (see Figure 8) it must hold s(Sk-3) < , which is a contradiction with Case 1. Therefore, suppose that f2 G N. But in this case we can use similar reasoning and either obtain a contradiction with the Case 1 or eventually obtain a matching M', which is a contradiction since |M'| > |N|.
Since we obtain a contradiction in every case, it follow s that every maximal matching
of Sk has at least + 1 edges. Since k++1 + 1 = lf ] +1 it follows s(Sf ) > lf ] +1 and we are done.	□
4 Hexagonal animals
In this section we prove some results regarding the saturation number of benzenoid chains and coronenes.
4.1 Benzenoid chains
A benzenoid chain of length h will be denoted by Bh. If all interior hexagons of a benzenoid chain are straight, the chain is called a polyacene and denoted by Ah.
T. Doslic et al.: Saturation number of lattice animals
199
Saturation number of benzenoid chains has been already studied in a recent paper coau-thored by one of the present authors [5]. We quote without proof some basic results established there.
Proposition 4.1 ([5]). Let Bh be a benzenoid chain with h hexagons. Then s(Bh) > h +1.
Proposition 4.2 ([5]). For any h it holds
s(Bh) + 1 < s(Bh+1) < s(Bh) + 2.
Proposition 4.3 ([5]). s(Bh) = h +1 if and only if Bh = Ah.
Let Bh, 1 denote a chain of length h = k + m in which hexagon hk is kinky and all other hexagons are straight. An example is shown in Figure 9. Furthermore, let Bh k denote a benzenoid chain of length h with exactly k kinky hexagons.
Figure 9: A chain with one kinky hexagon.
Proposition 4.4 ([5]). For any h it holds
s(Bh,i) = h + 2.
Hence one kinky hexagon means one more edge in the smallest maximal matching. The following claim was stated in [5] as Proposition 5.
Proposition 4.5 ([5]). Let Bh,k be a benzenoid chain of length h with k kinky hexagons such that no two kinky hexagons are adjacent. Then s(Bh,k) = h + k +1.
However, we show in Proposition 4.7, Proposition 4.8, and Proposition 4.9 that the above proposition provides only an upper bound for the saturation number, which is evident from the following proposition.
Proposition 4.6. Let Bh k be a benzenoid chain of length h with k kinky hexagons. Then
s(Bh,k) < h + k + 1.
Proof. Let M be a matching of Bh,k obtained by taking all edges shared by two hexagons, one additional edge in each terminal hexagon and all edges connecting vertices of degree two in kinky hexagons. See Figure 10 for an example.
It is easy to see that M is a maximal matching and |M | = h + k + 1. Therefore, we are done.	□
200
Ars Math. Contemp. 15 (2018) 147-160
Figure 10: Maximal matching M.
However, in the same graph shown in Figure 10 we can construct a smaller maximal matching by simply taking all vertical edges. Hence h + k + 1 is only an upper bound on s(Bh,k) and it can be improved in particular cases.
Let Bh be a chain of length h. A straight segment in Bh is any sequence of consecutive straight hexagons. Equivalently, it is any sub-word made of consecutive L's in the LA sequence of Bh. The number of consecutive straight hexagons is the length of the straight segment.
Figure 11: A benzenoid chain B8 with two straight segments (labelled with bold edges), one of length 2 and one of length 1.
In the following we consider the saturation number of benzenoid chains where all straight segments are of length one and no two kinky hexagons are adjacent. It turns out we have to distinguish between three cases. In all of them the upper bound from Proposition 4.6 is improved.
Proposition 4.7. Let B2k+1,k be a benzenoid chain such that all straight segments are of length one and no two kinky hexagons are adjacent. Then
s(B2fc+i,fc) < 4(10k + 9 - (-1)k).
Proof. We build B2k+1,k from left to right by adding blocks of 4 consecutive hexagons at a time. Each block has the form LALL and it is added on the rightmost hexagon of the already constructed chain so that it becomes a kinky hexagon in the new chain. To show an upper bound for the saturation number, we construct a maximal matching M of B2fc+1,fc. For the first four hexagons we need six edges in a maximal matching such that the edge connecting the first and the second block of hexagons is in the matching. See Figure 12.
T. Doslic et al.: Saturation number of lattice animals
201
Figure 12: Two possibilities for a maximal matching M of the first block.
Afterwards, we can always add four hexagons at a price of five new edges in a maximal matching. Let l be the number of blocks in B2k+i,k. We consider two cases.
•	If k is odd, then 4 | (2k - 2) and l = ^k-2 = ^r1 and we have three additional hexagons in a benzenoid chain. For these three hexagons, we need 4 additional edges in a maximal matching. We obtain |M| = 6 + 5(l - 1) + 4 = 10 + 5 • = .
•	If k is even, then l = = | and we have one additional hexagon in a benzenoid chain. For this hexagon, we need 1 additional edge in a maximal matching. Therefore, we get |M| = 6 + 5(l - 1) + 1 = 7 + 5 • ^ = .
Combining both cases, we obtain |M| = 1 (10k + 9 - (-1)k).	□
Proposition 4.8. Let B2k+2,k, k G N, be a benzenoid chain such that all straight segments are of length one and no two kinky hexagons are adjacent. Then
s(B2k+2,k) < 4(10k +13 - (-1)k).
Proof. We build B2k+2,k from left to right by adding blocks of 4 consecutive hexagons at a time. Each block has the form LALL or each block has the form LLAL (before adding) and it is added on the rightmost hexagon of the already constructed chain. Because of the symmetry, we can assume that each block has the form LALL (otherwise we can start from right to left). The new block is added on the last hexagon such that it becomes a kinky hexagon. To show an upper bound for the saturation number, we construct a maximal matching M of B2k+2,k. For the first four hexagons we need six edges in a maximal matching such that the edge connecting the first and the second block of hexagons is in the matching. Afterwards, we can always add four hexagons at a price of five new edges in a maximal matching. Let l be the number of blocks in B2k+2,k. We consider two cases.
•	If k is odd, then 4 | (2k + 2) and l = = ^. Weobtain |M| = 6 + 5(l - 1) =
6 + 5 • ^ = .
•	If k is even, then l = (2k+42)-2 = | and we have two additional hexagons in a benzenoid chain. For these two hexagons, we need 2 additional edges in a maximal matching. Therefore, we get |M| = 6 + 5(l - 1) + 2 = 8 + 5 • k-2 = .
Combining both cases, we obtain |M| = 4 (10k + 13 - (-1)k).	□
202
Ars Math. Contemp. 15 (2018) 147-160
Proposition 4.9. Let B2k+3,k, k G N, be a benzenoid chain such that all straight segments are of length one and no two kinky hexagons are adjacent. Then
s(B2k+3,k) < 1 (10k + 19 + ( —1)k).
Proof. We build B2k+3 k from left to right by adding blocks of 4 consecutive hexagons at a time. Each block has the form LLAL (before adding) and it is added on the rightmost hexagon of the already constructed chain. The new block is added such that the first hexagon of this block becomes a kinky hexagon. To show an upper bound for the saturation number, we construct a maximal matching M of B2k+3 k. For the first four hexagons we need six edges in a maximal matching such that the edge connecting the first and the second block of hexagons is in the matching. Afterwards, we can always add four hexagons at a price of five new edges in a maximal matching (such that the edge connecting that block with the next block is in the matching). Let l be the number of blocks in B2k+3 k. We consider two cases.
•	If k is odd, then 4 | ((2k + 3) - 1) and we have to add one additional hexagon (for this hexagon we need one additional edge). Hence, l = = . We obtain
|M| = 6 + 5(l - 1) + 1 = 7 + 5 • = 5k29.
•	If k is even, then 4 | ((2k + 3) - 3) and we have to add three additional hexagons (for this three hexagons we need four additional edges in a maximal matching). Hence,
l = 2k = k. Therefore, we get |M| = 6 + 5(l - 1) + 4 = 10 + 5 • = 5k2r0.
Combining both cases, we obtain |M| = 1 (10k + 19 + (-1)k).	□
4.2 Coronenes
In this section we prove bounds for the saturation number of coronenes. These highly symmetric benzenoid systems have long been attracting the attention of both theoretical and experimental chemists. They are suggested as markers for vehicle emissions, since they are produced by incomplete combustion of organic matter. Coronene H1 is just a single hexagon, and Hk is obtained from Hk-1 by adding a ring of hexagons around it. See Figure 13 for an example of coronene H4.
Proposition 4.10. Let Hk be a coronene. Then
2k2,	3 | (k - 1)
3k2 < s(Hk) <{ 2k2 + f, 3 | k
2k2 + 2k+2, 3 | (k - 2).
Proof. Obviously, every coronene has a perfect matching. Since the number of vertices in Hk is 6k2, it follows by Lemma 2.1 that s(Hk) > §k2.
For the upper bound, we will consider just the case when 3 | (k -1), since the proofs for other two cases are almost the same. To prove this case, we construct a maximal matching M for Hk. In the matching we put all the vertical edges lying in the center layer of the coronene Hk. Since there are 2k - 1 hexagons in the center layer, we obtain 2k edges in the matching M. See Figure 13. Next, we continue at the top half of the coronene with alternating non-vertical and vertical edges such that two layers of edges are needed
T. Doslic et al.: Saturation number of lattice animals
203
Figure 13: A coronene
for every three layers of hexagons. Furthermore, for every non-vertical layer of edges we need one additional vertical edge. Let x be the number of edges in M in the top half of the coronene. Then
x = (2k - 1) + (2k - 3) +(2k - 4) +(2k - 6) + ••• + (k + 3) + (k + 1) = = 2(k ~ 1) • (2k) - (1 + 3 + 4 + 6 + • • • + (k - 3) + (k - 1)) =
4k2 - 4k (k2 - k (	,,
= -3--- (2 + 5+ ••• + (k - 2))J =
_ 4k2 - 4k ( k2 - k k2 - k
= 3 V 2 6 j = = k2 - k.
Finally, we obtain |M| = 2k + 2x = 2k + 2(k2 - k) = 2k2.	□
In the next proposition we improve the lower bound for any k > 7.
Proposition 4.11. Let be a coronene where k > 1. Then
s(Hk) > 2k2 - 3k - 1.
Proof. For any , k > 2, one can construct a disk-shaped fullerene by taking another copy of and connecting the borders in the following way. We insert 6k edges between vertices of degree 2 such that end-vertices lie in different copies of . Obviously, this can be done in such a way that the resulting graph F is planar with only pentagonal and hexagonal faces. Since F is also 3-regular, it is a fullerene with 12k2 vertices.
Let M' be a maximal matching in each copy of . Then this matching can be extended to a maximal matching M of a graph F by adding at most 6k edges between two copies of Hfc. Therefore, |M| < 2|M'| + 6k. From Theorem 4.1 in [2] it follows |M| > J-^f^-2 = 4k2 - 2. Therefore, we obtain 2|M+ 6k > 4k2 - 2. Finally, |M> 2k2 - 3k - 1. □
204
Ars Math. Contemp. 15 (2018) 147-160
Concluding remarks
In the paper we have established some bounds and also exact values for the saturation number of certain families of lattice animals. However, there are still many open problems regarding the exact values for the saturation number of different families of graphs.
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, http://match.pmf.kg.ac.rs/electronic_versions/Match68/n1/ match68n1_10 9-130.pdf.
[2]	V. Andova, F. Kardoss and R. Sskrekovski, Sandwiching saturation number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 73 (2015), 501-518, http://match.pmf.kg. ac.rs/electronic_versions/Match73/n2/match73n2_501-518.pdf.
[3]	A. Behmaram, T. Doslic and S. Friedland, Matchings in m-generalized fullerene graphs, Ars Math. Contemp. 11 (2016), 301-313, doi:10.26493/1855-3974.882.539.
[4]	T. Doslic, Saturation number of fullerene graphs, J. Math. Chem. 43 (2008), 647-657, doi: 10.1007/s10910-006-9217-3.
[5]	T. Doslic and I. Zubac, Saturation number of benzenoid graphs, MATCH Commun. Math. Comput. Chem. 73 (2015), 491-500, http://match.pmf.kg.ac.rs/electronic_ versions/Match73/n2/match73n2_4 91-500.pdf.
[6]	T. Doslic and I. Zubac, Counting maximal matchings in linear polymers, Ars Math. Contemp. 11
(2016),	255-276, doi:10.26493/1855-3974.851.167.
[7]	N. Tratnik and P. Zigert Pletersek, Saturation number of nanotubes, Ars Math. Contemp. 12
(2017),	337-350, doi:10.26493/1855-3974.1056.ae9.
[8]	M. Zito, Small maximal matchings in random graphs, Theor. Comput. Sci. 297 (2003), 487-507, doi:10.1016/s0304-3975(02)00653-9.
[9]	M. A. A. Zito, Randomised Techniques in Combinatorial Algorithmics, Ph.D. thesis, University of Warwick, Warwick, 1999, http://www.dcs.warwick.ac.uk/report/pdfs/ cs-rr-369.pdf.