抄録
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.
| 本文言語 | English |
|---|---|
| ページ（範囲） | 123-132 |
| ページ数 | 10 |
| ジャーナル | Lecture Notes in Computer Science |
| 巻 | 3330 |
| DOI | |
| 出版ステータス | Published - 2005 |
| 外部発表 | はい |
| イベント | Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003 - Bandung, Indonesia 継続期間: 2003 9月 13 → 2003 9月 16 |
ASJC Scopus subject areas
- 理論的コンピュータサイエンス
- コンピュータ サイエンス（全般）