On r-regular subgraphs with hamiltonian cycles in graphs with many edges

Abstract

In this paper, we prove that for 0 < β < 1 (2r + 1) and sufficiently large n, every graph G with n vertices and at least n2-β edges contains a subgraph G′ with at least n2-2β 26 edges, such that any t disjoint edges in G' lie together on an r-regular subgraph with at most 2rt vertices. Furthermore, the r-regular subgraph has a Hamiltonian cycle that contains all the t disjoint edges. © 2014 Pushpa Publishing House, Allahabad, India.