Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :)

share|improve this question
    
Note that these conditions are sufficient, but not necessary. A regular hexagon fails the second two, but has a Hamiltonian path. –  Ross Millikan Jul 27 '11 at 22:02
    
You're stating Ore's theorem (but your second condition is not needed): en.wikipedia.org/wiki/Ore_theorem –  Justin W Smith Jul 28 '11 at 4:40

3 Answers 3

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.