"A Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once."
Hamiltonian graphs have a circuit that visits every vertex exactly once. They are often used in the study of optimization problems.
Graph theory: Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
Connected components: A connected component of a graph is a subset of vertices in which there is a path connecting any two vertices.
Degree of a vertex: The degree of a vertex in a graph is the number of edges incident on the vertex.
Hamiltonian path: A Hamiltonian path in a graph is a path that visits each vertex exactly once.
Hamiltonian cycle: A Hamiltonian cycle in a graph is a cycle that visits each vertex exactly once.
Cycle notation: Cycle notation is a way of representing a permutation as a product of disjoint cycles.
Eulerian graph: An Eulerian graph is a graph in which there exists a cycle that visits every edge exactly once.
Dirac's theorem: Dirac's theorem states that if a graph has n vertices, n≥3, and the degree of each vertex is at least n/2, then the graph contains a Hamiltonian cycle.
Ore's theorem: Ore's theorem states that if a graph has n vertices, n≥3, and the sum of the degree of any two non-adjacent vertices is at least n, then the graph contains a Hamiltonian cycle.
Necessary and sufficient conditions: A condition is necessary for a graph to be Hamiltonian if every Hamiltonian graph satisfies it, and it is sufficient if every graph that satisfies it is Hamiltonian.
Bondy-Chvatal theorem: Bondy and Chvatal proved that a graph is Hamiltonian if and only if its closure is Hamiltonian, where the closure of a graph is obtained by adding an edge between every pair of non-adjacent vertices whose degrees sum to at least n.
Hamiltonian graphs in the real world: Hamiltonian graphs have applications in physics, computer science, and operations research. Examples include the TSP problem, the design of computer networks, and the study of molecular systems.
Complete Graph: A complete graph is a graph where each pair of vertices is connected by an edge. It is also called a full graph. As every vertex has a direct connection with all the other vertices, it is an example of a Hamiltonian graph.
Cycle Graph: A cycle graph is a graph that consists of a single cycle. It can be viewed as being formed by connecting the first and last vertices of a path graph. Therefore, it is a Hamiltonian graph.
Bipartite Graph: A bipartite graph is a graph that can be divided into two sets of vertices, such that all edges connect a vertex in one set to a vertex in the other set. Bipartite graphs can be Hamiltonian, but not all bipartite graphs are Hamiltonian.
Regular Graph: A regular graph is a graph where all vertices have the same degree. It is possible for a regular graph to be Hamiltonian, but it is not always the case.
Grid Graphs: Grid graphs are a type of regular graph that is formed by arranging vertices in a rectangular grid, where each vertex is connected to its four adjacent vertices. Grid graphs can be Hamiltonian, but they can be difficult to analyze.
Other Graphs: There are many other types of graphs that can be Hamiltonian, including random graphs, planar graphs, and more. However, it can be difficult to identify the Hamiltonicity of these graphs.
"A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once."
"A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path."
"Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete."
"Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the icosian game, now also known as Hamilton's puzzle."
"Hamilton solved this problem using the icosian calculus, an algebraic structure based on roots of unity with many similarities to the quaternions."
"This solution does not generalize to arbitrary graphs."
"Hamiltonian cycles in polyhedra had also been studied a year earlier by Thomas Kirkman."
"Thomas Kirkman, who, in particular, gave an example of a polyhedron without Hamiltonian cycles."
"Knight's cycles and paths in the knight's graph of the chessboard, the knight's tour, had been studied in the 9th century in Indian mathematics by Rudrata."
"Around the same time in Islamic mathematics by al-Adli ar-Rumi."
"In 18th century Europe, knight's tours were published by Abraham de Moivre and Leonhard Euler."
"William Rowan Hamilton invented the icosian game, now also known as Hamilton's puzzle."
"The icosian calculus, an algebraic structure based on roots of unity with many similarities to the quaternions."
"This solution does not generalize to arbitrary graphs."
"Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete."
"A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle."
"Removing any edge from a Hamiltonian cycle produces a Hamiltonian path."
"The icosian calculus has many similarities to the quaternions."
"The quaternions were also invented by Hamilton."