October 14th, 2010, 05:36 AM  #1 
Member Joined: Sep 2010 Posts: 60 Thanks: 0  Hamiltonian cycle
How many edges should we leave at least from a G complete graph with n vertices, in order to avoid that G contains any Hamiltonian cycle? Any help would be appreciated. Thanks. 
October 14th, 2010, 05:59 AM  #2 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: Hamiltonian cycle
Should that say "At least how many should we remove?" Also, do you want: the minimum number to remove so that there is a graph on n vertices with that many edges removed that has no cycle, or do you want the minimum number removed such that there is no graph on n vertices and that many edges with a cycle? 
October 14th, 2010, 06:27 AM  #3 
Member Joined: Sep 2010 Posts: 60 Thanks: 0  Re: Hamiltonian cycle
Sorry, English is not my mother tongue. At least how many should we remove from a G complete graph with n vertice so that G contains no Hamiltonian cycle? So I want the minimum number to remove so that there is a graph on n vertices with that many edges removed that has no Hamiltonian cycle. Thank you! 
October 14th, 2010, 09:21 AM  #4 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: Hamiltonian cycle
No worries, I figured that was the case. Anyway... we can certainly get a graph with no Hamiltonian Cycle by removing n2: remove all edges except one from a single vertex. I don't think we can do better, but I'm not sure how to prove it... Here's an idea that might or might not work: A Hamiltonian cycle corresponds to an ordering of the vertices (I.e., a bijection f: {0,...,n1})>V(G) ), such that two adjacent vertices in the ordering are adjacent in the graph, and f(0) is adjacent to f(n1). Start with an arbitrary Hamiltonian cycle, and try to show that if you remove less than n2 edges from G, then you can rearrange your vertices to get a new cycle. 

Tags 
cycle, hamiltonian 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
which one is more efficience otto cycle or carnot cycle or d  rsoy  Physics  0  June 2nd, 2013 02:14 AM 
Hamiltonian graphs  Solarmew  Applied Math  2  December 25th, 2012 02:30 PM 
Hamiltonian graphs  Kramer  Applied Math  0  September 20th, 2012 09:33 AM 
Hamiltonian Paths and Hamiltonian Circuits  eulerrules1  Computer Science  1  December 28th, 2011 11:29 AM 
transformation of an Hamiltonian  plocq  Calculus  0  November 27th, 2011 03:46 AM 