Clumsy packings of graphs

zbMATH Open1416.05221arXiv1807.05041MaRDI QIDQ2001970FDOQ2001970

Maria Axenovich, Anika Kaufmann (Kaplan), Raphael Yuster

Publication date: 11 July 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1807.05041

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)

Cites Work

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

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)