solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看72次
Clumsy packings of graphs. (arXiv:1807.05041v1 [math.CO])
来源于:arXiv
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 $$ cl(K_n, H) = \frac{\binom{n}{2}-
ex(n,H)}{|E(H)|}+o(ex(n,H)),$$ where $ex(n,H)$ is the extremal number of $H$. A
related natural parameter i 查看全文>>