Hamiltonian cycle concept
E455347
The Hamiltonian cycle concept is a fundamental idea in graph theory describing a cycle that visits each vertex of a graph exactly once and returns to the starting point.
Observed surface forms (3)
| Surface form | Occurrences |
|---|---|
| Hamiltonian cycle | 0 |
| Hamiltonian cycle problem | 0 |
| Hamiltonian path problem | 1 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
cycle in a graph
ⓘ
decision problem ⓘ graph theory concept ⓘ |
| alsoCalled |
Hamiltonian circuit
ⓘ
Hamiltonian tour ⓘ |
| appearsIn |
network design
ⓘ
polyhedral combinatorics ⓘ routing problems ⓘ |
| appliesTo |
directed graphs
ⓘ
undirected graphs ⓘ |
| asks | whether a given graph contains a Hamiltonian cycle ⓘ |
| complexityClass | NP-complete ⓘ |
| complexityOfRecognition | NP-complete in general graphs ⓘ |
| contrastedWith | Eulerian cycle NERFINISHED ⓘ |
| decisionProblem | Hamiltonian cycle problem ⓘ |
| definition | a cycle in a graph that visits each vertex exactly once and returns to the starting vertex ⓘ |
| edgeConstraint | uses only edges of the graph ⓘ |
| exampleGraphWith | complete graph Kn for n ≥ 3 ⓘ |
| exampleGraphWithout |
star graph Kn,1 for n ≥ 2
ⓘ
tree with more than two vertices ⓘ |
| existsIn | Hamiltonian graph ⓘ |
| field | graph theory ⓘ |
| generalizedTo | infinite graphs with appropriate definitions ⓘ |
| historicalOrigin | Icosian game of William Rowan Hamilton NERFINISHED ⓘ |
| isSubgraphOf | underlying graph ⓘ |
| length | number of vertices in the graph ⓘ |
| namedAfter | William Rowan Hamilton NERFINISHED ⓘ |
| property | spans all vertices of the graph ⓘ |
| relatedConcept |
Eulerian cycle
ⓘ
Hamiltonian path NERFINISHED ⓘ |
| representation | sequence of vertices forming a simple cycle ⓘ |
| requires |
finite graph in standard definition
ⓘ
graph to be connected for existence ⓘ |
| returnsTo | starting vertex ⓘ |
| specialCaseOf | cycle ⓘ |
| studiedIn |
algorithmic graph theory
ⓘ
extremal graph theory ⓘ |
| sufficientCondition |
Bondy–Chvátal theorem
NERFINISHED
ⓘ
Chvátal–Erdős theorem NERFINISHED ⓘ Dirac's theorem NERFINISHED ⓘ Ore's theorem NERFINISHED ⓘ |
| tractableOn |
graphs of bounded treewidth
ⓘ
tournaments ⓘ |
| usedIn |
combinatorial optimization
ⓘ
computational complexity theory NERFINISHED ⓘ traveling salesman problem NERFINISHED ⓘ |
| vertexConstraint | includes every vertex of the graph ⓘ |
| visitsEachVertex | exactly once ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Hamiltonian path problem