Thread: Hamiltonian Graph help

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.

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?

A graph is Hamiltonion if it contains a cycle passing through all the vertices (this is called a Hamilton cycle ).

Can you see one in your graph ?

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.

That's a much more "circuitous" route (pun intended) than I found. I just did B, F, H, L, N, M, I, G, C, D, E, J, K, A, B. But yours works as well. Good job!

Originally Posted by Ackbeet

That's a much more "circuitous" route (pun intended) than I found. I just did B, F, H, L, N, M, I, G, C, D, E, J, K, A, B. But yours works as well. Good job!

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

Another follow up question: What would be the easiest way to find the eccentricity of each vertex?

Thanks in advance for any help for this question and my question in the post above.

Originally Posted by mathgirl1

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\{A} is definitely not Hamiltonian, because there's no way you can have any cycle that includes vertex B. You do have to have a Hamiltonian cycle/circuit in order for the graph to be Hamiltonian.

G\{B} is less clear. Thinking...

Originally Posted by Ackbeet

G\{A} is definitely not Hamiltonian, because there's no way you can have any cycle that includes vertex B. You do have to have a Hamiltonian cycle/circuit in order for the graph to be Hamiltonian.

G\{B} is less clear. Thinking...

Yeah, sorry I stated my last bit wrong, G\{A} means the degree of B is one so it is not Hamiltonian. But All vertices in G\{B} have at least degree 2.
Thanks

Originally Posted by Ackbeet

G\{B} is less clear. Thinking...

I think I have it. G and G\{B} have chromatic number 2, so it is bipartite. And any bipartite graph does not have any odd cycle's. Thus G\{B} is not Hamiltonian?

Originally Posted by mathgirl1

I think I have it. G and G\{B} have chromatic number 2, so it is bipartite. And any bipartite graph does not have any odd cycle's. Thus G\{B} is not Hamiltonian?

I'm confused. This argument has to fail for G, because G is Hamiltonian. Are you claiming that G has chromatic number 2 and is bipartite? I suppose that a Hamiltonian cycle for G is an even cycle, since there are an even number of vertices. Is that where it fails?

Originally Posted by Ackbeet

I'm confused. This argument has to fail for G, because G is Hamiltonian. Are you claiming that G has chromatic number 2 and is bipartite? I suppose that a Hamiltonian cycle for G is an even cycle, since there are an even number of vertices. Is that where it fails?

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.

Originally Posted by mathgirl1

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.

Makes sense. I think you've got a proof, then. Delete a vertex from a bipartite graph, and you still have a bipartite graph. Hence, G\{A} and G\{B} are not Hamiltonian, since a Hamiltonian cycle would have to be odd.