The Residue, defined by Fajtlowicz as the number of zeros remaining at termination of the Havel-Hakimi process applied to the degree sequence of a graph, is a well known lower bound on the independence number. The problem of characterizing the case of equality has been open since the early-90's.
Several partial results are known. If G is complete OR bi-complete (vertices can be partitioned into two cliques) OR split (vertices can be partitioned into an independent set and a clique), then independence number equals residue.
Of course, C5 is none of these things and yet has independence equal to residue.
Since residue depends only on degree sequence, and there can be many different graphs realizing same sequence, Triesch asks (1996) about the gap between the minimum independence number over all realizations of a graphic sequence D and the residue of D (this question was reiterated by Barrus, apparently unaware of Triesch's question). Triesch also gives an example of a sequence (nine 4's) such that every graphic realization has independence number at least 3 but residue is only 2. Barrus points out that many uni-graphs will have independence equal residue (graphs whose degree sequences have only one realization). He additionally points out that graphs with property that each step of Maxine algorithm (named by Fajtlowicz) mimics the corresponding step of Havel-Hakimi process, will have independence equal to residue.
I am also interested in the solution of this problem. A related URL is found here: http://www.math.illinois.edu/~dwest/regs/hhresidue.html. In particular, it seems hard to characterize those degree sequences whose residue equals the minimum of independence numbers of all realizations of the degree sequence.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs