Residue as a Lower Bound

Residue is a good – maybe the best – lower bound for the independence number. But, the data shows, as n gets larger, its success in exactly predicting the independence number decreases.We need more good efficiently computable lower bounds. I’ve asked Grafitti.pc for help!

Here’s the Survey data:

alpha for 6 out of 8 graphs of order 6 were predicted by residue.

alpha for 38 out of 88 graphs of order 7 were predicted by residue.

alpha for 411 out of 2079 graphs of order 8 were predicted by residue.

alpha for 11620 out of 76783 graphs of order 9 were predicted by residue.

alpha for 501793 out of 5005243 graphs of order 10 were predicted by residue.

Patrick’s INP “survey” function currently tests connected graphs with minimum degree at least 3 and maximum degree no more than n-2 (graphs with \delta<3 or \Delta=n-1 are reducible). These are the graphs reported on above.

 

Advertisements

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