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.

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

share|improve this question
    
It would seem that the closure of your tree is itself. Is that a problem? –  Gerry Myerson Oct 14 '11 at 21:58
    
Hmm, but it doesn't make hamiltonian cycle. Am i right? –  Chris Oct 15 '11 at 0:22

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
But do you know the method how to make any graph contain HC? I mean in minimum number of additions, because making graph always full is a little pointless. Or am i missing something? –  Chris Oct 15 '11 at 20:03
    
@Chris I think you are asking about the Hamiltonian completion problem. en.wikipedia.org/wiki/Hamiltonian_completion which is "hard" to solve. –  Joseph Malkevitch Oct 16 '11 at 15:52

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.