Regular factors containing a given hamiltonian cycle

Haruhide Matsuda

doi:10.1007/978-3-540-30540-8_14

Regular factors containing a given hamiltonian cycle

Haruhide Matsuda

Research output: Contribution to journal › Conference article › peer-review

1 Citation (Scopus)

Abstract

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 language	English
Pages (from-to)	123-132
Number of pages	10
Journal	Lecture Notes in Computer Science
Volume	3330
DOIs	https://doi.org/10.1007/978-3-540-30540-8_14
Publication status	Published - 2005
Externally published	Yes
Event	Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003 - Bandung, Indonesia Duration: 2003 Sept 13 → 2003 Sept 16

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-30540-8_14

Cite this

@article{2dd18badcebf4913b74cbc6d5b16ed1a,

title = "Regular factors containing a given hamiltonian cycle",

abstract = "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.",

author = "Haruhide Matsuda",

year = "2005",

doi = "10.1007/978-3-540-30540-8_14",

language = "English",

volume = "3330",

pages = "123--132",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

note = "Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003 ; Conference date: 13-09-2003 Through 16-09-2003",

}

TY - JOUR

T1 - Regular factors containing a given hamiltonian cycle

AU - Matsuda, Haruhide

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=23944486377&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23944486377&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30540-8_14

DO - 10.1007/978-3-540-30540-8_14

M3 - Conference article

AN - SCOPUS:23944486377

SN - 0302-9743

VL - 3330

SP - 123

EP - 132

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, IJCCGGT 2003

Y2 - 13 September 2003 through 16 September 2003

ER -

Regular factors containing a given hamiltonian cycle

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this