Independence and the Havel-Hakimi residue
type: Item
instance of: scholarly article
title: Independence and the Havel-Hakimi residue
zbMATH Open document ID: 0805.05082
DOI: 10.1016/0012-365X(92)00479-B
author: J. Griggs
author: Daniel J. Kleitman
published in: Discrete Mathematics
publication date: 1994-06-09T00:00:00Z
review text: It is known that for every graph \(G\) the number of zeros left after fully reducing the degree sequences (as in the Havel-Hakimi theorem) is at most the independence number of \(G\) (cf. \textit{O. Favaron}, \textit{M. Mahéo} and \textit{J.-F. Saclé} [J. Graph Theory 15, No 1, 39-64 (1991; Zbl 0751.05075)]). In the present paper the authors find how the residue relates to a natural greedy algorithm for constructing large independent sets in \(G\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 11B83
zbMATH DE Number: 562631
zbMATH Keywords: degree sequences
zbMATH Keywords: Havel-Hakimi theorem
zbMATH Keywords: independence number
zbMATH Keywords: residue
zbMATH Keywords: greedy algorithm
zbMATH Keywords: independent sets
reviewed by: Václav Havel
describes a project that uses: GRAFFITI
MaRDI profile type: Publication
cites work: On conjectures of Graffiti
cites work: On the residue of a graph
cites work: Lower bounds on the independence number in terms of the degrees
cites work: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
cites work: A remark on the existence of finite graphs
cites work: Approximation algorithms for combinatorial problems
full work available at URL: 0012-365x(92)00479-b
OpenAlex ID: W2089356095
description: scientific article; zbMATH DE number 562631