A \([k,k+1]\)-factor containing a given Hamiltonian cycle (Q5906318)
From MaRDI portal
scientific article; zbMATH DE number 1247858
Language | Label | Description | Also known as |
---|---|---|---|
English | A \([k,k+1]\)-factor containing a given Hamiltonian cycle |
scientific article; zbMATH DE number 1247858 |
Statements
A \([k,k+1]\)-factor containing a given Hamiltonian cycle (English)
0 references
2 February 1999
0 references
An \([a,b]\)-factor of a graph \(G\) is a spanning subgraph \(F\) such that the degree of each vertex of \(F\) is in the interval \([a, b]\). For a positive integer \(k \geq 2\), let \(G\) be a graph of order \(n\) with \(n \geq 8k - 16\) if \(n\) is even and \(n \geq 6k - 13\) if \(n\) is odd. If the sum of the degrees of each pair of nonadjacent vertices of \(G\) is at least \(n\), then \(G\) contains a \([k, k+1]\)-factor. Examples are given to show that the results are sharp for both \(n\) odd and \(n\) even.
0 references
Hamiltonian cycle
0 references
\([|k,k+1]\)-factor
0 references
Ore degree condition
0 references