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!


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