Packing Graphs: The Packing Problem Solved

Abstract

For every fixed graph $H$, we determine the $H$-packing number of $K_n$, for all $n > n_0(H)$. We prove that if $h$ is the number of edges of $H$, and $gcd(H)=d$ is the greatest common divisor of the degrees of $H$, then there exists $n_0=n_0(H)$, such that for all $n > n_0$, $$ P(H,K_n)=\lfloor {{dn}\over{2h}} \lfloor {{n-1}\over{d}} \rfloor \rfloor, $$ unless $n = 1 \bmod d$ and $n(n-1)/d = b \bmod (2h/d)$ where $1 \leq b \leq d$, in which case $$ P(H,K_n)=\lfloor {{dn}\over{2h}} \lfloor {{n-1}\over{d}} \rfloor \rfloor - 1. $$ Our main tool in proving this result is the deep decomposition result of Gustavsson.