Packings in dense regular graphs
Research output: Contribution to journal › Article
Colleges, School and Institutes
We prove that for all alpha,c > 0 and for all bipartite graphs H, all but at most alpha n vertices of every cn-regular graph G whose order n is sufficiently large can be covered by vertex-disjoint copies of H. If the vertex classes of H have different size, then even all but a constant number of vertices of G can be covered. This implies that for all c > 0 and all r >= 4 there exists a constant C such that, in every cn-regular graph G, all but at most C vertices can be covered by vertex-disjoint subdivisions of K-r. We also show that for r = 4, 5 one can take C = 0.
|Number of pages||13|
|Journal||Combinatorics, Probability and Computing|
|Publication status||Published - 1 May 2005|