ON THE RESIDUE OF A GRAPH

The residue R of a simple graph G of degree sequence S: d1 greater-than-or-equal-to d2 greater-than-or-equal-to ... greater-than-or-equal-to d(n) is the number of zeros obtained by the iterative process consisting of deleting the first term d1 of S, subtracting 1 from the d1 following ones, and sorting down the new sequence. The depth is the number n - R of steps in this algorithm. We prove here some conjectures given by the computer program GRAFFITI, in particular, R less-than-or-equal-to alpha, where alpha is the independence number of G. If G is a tree: mu less-than-or-equal-to R, where mu is the mean distance of G.