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 -