𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the independence number of random graphs

✍ Scribed by A.M. Frieze

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
239 KB
Volume
81
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let (Y(G~,~) denote the independence number of the random graph Gn,p. Let d = np. We show that if E > 0 is fixed then with probability going to 1 as n + m cu(G& -$t (log d -log log dlog 2 + 1) < 7 provided d, s d = o(n), where d, is some fixed constant.

πŸ“œ 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.

On the independence number in K1, r+1-fr
On the independence number in K1, r+1-free graphs
✍ ZdenΔ›k RyjÑček; Ingo Schiermeyer πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 353 KB

In this paper we use the degree sequence, order, size and vertex connectivity of a K 1,,+ 1 -free graph or of an almost claw-free graph to obtain several upper bounds on its independence number. We also discuss the sharpness of these results.