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.

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
PDF BibTeX Cite
Full Text: EMIS EuDML