Other designs, configurations (05B30) Combinatorial aspects of packing and covering (05B40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) General block designs in finite geometry (51E05) Optimal statistical designs (62K05) Statistical block designs (62K10) Applications of design theory to circuits and networks (94C30)
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.
- Covering graphs: The covering problem solved
- Packing of graphs and permutations -- a survey
- Packing and decomposition of graphs with trees
- The packing number of the double vertex graph of the path graph
- Orthogonal decomposition and packing of complete graphs
- \(H\)-packing of \(k\)-chromatic graphs
- Intersecting designs
- Clumsy packings of graphs
- On zero-sum spanning trees and zero-sum connectivity
- Asymptotically optimal K_k-packings of dense graphs via fractional K_k-decompositions
- An approximate version of the tree packing conjecture
- Uniform hypergraphs containing no grids
- Combinatorial and computational aspects of graph packing and graph decomposition
- Problems and invariants connected with bicliques and multicliques of graphs
- scientific article; zbMATH DE number 812039 (Why is no real title available?)
- On the packing number of generalized Petersen graphs \(P(n,2)\).
- Leaves for packings with block size four
- Packing copies of Cartesian product of certain classes of paths and cycles into power graphs
- Block allocation of a sequential resource
- Packing cliques in 3‐uniform hypergraphs
- Graph and hypergraph packing
- Completing partial packings of bipartite graphs
- Generalising Fisher's inequality to coverings and packings
- Triangle-free triple systems
- Planar packing of trees and spider trees
This page was built for publication: Packing graphs: The packing problem solved
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1378488)
