Originators: Odile Favaron et al. (presented by Michael Barrus - REGS 2010)
Definitions: Let d be a graphic list (the degree list of a simple graph). The (Havel-Hakimi) residue r(d) is found by iteratively deleting the largest entry in d and subtracting 1 from each of that many largest remaining entries. When d is graphic, this eventually produces a list in which every entry is zero, and the residue is the number of zeros in that list (it equals the number of vertices minus the number of steps in the process). The annihilation number a(d) is the maximum k such that the sum of the smallest k degrees in d is no more than the sum of the rest of the degrees.
Background: The Havel-Hakimi reduction process provides a realization of d: begin with r(d) isolated vertices (realizing the list of zeros at the end of the process) and iteratively add one vertex at a time, making it adjacent to vertices with appropriate degrees so that after adding j vertices the graph realizes the list that is j steps before the final list in the Havel-Hakimi process. A graph G produced in this way has indpendence number at least r(d), since no edge is ever joins two of the r(d) original vertices.
Favaron et al. [F] proved the stronger statement that for any graph
G, the degree sequence d(G) satisfies
r(d(G)) ≤ α(G). (They also showed
that this lower bound on α(G) is always at least as large
as the well-known Caro-Wei bound α(G) ≥
∑v∈V(G) (d(v)+1)-1.)
The proof of Favaron et al. was long and technical; simpler
proofs were given by Griggs and Kleitman [GK] and by Triesch [T].
Though r(d(G)) is often the best possible lower bound on
α(G) in terms of the degree list, equality does not always
hold, even when all realizations of a the list are considered. For example, the
list (4,4,4,4,4,4,4,4,4) has residue 2, but inspection shows that every
4-regular graph on nine vertices has independence number at least 3.
The Havel-Hakimi process also tests whether a list d is graphic; if
d' is the list produced after one reduction step of the process, then
d is graphic if and only if d' is graphic. Kleitman and Wang
[KW] showed that if d' is formed by removing any term
dk from the list and reducing the largest
dk remaining terms by 1, then again d is graphic if
and only if d' is graphic. Such a reduction is called laying off
dk from d.
In contrast to the residue, the annihilation number was introduced by Pepper in
[P] and is easily seen to be an upper bound on the independence number
of any graph with degree list d.
Problem 1: Characterize graphs G for which α(G) = r(d(G)).
Problem 2: Characterize graphic lists d for which there exists G such that d(G)=d and α(G) = r(d).
Comments: Nelson and Radcliffe [NR] showed that for any semi-regular graphic list d (i.e., a list where the maximum and minimum terms differ by at most 1), the minimum independence number among realizations of d is either r(d) or r(d)+1, and they characterized the semi-regular graphic lists corresponding to each of these two values of the independence number.
Conjecture 3 (posed in REGS discussion): Using the terminology of Kleitman and Wang, if one iteratively lays off terms from a graphic list d until only a list of 0's remains, then the number of 0's is at most the residue of d.
Problem 4: (posed by Barrus) Characterize the graphic lists d for which r(d) = a(d).
Comments: Answering Problem 4 yields a partial answer to Problems 1 and 2, since for such a graphic list d, every graph G with degree sequence d satisfies α(G) = r(d(G)). Larson and Pepper [LP] gave a structural characterization of graphs G for which α(G) = a(d(G)).
References:
[F] O. Favaron, M. Mahéo and J. Saclé, On the residue of a graph. J. Graph Theory 15 (1991), 39--64.
[GK] J.R. Griggs and D.J. Kleitman, Independence and the Havel-Hakimi residue. Graph theory and applications (Hakone, 1990). Discrete Math. 127 (1994), 209--212.
[KW] D.J. Kleitman and D.L. Wang, Algorithm for constructing graphs and digraphs with given valences and factors. Discrete Math. 6 (1973), 79--88.
[LP] C.E. Larson and R. Pepper, Graphs with equal independence and annihilation numbers, preprint.
[NR] P. Nelson and A.J. Radcliffe, Semi-regular graphs of minimum independence number. Discrete Math. 275 (2004), 237--263.
[P] R. Pepper, Binding Independence, Ph.D. Dissertation, University of Houston, Houston, TX, 2004.
[T] E. Triesch, Degree sequences of graphs and dominance order. J. Graph Theory 22 (1996), no. 1, 89--93.