1
$\begingroup$

Given simple graph G(V,E) we have to make it hamiltonian. Bondy and Chvatal theorem states that : Given a graph G with n vertices, the closure cl(G) is uniquely constructed from G by successively adding for all nonadjacent pairs of vertices u and v with degree(v) + degree(u) ≥ n the new edge uv.(from wikipedia)

Now consider tree ( which is also simple graph ) n=6

1<->2 2<->3 3<->4 4<->5 5<->6 

And now we realise that we can't get any two verticles(non adjacent) which sums of degrees is ≥ n.

Am i missing something? Seems like quite powerful theorem, but i don't get it.. fully.

Any help will be appreciated.

Chris

  • 0
    Hmm, but it doesn't make hamiltonian cycle. Am i right?2011-10-15

1 Answers 1

3

What the theorem you have in mind says is that: A graph has a hamiltonian circuit (HC) if and only if its "Bondy-Chvatal" closure is Hamiltonian. In the example you cite one cannot add any edges. The graph you start with has no HC and no edges get added so it remains without an HC. What sometimes happens is that one can not easily see if the graph one started with has an HC, but, say after computing the Bondy-Chvatal closure one gets a complete graph. Now the complete graph has an HC so the theorem above tells one that the original graph, where it was not clear if there was an HC or not, has to have an HC.

  • 0
    @Chris I think you are asking about the Hamiltonian completion problem. http://en.wikipedia.org/wiki/Hamiltonian_completion which is "hard" to solve.2011-10-16