English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The Havel-Hakimi residue (or residue) of a graph is the number of zeros left after iteratively applying the Havel-Hakimi algorithm to a degree sequence. Favaron, Mahéo, and Saclé showed that the residue is a lower bound on the independence number. Determining how good of a bound this is remains an open question, including in what cases the bound is realized. This dissertation looks to help answer when the bound is realized by examining the Maxine heuristic, which reduces a graph G, to an independent set of size M(G). It has been shown that given a graph G, M(G) is bounded between the independence number and the residue of a graph. We find a class of graphs characterized by a list of forbidden subgraphs, an improvement on a list from Barrus and Molnar, such that M(G) is equal to the independence number for all graphs in the class. Furthermore, to help understand the relationship between the independence number and the residue, the number of reorderings required in the Havel-Hakimi algorithm is found for all regular sequences. It is known that threshold degree sequences, a well known family of degree sequences, have independence number equal to the residue. This dissertation shows that threshold degree sequences require no reorderings and thus begs the question if the number of reorderings is related to the difference in the bound between the independence number and the residue. Then the cases of one reordering and a maximum number of reorderings is determined and analyzed.

ON THE HAVEL-HAKIMI RESIDUE OF DEGREE SEQUENCES AND ITS RELATION TO THE INDEPENDENCE NUMBER