Hamiltonian cycles in maximal planar graphs

Whitney proved long ago that every maximal planar graph with no separating triangles is Hamiltonian. However, the converse is not necessarily true, that is, there exist maximal planar graphs that are hamiltonian and have separating triangles. So what happens when a maximal planar graph has separating triangles? Is there still some condition under which we can say with certainty that it will be Hamiltonian as well?

One theorem of this kind was shown by Jackson and Yu.

Consider a maximal planar graph G with a separating triangle T. G can be decomposed into two graphs G_1 and G_2 such that G_1 \cup G_2 = G and G_1 \cap G_2 = T. If G_1 or G_2 still has separating triangles, then decompose them similarly. Eventually, we will be left with a collection S of maximal planar graphs without any separating triangles. Now, consider a graph whose nodes represent elements of the set S and there is an edge between two nodes if they share a separating traingle in G. Let’s call this graph D. The theorem by Jackson and Yu states that if D has maximum degree 3, then G is Hamiltonian.

This way of decomposing maximal planar graphs has been popular. It was first used by William Cunningham and Jack Edmonds in 1980. They proved several interesting results about the decomposition graph D.

Advertisements

6 thoughts on “Hamiltonian cycles in maximal planar graphs

  1. Hey there! This is kind of off topic but I need some guidance from an established blog.
    Is it difficult to set up your own blog? I’m not very techincal but I can figure things out pretty quick. I’m thinking about creating my own
    but I’m not sure where to start. Do you have any tips or suggestions? With thanks

  2. I almost never leave a response, but after reading through a few of the
    comments here Hamiltonian cycles in maximal planar graphs | Stuff.

    I actually do have a couple of questions for
    you if it’s okay. Is it only me or do some of these remarks look like they are written by brain dead visitors? 😛 And, if you are writing on other social sites, I’d like to keep up with you.
    Could you make a list of every one of all your shared sites like
    your twitter feed, Facebook page or linkedin profile?

  3. Hello! I just would like to offer you a big thumbs
    up for your excellent info you have right here on this post.
    I am returning to your site for more soon.

  4. First of all, I want to point out that dieting and exercises are best methods for fat loss.
    I thought this would turn me into a super-lean machine.
    Sunlight on un-protected skin produces a highly usable form
    of Vitamin D that lasts twice as long in your bloodstream as when you consume it through food or a supplement, but you still
    need caution due to the risk of skin cancer.

  5. The challenge we face when we want to approach people,
    who we believe are of high stature, is that
    all we see is the faade, which is created around them, not the
    real person underneath. This connect on a emotional
    level is what get’s us to divulge to you, share some personal things with you and connect with you on a whole different level, it is that “secret ingredient” that will keep
    us bonded to ONE woman over the long haul. Have you ever dropped a secret valentine through the
    gap in a colleague’s private filing cabinet.

  6. You post very interesting posts here. Your page deserves much more traffic.
    It can go viral if you give it initial boost, i know very useful service that can help
    you, just search in google: svetsern traffic tips

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s