The next difficult graph

We’re slowly adding \alpha-properties and \alpha-bounds. After adding the property of being almost-edge-KE, the program popped out the following graph, “difficult” with respect to the fledgling theory:

If you remove vertices 5 and 7, you get a KE graph. It can be argued that, if you remove a pair of vertices from a graph G and get a KE graph, then either G has a non-empty KE part (and the problem of calculating independence can be efficiently reduced to that of a smaller graph or, if n=2k+1, alpha=k, and if n=2k, alpha=k-1. So again the program is suggesting how to extend the theory. In this case, the programmed bounds are rather far apart. alpha=3 here, whereas the Cvetkovic upper bound is 5, and the residue lower bound is 2.

Adding this property, we find that the independence number of all graphs through order 8 can be computed efficiently. Here’s the next difficult graph:

It has a degree 2 vertex – which is foldable. And so we know the next property to add.


Leave a Reply

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

You are commenting using your 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