# Graphs where the Independence Number equals its Residue

The residue of a graph is the number of zeros that remain after repeated application of the Havel-Hakimi process to the degree sequence of a graph. This invariant can be computed efficiently (it is clearly no worse than O(n^2)). The residue is often the best performing of the known lower bounds for the independence number (alpha) of a graph. Its not great – but the lower bound theory is relatively poor compared to the upper bound theory (and Lovasz’s amazing theta function).

Characterizing graphs where alpha = residue is a theoretical challenge and of practical utility. A recognition algorithm for graphs in this class would expand the class of graphs where the independence number can be computed efficiently. These include, for instance, odd cycles \$C_{2n+1}\$ and the complete bipartite graphs \$K_{n,n}\$.

We are testing the new property-relations version of the program. So we generated some necessary and sufficient conditions for a graph to have this property. First some necessary conditions for graphs where residue = alpha. If a graph is 2-connected and the degree sum of any pair of non-adjacent vertices is at least n, it “is ore” (this is a sufficient condition for a graph to be hamiltonian). “is circular planar”” means outerplanar. “weakly chordal” means no induced cycle of length >= 5.
1.  (has_residue_equals_alpha)->((is_regular)->(is_ore))
2. (has_residue_equals_alpha)->((is_bipartite)->(is_circular_planar))
3. (has_residue_equals_alpha)->((is_regular)->(is_odd_hole_free))
4. (has_residue_equals_alpha)->((is_cartesian_product)->(is_regular))
5. (has_residue_equals_alpha)->((is_line_graph)->(is_weakly_chordal))
6. (has_residue_equals_alpha)->((is_perfect)|(is_eulerian))
Now here are some sufficient conditions for graphs where residue = alpha. “generalized dirac” is the condition that the graph is 2-connected and non-adjacent vertices have at least (2n-1)/3 neighbors. It is also a sufficient condition for hamiltonicity.

1. ((has_perfect_matching)&(is_generalized_dirac))->(has_residue_equals_alpha)
2. ((is_line_graph)&(is_circular_planar))->(has_residue_equals_alpha)
3. (is_chordal)->(has_residue_equals_alpha)
4. ((is_even_hole_free)&(is_eulerian))->(has_residue_equals_alpha)

As always counterexamples would be of interest. They will help the program make better conjectures. Proofs would be of interest too!