And the Odd Levels…

Ryan Pepper points out that, for the “rocket” graph F?q`o, iterating the lower bounds currently in the program over the Odd Levels (with respect to the individual vertices) would yield the independence number of this graph. In fact, the independence number of F?q`o is 4 and the Odd Levels with respect to vertex 5 yield an empty graph on 4 vertices.

Running now and iterating over both Even and Odd levels yields the following graph. The independence number here is 4, and the best you can get from the Even over the Odd levels is 3. So we need to add a new general lower bound.

The critical independence number alpha_c here is 4, so we can add that to this investigation of “lower bound strategy”. Its not in the general program at the moment – as graphs with non-empty KE-parts (which have non-empty critical independent sets) are identified and reduced – so by the time bounds are calculated, the considered graphs have alpha_c = 0.


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