Clumsy Packings of Graphs

Abstract

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 graph), $Q_n$ (the cube graph), as well as square, triangular, and hexagonal grids. We asymptotically determine $\mathrm{cl}(K_n,H)$ for every fixed non-empty graph $H$. In particular, we prove that 

$$\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$.

A 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.