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

On the bounds for the ultimate independence ratio of a graph

โœ Scribed by Xuding Zhu

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
416 KB
Volume
156
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we study the ultimate independence ratio I(G) of a graph G, which is defined as the limit of the sequence of independence ratios of powers of G. We construct a graph G with ultimate independence ratio I(G) strictly between the previous known upper bound 1/zz(G) and lower bound 1/x(G). We give a better lower bound for I(G) by using the concept of starchromatic number of a graph.

๐Ÿ“œ SIMILAR VOLUMES

On the independence ratio of a graph
On the independence ratio of a graph
โœ Michael O. Albertson; Joan P. Hutchinson ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 318 KB

## Abstract This paper presents some recent results on lower bounds for independence ratios of graphs of positive genus and shows that in a limiting sense these graphs have the same independence ratios as do planar graphs. This last result is obtained by an application of Menger's Theorem to show t

A lower bound on the independence number
A lower bound on the independence number of a graph
โœ Jochen Harant ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 210 KB

A new lower bound on the independence number of a graph is established and an accompanying efficient algorithm constructing an independent vertex set the cardinality of which is at least this lower bound is given. (~

Bounds on the Size of the Likelihood Rat
Bounds on the Size of the Likelihood Ratio Test of Independence in a Contingency Table
โœ W.Y. Loh; X.J. Yu ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 323 KB

Bounds are obtained on the limiting size of the nominal level- \(\alpha\) likelihood ratio test of independence in a \(r \times c\) contingency table. The situations considered include sampling with both marginal totals random and with one margin fixed. Upper and lower bounds are obtained. The limit

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.