Results 1 to 15 of 15

Math Help - Hamiltonian Graph help

  1. #1
    Newbie
    Joined
    Jun 2011
    Posts
    20

    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.
    Last edited by mathgirl1; June 2nd 2011 at 02:58 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2011
    Posts
    20
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Quote Originally Posted by Ackbeet View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2011
    Posts
    20
    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.
    Last edited by mathgirl1; June 3rd 2011 at 11:12 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Quote Originally Posted by mathgirl1 View Post
    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 O(n^{3}) 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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jun 2011
    Posts
    20
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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...
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Quote Originally Posted by Ackbeet View Post
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Quote Originally Posted by Ackbeet View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Quote Originally Posted by mathgirl1 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Quote Originally Posted by Ackbeet View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Quote Originally Posted by mathgirl1 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hamiltonian graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 23rd 2011, 03:35 AM
  2. Replies: 0
    Last Post: April 9th 2011, 08:57 AM
  3. Replies: 1
    Last Post: October 13th 2010, 03:58 AM
  4. Graph Theory Hamiltonian Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2009, 08:41 PM
  5. The Tutte graph is not hamiltonian
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 14th 2009, 02:51 PM

Search Tags


/mathhelpforum @mathhelpforum