My Math Forum Hamiltonian cycle

 Applied Math Applied Math Forum

 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 n-2: 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,...,n-1})->V(G) ), such that two adjacent vertices in the ordering are adjacent in the graph, and f(0) is adjacent to f(n-1). Start with an arbitrary Hamiltonian cycle, and try to show that if you remove less than n-2 edges from G, then you can rearrange your vertices to get a new cycle.

 Tags cycle, hamiltonian

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post r-soy Physics 0 June 2nd, 2013 02:14 AM Solarmew Applied Math 2 December 25th, 2012 02:30 PM Kramer Applied Math 0 September 20th, 2012 09:33 AM eulerrules1 Computer Science 1 December 28th, 2011 11:29 AM plocq Calculus 0 November 27th, 2011 03:46 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top