TY - JOUR

T1 - Packings in dense regular graphs

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2005/5/1

Y1 - 2005/5/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=18844431375&partnerID=8YFLogxK

U2 - 10.1017/S0963548304006406

DO - 10.1017/S0963548304006406

M3 - Article

SN - 0963-5483

VL - 14

SP - 325

EP - 337

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

ER -