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

A Probabilistic lower bound on the independence number of graphs

โœ Scribed by Stanley M. Selkow

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
124 KB
Volume
132
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

A lower bound on the independence number
A lower bound on the independence number of arbitrary hypergraphs
โœ Thiele, Torsten ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 104 KB ๐Ÿ‘ 3 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies ฮฑ(H) โ‰ฅ vโˆˆV f (d

On the independence number of random gra
On the independence number of random graphs
โœ A.M. Frieze ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 239 KB

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.

On the Density of Subgraphs in a Graph w
On the Density of Subgraphs in a Graph with Bounded Independence Number
โœ Pavel Valtr ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(