2
$\begingroup$

As I understand a graph has a Hamilton Circuit if

  • It has $n \ge 3$ vertexes
  • degree of every vertex is at least $n/2$
  • $\deg u + \deg v \ge n$ for every pair of nonadjacent vertices $u$ and $v$ in the graph

I can't seem to find a concrete set of properties for deciding if a graph has a Hamilton Path. Can anyone help me out? Please add some references/sources :)

  • 0
    You're stating Ore's theorem (but your second condition is not needed): http://en.wikipedia.org/wiki/Ore_theorem2011-07-28

3 Answers 3

1

If a graph has a Hamilton circuit C what happens if you delete an edge from this Hamilton circuit C?

1

A number of sufficient conditions can be found in this thesis of Landon Jennings, among them Chvátal’s condition: if $d_1 \le d_2 \le \dots \le d_n$ are the degrees of $G$, and for $1 \le k \le n/2$ either $d_k \ge k$ or $d_{n+1-k} \ge n-k$, then $G$ has a Hamilton path. The main result of the thesis is the following. Let $G$ be a connected graph with degree sequence $d_1 \le d_2 \le \dots \le d_n$, and let $A(G)$ be the largest integer $k$ such that $\sum\limits_{i=1}^k d_k \le |E(G)|$; if $d_2 \ge A(G)-1$, then $G$ contains a Hamilton path. This test detects some graphs with Hamilton paths not detected by Chvátal’s condition. Some of the references may also be useful.

0

As stated above, all graphs that contain hamiltonian cycles contain hamiltonian paths, however, this does not capture all graphs that have paths but not cycles. As a simple example consider $P_n$. Also, any connected graph, not isomorphic to $C_n$ where each vertex sits on 1 cycle contains a hamiltonian path but not a hamiltonian cycle. Finally, a connected graph that contains a spanning tree with 2 and only 2 vertices of degree 1 has a hamiltonian path but not a hamiltonian cycle.