Regular factors containing a given hamiltonian cycle

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)


Let k ≥ 1 be an integer and let G be a graph having a sufficiently large order n. Suppose that kn is even, the minimum degree of G is at least k + 2, and the degree sum of each pair of nonadjacent vertices in G is at least n+α, where α = 3 for odd k and α = 4 for even k. Then G has a k-factor (i.e. a k-regular spanning subgraph) which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. As a consequence, we have an Ore-type condition for graphs to have a k-factor containing a given Hamiltonian cycle.

Original languageEnglish
Pages (from-to)123-132
Number of pages10
JournalLecture Notes in Computer Science
Publication statusPublished - 2005
Externally publishedYes
EventIndonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003 - Bandung, Indonesia
Duration: 2003 Sept 132003 Sept 16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Regular factors containing a given hamiltonian cycle'. Together they form a unique fingerprint.

Cite this