Clumsy packings of graphs (Q2001970): Difference between revisions
From MaRDI portal
Set profile property. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1807.05041 / rank | |||
Normal rank |
Revision as of 00:46, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Clumsy packings of graphs |
scientific article |
Statements
Clumsy packings of graphs (English)
0 references
11 July 2019
0 references
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.
0 references
maximal \(H\)-packing
0 references