We say that a graph G has a perfect H-packing if there exists a set of vertex- disjoint copies of H which cover all the vertices in G. We consider various problems concerning perfect H-packings: Given n; r;D ∈ ℕ, we characterise the edge density threshold that ensures a perfect Kr-packing in any graph G on n vertices and with minimum degree δ(G) ≥ D. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect H-packing. Other related embedding problems are also considered. Indeed, we give a structural result concerning Kr-free graphs that satisfy a certain degree sequence condition.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics