Results 1 to 3 of 3

Math Help - Hamiltonian Graphs

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Italy
    Posts
    7

    Hamiltonian Graphs

    Prove or disprove: There exists an integer k such that every k-connected graph is hamiltonian.

    I am quite sure that it is not true but am having difficulty showing this
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Hamiltonian Graphs

    Consider complete bipartite graphs. When are they k-connected? When are they Hamiltonian?

    ASIDE: These graphs are wonderful in graph theory. Other than complete graphs, my memory is that they show up more than any other class of graphs. They seem to often show up in theorems as "...is less than or equal to ... with equality holding only for complete bipartite graphs." They're complicated enough to be non-trivial, but simple enough to serve as concrete COMPUTABLE examples when examining a great many definitions and theorems. I'd advise keeping them as a "stock example" to make concrete the various definitions and theorems you encounter.
    Last edited by johnsomeone; September 25th 2012 at 04:30 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Italy
    Posts
    7

    Re: Hamiltonian Graphs

    Yes works very well, I understand. Very useful construction. Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hamiltonian Graphs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 25th 2012, 02:10 AM
  2. Hamiltonian Graph help
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: June 6th 2011, 03:54 AM
  3. If T is a tree, how can T^2 be hamiltonian?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 16th 2009, 10:24 PM
  4. hamiltonian graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 30th 2009, 11:15 PM
  5. Hamiltonian regular graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 8th 2006, 08:41 PM

Search Tags


/mathhelpforum @mathhelpforum