# zbMATH — the first resource for mathematics

Packing graphs: The packing problem solved. (English) Zbl 0885.05052
Electron. J. Comb. 4, No. 1, Research paper R1, 7 p. (1997); printed version J. Comb. 4, No. 1, 1-7 (1997).
Summary: 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)=\Biggl\lfloor \frac{dn}{2h} \biggl\lfloor \frac{n-1}{d} \biggr\rfloor \Biggr\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)=\Biggl\lfloor \frac{dn}{2h} \biggl\lfloor \frac{n-1}{d} \biggr\rfloor \Biggr\rfloor-1.$ Our main tool in proving this result is the deep decomposition result of Gustavsson.

##### MSC:
 05B40 Combinatorial aspects of packing and covering 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05B30 Other designs, configurations 51E05 General block designs in finite geometry 94C30 Applications of design theory to circuits and networks 62K05 Optimal statistical designs 62K10 Statistical block designs
##### Keywords:
packing problem; decomposition
Full Text: