{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:44:25Z","timestamp":1753893865243,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Let $G$ and $H$ be graphs. We say that $P$ is an $H$-packing of $G$ if $P$ is a set of edge-disjoint copies of $H$ in $G$. An $H$-packing $P$ is maximal if there is no other $H$-packing of $G$ that properly contains P. Packings of maximum cardinality have been studied intensively, with several recent breakthrough results. Here, we consider minimum cardinality maximal packings. An $H$-packing $P$ is called clumsy if it is maximal of minimum size. Let $\\mathrm{cl}(G,H)$ be the size of a clumsy $H$-packing of $G$. We provide nontrivial bounds for $\\mathrm{cl}(G,H)$, and in many cases asymptotically determine $\\mathrm{cl}(G,H)$ for some generic classes of graphs G such as $K_n$ (the complete\u00a0graph), $Q_n$ (the cube graph), as well as square, triangular, and\u00a0hexagonal grids.\u00a0We asymptotically determine $\\mathrm{cl}(K_n,H)$ for every fixed non-empty graph $H$. In particular, we prove that\u00a0\r\n$$\\mathrm{cl}(K_n, H) = \\frac{\\binom{n}{2}- \\mathrm{ex}(n,H)}{|E(H)|}+o(\\mathrm{ex}(n,H)),$$where $ex(n,H)$ is the extremal number of $H$.\r\nA related natural parameter is $\\mathrm{cov}(G,H)$, that is the smallest number of copies of $H$ in $G$ (not necessarily edge-disjoint) whose removal from $G$ results in an $H$-free graph. While clearly $\\mathrm{cov}(G,H) \\leqslant\\mathrm{cl}(G,H)$, all of our lower bounds for $\\mathrm{cl}(G,H)$ apply to $\\mathrm{cov}(G,H)$ as well.<\/jats:p>","DOI":"10.37236\/7942","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T02:13:30Z","timestamp":1578622410000},"source":"Crossref","is-referenced-by-count":0,"title":["Clumsy Packings of Graphs"],"prefix":"10.37236","volume":"26","author":[{"given":"Maria","family":"Axenovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anika","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2019,6,21]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i2p39\/7854","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i2p39\/7854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T23:12:12Z","timestamp":1579216332000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v26i2p39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,21]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,4,5]]}},"URL":"https:\/\/doi.org\/10.37236\/7942","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2019,6,21]]},"article-number":"P2.39"}}