๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Lower bounds on the stability number of graphs computed in terms of degrees

โœ Scribed by Owen Murphy

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
246 KB
Volume
90
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Probabilistic lower bound on the indep
A Probabilistic lower bound on the independence number of graphs
โœ Stanley M. Selkow ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 124 KB

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.

Sharp bounds on the order, size, and sta
Sharp bounds on the order, size, and stability number of graphs
โœ Pierre Hansen; Maolin Zheng ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 276 KB

## Abstract We consider graphs __G = (V,E)__ with order ฯ = |__V__|, size __e__ = |__E__|, and stability number ฮฒ~0~. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. ยฉ __1993 by John Wiley