Need tight lower bound for independence number of order 10 graph

Question

The independence number of a graph is the cardinality of a maximum set of vertices which are pairwise non-adjacent. It is an NP-hard graph invariant.

There are a variety of ways to efficiently reduce the calculation of the independence number, for instance, if the graph has a simplicial vertex, there is a maximum independent set which contains it (these can be identified efficiently and then it and its neighbors can be removed). There are a variety of graph classes, for instance, claw-free graphs, where it is known that the independence number can be computed efficiently. There are a variety of efficiently computable upper and lower bounds for the independence number of a graph including, respectively, Lovasz's theta function and the residue.

The graph I?bbrr[ko (in B. McKays Graph-6 notation, picture below) has independence number 4. It is the smallest graph such that, using the theory of the independence number of a graph, can not be efficiently reduced, nor belongs to a class where the independence number can be efficiently computed, nor whose value can be predicted from known efficiently computable upper and lower bounds.

In this case, I know the independence number is 4. Lovasz's theta function upper bound gives the exact value of the independence number - but no lower bound that I know of gives the correct value of 4 - no lower bound that I am aware of gives a better value than 3. Would anyone know a lower bound for the independence number of a graph that gives the value 4 for graph I?bbrr[ko ?

I am trying to see how far the existing theory for the efficient computation of the independence number of a graph can be taken - and then find examples that will motivate new theory.

A drawing of the graph can be found here.

Answer 1

A simple method will be to run a greedy algorithm for finding an independent set: recursively choose a vertex of the least degree (and least index), add it to the set, and remove it and all its neighbors from the graph.

I'm not sure if that's what you mean by a method, but it works for the mentioned example.

Answer 2

A greedy algorithm gives a lower bound, often useful, but isn't a graph invariant (to be an invariant the number must be independent of graph representation - any greedy algorithm is dependent on the choice of vertex order/labels). You could make it into an invariant by, for instance, defining it to equal the largest possible value of all possible ways the heuristic can be implemented. For a greedy choosing of vertices of minimum (or maximum, etc) degree vertices, there will generally be an exponential number of ways to proceed - this invariant won't be efficiently computable.

I get 2 when I calculate Murphy's bound. I wasn't previously aware of it. Thanks.

I get 3 when I use the following lower bound of Fajtlowicz. Choose any vertex v. Let O(v) be the set of vertices at odd distance from v. Let OH(v) be the set of edges in the graph induced on O(v). Then, it can be argued, that the independence number of the parent graph is at least |O(v)|-|OH(v)|. Then take the max over all the vertices. Each v calculation requires a calculation of the corresponding distances to the other vertices. This can be done efficiently. To get the max, repeat n times, which is still efficient.

The properties this graph I?bbrr[ko has includes that it is claw-free, any optimum of the relaxed vertex packing IP has only 1/2's in the solution, it has no simplicial vertices, no magnets, isn't perfect, and it is almost Konig-Egervary (it is possible to remove a single vertex so that the resulting graph has equal covering and matching numbers).