Monthly Archives: September 2011

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.

Advertisement

Intelligence and How to Get it

Some time ago, I read a book called Intelligence and How to Get it: Why Schools and Cultures Count, written by Richard E. Nisbett.

That’s when I became intelligent.

The book has some very interesting research about intelligence. It basically tries to argue that intelligence is not completely in the genes.

Anyway, while I was reading the book, I started writing up some interesting stuff that I read, and emailing it to some friends. The idea was of course, to archive things so that, you know, when 10 years from now, I start writing my New York Times bestseller, I have access to all the material I was reading.

Now, I realized that the emails can actually be shared online. So here is a pdf that has all the emails in this series. When I was writing those emails, I was not trying to make them into well organized essays. Thus this pdf looks like a collection of various independent thoughts. I have separated those indpendent thoughts with a line made of asterisks.

I did the same thing with some other books that I read too. I will post their respective pdf’s here as well.