# 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$.

## 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

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 façade, 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