Article ID Journal Published Year Pages File Type
4649761 Discrete Mathematics 2009 9 Pages PDF
Abstract

Let kk be an integer with k≥2k≥2 and let GG be a graph having sufficiently large order nn. Suppose that knkn is even, the minimum degree of GG is at least kk and max{dG(x),dG(y)}≥(n+α)/2max{dG(x),dG(y)}≥(n+α)/2 for each pair of nonadjacent vertices xx and yy in GG, where α=3α=3 for odd kk and α=4α=4 for even kk. Then GG has a kk-factor (i.e. a kk-regular spanning subgraph) which contains a given Hamiltonian cycle CC if G−E(C)G−E(C) is connected.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,