My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 14th, 2010, 06: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.
butabi is offline  
 
October 14th, 2010, 06: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?
cknapp is offline  
October 14th, 2010, 07: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!
butabi is offline  
October 14th, 2010, 10: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.
cknapp is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 r-soy Physics 0 June 2nd, 2013 03:14 AM
Hamiltonian graphs Solarmew Applied Math 2 December 25th, 2012 03:30 PM
Hamiltonian graphs Kramer Applied Math 0 September 20th, 2012 10:33 AM
Hamiltonian Paths and Hamiltonian Circuits eulerrules1 Computer Science 1 December 28th, 2011 12:29 PM
transformation of an Hamiltonian plocq Calculus 0 November 27th, 2011 04:46 AM





Copyright © 2017 My Math Forum. All rights reserved.