Abstract: The Havel-Hakimi algorithm iteratively reduces the degree sequence of a graph to a list of zeroes. As shown by Favaron, Mah'eo, and Sacl'e, the number of zeroes produced, known as the residue, is a lower bound on the independence number of the graph. We say that a graph has the strong Havel-Hakimi property if in each of its induced subgraphs, deleting any vertex of maximum degree reduces the degree sequence in the same way that the Havel-Hakimi algorithm does. We characterize graphs having this property (which include all threshold and matrogenic graphs) in terms of minimal forbidden induced subgraphs. We further show that for these graphs the residue equals the independence number, and a natural greedy algorithm always produces a maximum independent set.
Recommendations
Cites work
- scientific article; zbMATH DE number 4173029 (Why is no real title available?)
- A remark on the existence of finite graphs
- Degree sequences of graphs and dominance order
- Graphs \& digraphs
- Independence and the Havel-Hakimi residue
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On the \(k\)-residue of disjoint unions of graphs with applications to \(k\)-independence
- On the residue of a graph
- Threshold graphs and related topics
- k-Independence and thek-residue of a graph
Cited in
(4)
This page was built for publication: Graphs with the strong Havel-Hakimi property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q343704)
