A conjectured lower bound for the independence number

Nico and I are running conjectures for lower bounds for the independence number. We are limiting the conjectures to connected graphs where every non-empty independent set X has the property that |N(X)|>|X| (these graphs are the “hardest” graphs in some sense with respect to independence number calculations—if a graph has an independent set X with no more than |X| neighbors, it can be identified in polynomial time and included in a maximum independent set).

Here are the conjectures:

[independence_number(x) >= radius(x), independence_number(x) >= residue(x), independence_number(x) >= minimum(cvetkovic(x), girth(x) – 1)].

The first two are well-known and proved conjectures of Graffiti. The third conjecture is curious. Cvetkovic is the minimum of the non-negative and non-positive eigenvalues of the graph. Cvetkovic proved that this is an upper bound for the independence number. Here it appears in a lower bound. The conjecture is tested for all graphs of order less than 10.

We guess that this conjecture is false—but don’t know a counterexample. We’d love to know one. We can use it to generate better conjectures.




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