Clumsy packings of graphs

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 clumsy if it is maximal of minimum size. Let

c l (G, H)

be the size of a clumsy

H

-packing of

G

. We provide nontrivial bounds for

c l (G, H)

, and in many cases asymptotically determine

c l (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

c l (K_{n}, H)

for every fixed non-empty graph

H

. In particular, we prove that

cl(K_n, H) = frac{�inom{n}{2}- ex(n,H)}{|E(H)|}+o(ex(n,H)),

where

e x (n, H)

is the extremal number of

H

. A related natural parameter is

c o v (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

c o v (G, H) l e c l (G, H)

, all of our lower bounds for

c l (G, H)

apply to

c o v (G, H)

as well.

Review text

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.

Recommendations

Cites work

This page was built for publication: Clumsy packings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2001970)