Hamiltonian Graphs: Paths, Cycles, Criteria, and Complexity

All flashcards

Hamiltonian-connected graph

A graph with a Hamiltonian path between every pair of distinct vertices.

Hamiltonian decomposition

A partition of a graph's edges into Hamiltonian circuits.

Dirac's theorem

A simple graph on $n\ge 3$ vertices is Hamiltonian if every vertex has degree at least $n/2$.

Ore's theorem

A simple graph on $n\ge 3$ vertices is Hamiltonian if every nonadjacent pair has degree sum at least $n$.

Bondy–Chvátal closure

The graph formed by repeatedly adding eligible nonadjacent edges whose endpoint degrees sum to at least the vertex count.

Quiz questions

1. For a simple undirected graph with $n\ge 3$ vertices, what degree condition guarantees Hamiltonicity by Dirac's theorem?Answer: Every vertex has degree at least $n/2$.
2. According to Ore's theorem, what condition on nonadjacent vertices guarantees that a simple graph with $n\ge 3$ vertices is Hamiltonian?Answer: Each nonadjacent pair has degree sum at least $n$.
3. Why can Bondy–Chvátal closure add an edge between nonadjacent vertices whose degree sum is at least the graph's vertex count?Answer: Adding that edge preserves whether the graph is Hamiltonian.
4. For a tournament with more than two vertices, when is it Hamiltonian?Answer: Exactly when it is strongly connected.
5. What does NP-completeness imply for Hamiltonian path and cycle decision problems?Answer: They are in NP and NP-hard; no polynomial-time algorithm is known for all instances.