Graphs with the strong Havel-Hakimi property

DOI10.1007/S00373-015-1674-7zbMATH Open1351.05166arXiv1505.00085OpenAlexW2106681755MaRDI QIDQ343704FDOQ343704

Authors: Michael D. Barrus, Grant Molnar 

Publication date: 29 November 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1505.00085

Recommendations

• Independence and the Havel-Hakimi residue
• k-Independence and thek-residue of a graph
• Havel-Hakimi residues of unigraphs
• On the residue of a graph
• A simple criterion on degree sequences of graphs

zbMATH Keywords

independence numberresidueHavel-Hakimi algorithm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Cites Work

• Threshold graphs and related topics
• Graphs \& digraphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• A remark on the existence of finite graphs
• On the residue of a graph
• Degree sequences of graphs and dominance order
• Independence and the Havel-Hakimi residue
• Title not available (Why is that?)
• On the \(k\)-residue of disjoint unions of graphs with applications to \(k\)-independence
• k-Independence and thek-residue of a graph

Cited In (4)

• Graphs with the balas—uhry property
• Title not available (Why is that?)
• Havel-Hakimi residues of unigraphs
• A strong Harnack inequality for graphs

Uses Software

• GRAFFITI

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)