A PROBABILISTIC LOWER-BOUND ON THE INDEPENDENCE NUMBER OF GRAPHS

被引：16

作者：

SELKOW, SM ^{[1
]}

机构：

[1] WORCESTER POLYTECH INST,DEPT COMP SCI,WORCESTER,MA 01609

来源：

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

关键词：

D O I：

10.1016/0012-365X(93)00102-B

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Caro (1979) and Wei (1981) established a bound on the size of an independent set of a graph as a function of its degrees. In case the degrees of each vertex's neighbors are also known, we establish a lower bound which is tighter for most graphs.

引用

页码：363 / 365

页数：3