Packing graphs: The packing problem solved

Yair Caro ; Raphael Yuster

The electronic journal of combinatorics, Tome 4 (1997) no. 1

Résumé

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.

Détail

DOI : 10.37236/1286

Classification : 05B40, 05C70, 05B30, 51E05, 94C30, 62K05, 62K10
Mots-clés : packing problem, decomposition