Topic summary
Hamiltonian graph
Extracted from the Wikipedia article Hamiltonian path.
See also
- Barnette's conjecture, an open problem on Hamiltonicity of cubic bipartitepolyhedral graphs
- Eulerian path, a path through all edges in a graph
- Fleischner's theorem, on Hamiltonian squares of graphs
- Gray code
- Grinberg's theorem giving a necessary condition for planar graphs to have a Hamiltonian cycle
- Hamiltonian path problem, the computational problem of finding Hamiltonian paths
- Hypohamiltonian graph, a non-Hamiltonian graph in which every vertex-deleted subgraph is Hamiltonian
- Knight's tour, a Hamiltonian cycle in the knight's graph
- LCF notation for Hamiltonian cubic graphs.
- Lovász conjecture that vertex-transitive graphs are Hamiltonian
- Pancyclic graph, graphs with cycles of all lengths including a Hamiltonian cycle
- Panconnectivity, a strengthening of both pancyclicity and Hamiltonian-connectedness
- Seven Bridges of Königsberg
- Shortness exponent, a numerical measure of how far from Hamiltonian the graphs in a family can be
- Snake-in-the-box, the longest induced path in a hypercube
- Steinhaus–Johnson–Trotter algorithm for finding a Hamiltonian path in a permutohedron
- Subhamiltonian graph, a subgraph of a planar Hamiltonian graph
- Tait's conjecture (now known false) that 3-regular polyhedral graphs are Hamiltonian
- Travelling salesman problem
- Harris graphs, a family of graphs that are tough, Eulerian, and non-Hamiltonian