Packings in dense regular graphs

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

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.

Details

Original languageEnglish
Pages (from-to)325-337
Number of pages13
JournalCombinatorics, Probability and Computing
Volume14
Publication statusPublished - 1 May 2005