Block allocation of a sequential resource - Došlić, Tomislav (Ars mathematica contemporanea, 2019)
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 ?$P_m$?-packings. We enumerate maximal ?$P_m$?-packings of ?$P_n$? 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: maksimalno pakiranje; maksimalno prirejanje; maximal matching; maximal packing