ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 79-88
https://doi.org/10.26493/1855-3974.1508.f8c
(Also available at http://amc-journal.eu)
Block allocation of a sequential resource
Tomislav Doslic *
University of Zagreb, Faculty of Civil Engineering, Kaciceva 26, 10000 Zagreb, Croatia
Received 16 October 2017, accepted 27 May 2019, published online 22 June 2019

Abstract
An H-packing of G is a collection of vertex-disjoint subgraphs of G such that each component is isomorphic to H. An H-packing of G is maximal if it cannot be extended to a larger H-packing of G. In this paper we consider problem of random allocation of a sequential resource into blocks of m consecutive units and show how it can be successfully modeled in terms of maximal Pm-packings. We enumerate maximal Pm-packings of Pn of a given cardinality and determine the asymptotic behavior of the enumerating sequences. We also compute the expected size of m-packings and provide a lower bound on the efficiency of block-allocation.
Keywords: Maximal matching, maximal packing. Math. Subj. Class.: 05C70, 05A15, 05A16
1 Matchings and packings
A matching M in a graph G is a collection of edges of G such that no two edges from M have a vertex in common. The number of edges of M is called the size of the matching. Small matchings are not interesting - they are easy to find and enumerate. Hence, we are mostly interested in matchings that are as large as possible. There are two ways to quantify the idea of "large" matchings, one of them based on their cardinality, the other based on the set inclusion.
A matching M is maximum if there is no matching in G with more edges than M. The cardinality of any maximum matching in G is called the matching number of G and denoted by v(G). The matching number of a graph on n vertices, obviously, cannot exceed |_n/2_|, since each edge saturates two vertices. A matching that saturates all vertices of G is called a perfect matching.
* Partial support of the Croatian Science Foundation (research projects BioAmpMode (Grant no. 8481) and LightMol (Grant no. IP-2016-06-1142)) is gratefully acknowledged. I also thank Damir Vukicevic and Kristina Ana Skreb for useful discussions.
E-mail address: doslic@grad.hr (Tomislav Doslic)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
104
ArsMath. Contemp. 17 (2019) 80-114
A matching M in G is maximal if it cannot be extended to a larger matching in G, i.e., if no other matching in G contains it as a proper subset. Obviously, every maximum matching is also maximal, but the opposite is generally not true. The cardinality of any smallest maximal matching in G, denoted by s(G), is the saturation number of G; the largest size of a maximal matching is, of course, v(G).
Matchings are natural models for many problems in natural, technical and social sciences. Worth mentioning are applications of perfect matchings in organic chemistry and solid state physics. For a general background on matching theory and terminology we refer the reader to the classical monograph by Lovasz and Plummer [14]. For graph theory terms not defined here we also recommend [3, 19].
A closely related concept of packing is a generalization of matching. There are several varieties of packing; we consider here only the simplest case. An H-packing of G is a collection of vertex-disjoint subgraphs of G such that each component is isomorphic to H [3]. Hence, a matching of G is a P2-packing in G, where P2 denotes a path on 2 vertices. Again, we are interested only in large packings. If a packing is a spanning subgraph, we say that the packing is perfect; if no other H-packing has more components, the packing is maximum; finally, if an H-packing cannot be extended to a valid H-packing, we say that it is a maximal H-packing. The H-packing number and H-saturation number are defined in the same way as for matchings. When H = Pm we denote these two quantities by vm(G) and sm(G) and call them the m-packing number and m-saturation number, respectively. We refer the reader to [12,13] for some aspects of P3-packings in claw-free and in subcubic graphs and to [15] for similar problems in directed graphs.
Maximal matchings and packings can serve as models of several physical and technical problems such as the block-allocation of a sequential resource or adsorption of dimers and/or polymers on a structured substrate or a molecule. When that process is random, it is clear that the substrate can become saturated by a number of units much smaller than the theoretical maximum. The respective saturation numbers provide an information on the worst possible case of clogging; they measure how inefficient the adsorption or the allocation process can be. However, in order to assess its efficiency, we also need to know how likely it is that a given number of units will saturate the substrate. Hence, we must study the enumerative aspects of the problem.
For the matching case, the question has been answered in [7]. The main goal of this paper is to contribute to the corpus of knowledge about the enumerative aspects of maximal Pm-packings in paths and cycles. Specifically, we compute the efficiency of block-allocation of length m of a sequential linear or cyclic resource. In some cases we provide explicit formulas for the number of maximal m-packings of a given cardinality, while in other cases we establish the recurrences for the enumerating sequences and then use their uni- and bivariate generating functions to determine their asymptotic behavior.
Finally, in the concluding section we discuss some open problems and indicate some directions of possible future research.
2 Paths and cycles 2.1 Paths
We remind the reader that throughout this paper Pn denotes the path on n vertices, hence of length n - 1. As a motivation, we consider a parking lot made of n parallel concrete strips such that a car can be parked on any two neighboring strips. In ideal situation, when all
T. Doslic: Block allocation of a sequential resource
81
drivers take care and park responsibly, the lot can accommodate \n/2 J cars. However, if the drivers are careless, the lot can become saturated by a smaller number of cars, as shown in Figure 1. In the worst possible case, it can become saturated by as few as \(n + 1)/3J
Figure 1: A saturated parking lot and the corresponding maximal matching.
cars. Hence, it is of interest to find out how likely is this to happen, and what is the expected number of cars under the random regime.
In the continuous setting, this problem is known as the random car-parking problem of Renyi [16, 17], while in discrete setting it has a natural representation as a problem of maximal matching in Pn, as shown in Figure 1; it was considered in detail in [7], where its full solution was obtained, including the explicit formulas for the number of different configurations accommodating a given number of cars. Also, the expected number of cars under the random regime was computed, and the asymptotic behavior of the sequence enumerating all possible parking arrangement was determined.
But what happens if we wish to park trucks such that each of them is twice as wide as a car? Each truck will then consume three consecutive strips, as shown in Figure 2, and the corresponding graph-theoretical model will not be a matching, but a packing of copies of
n n n
Figure 2: A parking lot saturated with trucks.
P3 in Pn. Obviously, the structure of the problem remains the same if instead of parking lots and cars and trucks we consider any sequential resource of length n which is allocated in blocks of m > 2 consecutive units. All such situations can be studied as problems of packing copies of Pm in Pn. We call such a packing an m-packing. In this subsection we consider the enumerative aspects of m-packings in paths. Before counting them, we state
104
ArsMath. Contemp. 17 (2019) 82-114
(without proof) two results about the smallest and the largest possible size of m-packings in Pn.
Proposition 2.1. Let Pn be a path on n vertices. Then
n + m — 1
(Pn)
2m — 1
and vm(Pn)
n m
We now start counting all maximal m-packings in Pn. Let ^"ik denote the total number of maximal m-packings in Pn with exactly k copies of Pm.
Proposition 2.2. The sequence is given by the recurrence
2m-1
/(m) - V /(m)
l=m
for n > 2m — 1 and with the initial conditions
(m)	(m)	(m)
/o,o) = /(,o) - • • • = /m-i,o-1 and = 0 for all other values of l.
Proof. Let us label the vertices of Pn by v1,..., vn. Let vl be the vertex with the highest label that is covered by a copy of Pm in a maximal m-packing of size k. Clearly, vl G {vn-m+1,..., vn} (otherwise there would be enough place to pack one more copy of Pm, contrary to the assumption of maximality), and the remaining k — 1 copies of Pm must form a valid maximal packing of Pm of size k — 1 in the remaining portion of Pn, i.e., in Pl-m+1. The initial conditions count trivial packings of size zero.	□
From the above recurrence one can immediately compute the bivariate generating function for the numbers by multiplying them throughout by xnyk and summing over all n > 2m — 1, k > 1. We state the result omitting the computational details.
Theorem 2.3. Let Fm(x, y) = J2 n k> 0 /nkxnyk be the bivariate generating function of
/nmk).Then
Fm(x,y)=1 Pm(x)( ), 1 — yqm(x)
where pm(x) = and qm(x) = xmpm(x).
Corollary 2.4. The bivariate generating function of /""k) is given by
1 xm
Fm(x, y) =
1 — x — xm(1 — xm)y
The generating function Fm(x) = J2n>o ^nm)xn for the sequence enumerating the total number of m-packings in Pn is now obtained by substituting y = 1 into the expression
for Fm(x,y).
T. Doslic: Block allocation of a sequential resource
83
Corollary 2.5. The generating function of the sequence enumerating the total number of maximal m-packings in Pn is given by
1 - xm
Fm(x) -, _	, ..2m'
(m)
1 — X — Xm + X
From the above result we can deduce the recurrence satisfied by ^
n
Corollary 2.6. The numbers satisfy the recurrence
/(") = //;(m) +_____i //;(m)
r n = Vn-m + + /n-2m+1
for n > 2m — 1 with the initial conditions /m) = • • • = /"m" = 1 and /""+ = i + 1 for 1 < i < m — 2.
The numbers /"k form a triangular array with rows indexed by n and columns indexed by k. It can be deduced from the form of the bivariate generating function that the columns are, in fact, shifted rows of the triangle of multinomial (m-nomial) coefficients. Recall that the (p, q)-th m-nomial coefficient
L?/mJ / \/ , 1 • \ t(m) _ (_ 1)i P\ p + q - 1 - im\
p.q_ (1)lA p -1 )
is the coefficient of xq in (1 + x + • • • + xm 1)p. (See, for example, sequence A035343 in [18] for m = 5.) The observation can be formally stated in the following way.
Corollary 2.7.
„/,0 _
,k	k+l.n-mk '
(m) (m)
^n.fc _ ti)
As a consequence, we can obtain formulas for \k) and /(n"). We refer the reader to the On-Line Encyclopedia of Integer Sequences for more details on multinomial coefficients [18].
Corollary 2.8.
L mm-fcJ
,(m)_ ^ , Uifk + A (n + k — m(i + k)V
/n'fc = ^ ( 1) I i A k y
LmnJ Lmm-kJ
/(m) = p	(—kfn+k—m(i+k)
k=0 i=0 V i / V k
When m = 2, the above formulas reduce to known results about the number of maximal matchings [7].
As a further consequence, we note that the number of all maximal m-packings of size k in all paths is given by mk+1.
Our next goal is to determine the asymptotic behavior of the enumerating sequences and then use it to compute the expected size of a maximal m-packing in Pn. We rely on the following version of Darboux's theorem [2].
104
ArsMath. Contemp. 17 (2019) 84-114
Theorem A. If the generating function f (x) = n>o anxn of a sequence (an) can be written in the form f (x) = (1 — h(x), where w is the smallest modulus singularity of
f and h is analytic in w, then an
h(w)n
r(-a)wn
-, where r denotes the gamma function.
As a consequence, the expected size of a maximal m-packing in Pn, nm(Pn), can be computed as
.(Pn) =
[xn]
dFm(x,y) dy
ly=i
[xn]Fm(x, y) |y=i '
where [xn]F(x) denotes the coefficient of xn in the expansion of F(x).
We refer the reader to [2, 20] for more information on obtaining the asymptotics of a sequence from its generating function.
We start by observing that Fm(x) = Fm(x, y) |y=1 and dFma(x'y) |y=1 can be represented as
Fm(x) =1--
i
Pm (x)
l-?m(x)
-1
1--— ) gm (x)
wm
and
dFm (x, y)
dy
y=i
1
-2
Pm(x)qm(x)
„,. 1-qm(x)
-2
1--— ) hm(x).
wm
Here wm denotes the smallest (and the only) real solution of the equation qm (x) plugging this into Theorem A we obtain following results.
Theorem 2.9. The asymptotics of the number of m-packings in Pn is given by
1. By
^n
m)
gm(Wm) • W-
Theorem 2.10. The expected size of a maximal m-packing in Pn is given by
nm (Pn) =
mqm (wm)
where wm is the only real solution of qm (x) = 1.
Now we can define the efficiency of random m-packing in Pn as the quotient of the expected and the optimal size of an m-packing. Since the size of any largest possible m-packing in Pn is \n/m\, the efficiency is given by
e(m)
wmqm (wm)
It is, hence, of interest to investigate the behavior of the above quotient for large values of n and m. (We will assume that n > m, since the opposite case is not very interesting.) Numerical computations indicate that it initially decreases from 0.823 for m = 2 and achieves the minimum value of 0.758317 for m = 9, and then increases slowly (apparently monotonously) so that for m = 100 it has the value of approximately 0.796. In the rest of this subsection we show that e(m) remains bounded from below for all values of m.
n
m
m
x
x
2
w
m
m
wx
n
T. Doslic: Block allocation of a sequential resource
85
For the beginning, we transform the expression for q!m (x) as follows:
mxm-1	xm (1 _ xm)
q'm (x) = m- (1 - 2xm) + X 1 X )
1 — x	1 — x
l(1 - xm) 1 — x
2m 1 m 1
m
By plugging in x = wm, the first term on the right-hand side becomes 1, and by multiplying the resulting equation through by wm, we obtain
wmqm (w m) = ( 2 ~ 1 m ) m +
1 - w	1 - w
We would like to estimate the right-hand side and give some upper bound. The first term never exceeds m; it is enough to note that wm > 1/2 for all m > 2, and from there it follows 2 - 1_1wm < 2 - x_\-r < 1. In order to bound the second term, we notice that for large enough values of m we must have wm < 1 - m. Indeed, this is equivalent to
2 \ m /	2 \ 2m 3
1 - - - 1 - - >-, m J \ m J	m
and this is true, since the left-hand side tends to e-3 - e-6 « 0.047308, while the right-hand side tends to zero. Numerical computations show that "large enough" here means m = 68. By plugging in the upper bound wn < 1 - m into the second term, we obtain 1 WW; < m. Now the right-hand side can be bounded from above by 4m. This gives us a lower bound on the efficiency.
Proposition 2.11. The efficiency of m-packings is bounded from below. For all m > 2,
3
elm) > —.
4
The same argument as above could be used to show that for large enough values of m and for any real a > 0, an expression of the type 1 - m will be an upper bound on wm. This implies that the right-hand side of the expression for wmqm (wm) can be bounded from above by m, and consequently, that	e(m) = 1.
Our results indicate that longer blocks achieve better efficiency of random block allocation of a sequential resource. The dependency is rather mild, and the growth is slow. For example, a hundredfold increase of the block length from m = 1000 to m = 100 000 results in the moderate increase of efficiency from e(1000) = 0.844 to e(100000) = 0.903. Still, the block length of nine seems to be a bad choice.
Before we move to the cycles, we mention that our analysis assumes that all packings are equally probable. It is known for maximal matchings that the efficiency is slightly better if instead one considers dynamics, i.e., the situation where the dimers arrive sequentially and try to bind to the substrate [9]. It would be interesting to see how such approach would affect the efficiency here.
2.2 Cycles
Let us now consider the number of maximal m-packings in a cycle Cn of length n > 3, n > m. We denote it by and the number of maximal m-packings in Cn of size k
i (m)
by
104
ArsMath. Contemp. 17 (2019) 86-114
Proposition 2.12. The numbers (Vk are given by
m—1
(S=-em,*—i^
n — m,k —1 1 / j "n—2m—l,k-2 i=1
for n > 3, k > 2, where count maximal m-packings of size k in Pn.
Proof. Let us consider vertex vn in Cn. If it is not covered by a copy of Pm in an m-packing, then it must be in a "hole" of size i for some 1 < i < m — 1. At each side of the hole there must be a copy of Pm. Hence the remaining k — 2 copies of Pm must form a valid m-packing in Pn—2m— 1, and those are counted by	1 k-1- As there are i
holes of size i containing vertex vn, the second term in the right-hand side of the above expression counts all of them. The first term counts the m-packings in Cn that cover vn by a copy of Pm.	□
Proposition 2.13. The numbers J™ satisfy the same recurrence as the numbers ■i'v™^, i.e.,
J™) = ((m) +_____, ((m)
(n = (n—m + + (n—2m+1
with the initial conditions
(m)	(m) ,
) = • • • = = 1
and Jm+)i = m + i for 0 < i < m — 1.
Hence, the asymptotic behavior, the expected size and the efficiency of m-packings in Cn are the same as in Pn.
3 Future developments
This manuscript presents a systematic attempt to address enumerative aspects of maximal Pm-packings in some classes of graphs with simple connectivity patterns. It continues the line of research of a recent paper concerned with maximal matchings [7]. As this is, to the best of my knowledge, the first paper of this type, it leaves unanswered many questions that arise in the course of research. In this last section we outline some of the open problems and suggest some possible directions for future research.
The most natural thing would be to count m-packings in some other families of graphs with repetitive structure that have low connectivity. Examples of such graphs are cactus chains, such as those considered in [5, 6, 7]. Due to their simple structure, it is reasonable to expect that the enumerating sequences will satisfy (rather short) linear recurrences with constant coefficients, yielding thus to the same type of asymptotic analysis as obtained here. Besides finding the asymptotics, an interesting problem would be to find the extremal chains. For maximal matchings (m = 2) the problem is solved for hexagonal cacti and it would be interesting to see if the pattern persists for larger values of m.
Another promising class could be the so-called thorny graphs. From a given graph G one obtains the t-thorny graph Tt(G) by appending t pendent vertices to every vertex of G. When G has a simple structure, the methods of this paper could be employed to obtain the recurrences for the number of m-packings in Tt(G). As an example, we consider 3-packings in Tt(Pn).
T. Doslic: Block allocation of a sequential resource
87
(3)
Proposition 3.1. Let pn ) denote the number of 3-packings in Tt(Pn). Then
P? = (2 )P-, ^ + P™,
for n > 3 with the initial conditions than can be verified by direct computation.
The next step could be to consider linear polymers of connectivity 2. Among them, the most interesting are without doubt the benzenoid chains. Again, there are some results for maximal matchings [6, 7] for benzenoid and polyomino chains, but for other classes of fascia- and rota-graphs [11] not even that case is investigated.
Another direction could be to consider structural and enumerative problems of m-packings in composite graphs, i.e., in graphs that arise from simpler building blocks via various binary operations known as graph products. We have considered here one such example of low connectivity (the thorny graph, that could be thought of as the corona product of G and Kt). However, many interesting operations such as, e.g., the Cartesian product, actually increase the connectivity. It would be too optimistic to expect that complete results of the type presented here could be obtained in general cases, but we believe that the cases when one component is a path or a cycle should be feasible. Another interesting problem would be to determine the m-saturation number of such graphs, in particular for the finite portions of grids and lattices. Also, nanostructures and fullerenes are natural candidates for investigation of structural properties related to m-packings. The results would generalize those for maximal matchings [1,4].
A graph G is equimatchable [10,14] if every maximal matching in G is also maximum, i.e., if all maximal matchings are of the same size. What can be said about equipackable graphs in which every maximal m-packing is also maximum m-packing?
Finally, it would be interesting to see if packing polynomials and maximal packing polynomials, modelled after their matching counterparts [7, 8, 14], would be useful in the study of packing enumeration.
References
[1]	V. Andova, F. Kardos and R. Skrekovski, 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/match7 3n2_501-518.pdf.
[2]	E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications, Dover, 2006, http://www.math.ucsd.edu/~ebender/CombText/.
[3]	R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer, Heidelberg, 4th edition, 2010, doi:10.1007/978-3-642-14279-6.
[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 F. Mal0y, Chain hexagonal cacti: matchings and independent sets, Discrete Math. 310 (2010), 1676-1690, doi:10.1016/j.disc.2009.11.026.
[6]	T. Doslic and T. Short, Maximal matchings in polyspiro and benzenoid chains, submitted, arXiv:1511.00590 [math.CO].
[7]	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.
104
ArsMath. Contemp. 17 (2019) 88-114
[8]	E. J. Farrell, An introduction to matching polynomials, J. Comb. Theory Ser. B 27 (1979), 75-86, doi:10.1016/0095-8956(79)90070-4.
[9]	P. J. Flory, Intramolecular reaction between neighboring substituents of vinyl polymers, J. Am. Chem. Soc. 61 (1939), 1518-1521, doi:10.1021/ja01875a053.
[10]	A. Frendrup, B. Hartnell and P. D. Vestergaard, A note on equimatchable graphs, Australas. J. Combin. 46 (2010), 185-190, https://ajc.maths.uq.edu.au/pdf/4 6/ajc_v4 6_ p185.pdf.
[11]	M. Juvan, B. Mohar, A. Graovac, S. Klavzar and J. Zerovnik, Fast computation of the Wiener index of fasciagraphs and rotagraphs, J. Chem. Inf. Comput. Sci. 35 (1995), 834-840, doi: 10.1021/ci00027a007.
[12]	A. Kelmans, Packing 3-vertex paths in claw-free graphs and related topics, Discrete Appl. Math. 159 (2011), 112-127, doi:10.1016/j.dam.2010.05.001.
[13]	A. Kosowski, M. Malafiejski and P. Zylinski, Packing three-vertex paths in a subcubic graph, in: S. Felsner (ed.), 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS, Nancy, France, volume AE of DMTCS Proceedings Series, 2005 pp. 213-218, proceedings of a conference held at Technische Universitat, Berlin, September 5 - 9, 2005,https://dmtcs.episciences.org/3413.
[14]	L. Lovasz and M. D. Plummer, Matching Theory, volume 121 of North-Holland Mathematics Studies, North-Holland, Amsterdam, 1986.
[15]	S. Pantel, Graph Packing Problems, Master's thesis, Simon Fraser University, Canada, 1993.
[16]	M. D. Penrose, Random parking, sequential adsorption, and the jamming limit, Comm. Math. Phys. 218 (2001), 153-176, doi:10.1007/s002200100387.
[17]	A. Renyi, On a one-dimensional problem concerning random space filling, Magyar Tud. Akad. Mat. Kutatd Int. Kozl. 3 (1958), 109-127.
[18]	N. J. A. Sloane (ed.), The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.
[19]	D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, New Jersey, 1996.
[20] H. S. Wilf, generatingfunctionology, Academic Press, Boston, Massachusetts, 1990.