Maxine: A greedy algorithm we studied, Maxine, uses this graph property by iteratively deleting maximum degree vertices until isolates are reached. Maxine terminates with an independent set of vertices which has cardinality at most the independence number The Maxine cardinality represents a lower bound on the independence number of G.
The Havel-Hakimi Algorithm: The number of zeros in the final sequence obtained by the Havel-Hakimi process beginning with D is called the residue of D and is denoted R(D).The concept of residue of a graph, first introduced by Fajtlowicz, has since been popularized by its relationship to independence number.
Results: Maxine cardinality represents a lower bound on the independence number of G