Clumsy packings of graphs (Q2001970)

Summary: 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 \textit{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 \(\text{cl}(G,H)\) be the size of a clumsy \(H\)-packing of \(G\). We provide nontrivial bounds for \(\text{cl}(G,H)\), and in many cases asymptotically determine \(\text{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 \(\text{cl}(K_n,H)\) for every fixed non-empty graph \(H\). In particular, we prove that \[ \text{cl}(K_n, H) = \frac{\binom{n}{2}- \text{ex}(n,H)}{|E(H)|}+o(\text{ex}(n,H)),\] where \(\text{ex}(n,H)\) is the extremal number of \(H\). A related natural parameter is \(\text{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 \(\text{cov}(G,H) \leqslant\text{cl}(G,H)\), all of our lower bounds for \(\text{cl}(G,H)\) apply to \(\text{cov}(G,H)\) as well.