Let's use the following labeling scheme (in reading order): A through N are the vertices. I would start at B (upper right corner) and go down. Can you see the cycle?
Hi all, love this forum. I need a little bit of help with this question.
I have this graph that I need to prove if it is Hamiltonian or not.
http://imageshack.us/photo/my-images/606/unledzw.png/
I have found that it satisfies the necessary condition that if you take U to be a proper set of the vertices, then the sub graph induced by V\U has at most |U| components.
But I don't how to show if it is Hamiltonian or not. So does it satisfy any sufficient condition? Is this
Thanks in advance for any help given.
Oh yes, thanks Ackbeet and bobak. I must not have been thinking straight. Using your labeling Ackbeet, I get the Hamiltonian cycle to be B,F,E,J,I,M,N,D,C,G,H,L,K,A. And so it has used all vertices once and went from B back to B.
Thanks for your help. Much appreciated.
Thanks Ackbeet.
The pic I posted doesn't work anymore so I uploaded it again here: ImageShack® - Online Photo and Video Hosting
I have another follow up question:
If you have the above graph that is Hamiltonian and take away a vertex and the edges connected to it, is the resulting graph Hamiltonian? I know that it will have a Hamiltonian path but is it Hamiltonian?
So for example, using your labeling Ackbeet, is G \{A} or G\{B} Hamiltonian?
Thanks
I should think that would vary depending on the graph and on which vertex you removed. As for the particular two subgraphs you mentioned, I would need to see them drawn out by themselves to see if I thought they were Hamiltonian.
As for the eccentricity, I would think that you could just run Dijkstra's algorithm from the vertex whose eccentricity you wish to compute, to all the other vertices. The vertex that has the longest "shortest path" will give you the eccentricity. That would be an algorithm, which is good as algorithms go. You could actually do better if you use some fancy implementations of Dijkstra's algorithm. See here for an explanation.
I'm not an expert on graph theory, though I did take one course in it, so I'm afraid that you're rapidly reaching the hazy borders of my knowledge.
Cheers.
Thanks again Ackbeet.
The Graphs of G\{A} and G\{B} are:
G\{A}: ImageShack® - Online Photo and Video Hosting
G\{B}: ImageShack® - Online Photo and Video Hosting
G\{B} could only have a Hamiltonian path so does that mean it is not Hamiltonian? G\{A} could be Hamiltonian, but I can't find a circuit, I always miss one vertex.
Thanks
G has a cycle of length 14, since there are 14 vertices. You take 1 away and you can not make an even cycle. I tired many times to find a Hamiltonian cycle, but always ended up missing 1 vertex. So this seems to confirm my thoughts.
Yes, I am saying G is bipartite, and a property of a bipartite graph is that it does not contain an odd cycle.