Clumsy packings of graphs

MaRDI QIDQ2001970zbMATH OpenFDO

Authors Anika Kaufmann (Kaplan), Raphael Yuster, Maria Axenovich

Publication date 11 July 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.05041, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p39

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

zbMATH Keywords

maximal \(H\)-packing

Mathematics Subject Classification ID

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

Recommendations

• Near packings of graphs
• Near packings of two graphs
• Packing graphs: The packing problem solved
• Covering and packing in graphs. V. Mispacking subcubes in hypercubes
• Solution of two problems of P. Erdős concerning Hamiltonian cycles

Cites work

• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Clumsy packing of dominoes
• Edge-decompositions of graphs with high minimum degree
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Near perfect coverings in graphs and hypergraphs
• Nearly perfect matchings in regular simple hypergraphs
• On a problem of K. Zarankiewicz
• Packing and decomposition of graphs with trees
• Packing graphs: The packing problem solved
• Packing polyominoes clumsily
• Polarities and \(2k\)-cycle-free graphs
• Ramanujan graphs
• Some Turán type results on the hypercube
• Turán’s Theorem in the Hypercube

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)