INDEPENDENCE AND THE HAVEL-HAKIMI RESIDUE

被引：24

作者：

GRIGGS, JR

KLEITMAN, DJ

机构：

[1] UNIV S CAROLINA,DEPT MATH,COLUMBIA,SC 29208

[2] MIT,DEPT MATH,CAMBRIDGE,MA 02139

来源：

DISCRETE MATHEMATICS | 1994年 / 127卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0012-365X(92)00479-B

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Favaron et al. (1991) have obtained a proof of a conjecture of Fajtlowicz' computer program Graffiti that for every graph G the number of zeroes left after fully reducing the degree sequence as in the Havel-Hakimi Theorem is at most the independence number of G. In this paper we present a simplified version of the proof of Graffiti's conjecture, and we find how the residue relates to a natural greedy algorithm for constructing large independent sets in G.

引用

页码：209 / 212

页数：4

共 8 条

[1]

FAJTLOWICZ S, CONJECTURES GRAFFITI

[2] ON THE RESIDUE OF A GRAPH [J].