✦ LIBER ✦

On the independence number of a graph in terms of order and size

✍ Scribed by J. Harant; I. Schiermeyer

Book ID: 108315560
Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 97 KB
Volume: 232
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(00)00298-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The independence number of graphs in ter

The independence number of graphs in terms of degrees

✍ Stanley M. Selkow 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 272 KB

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. (~

A bound on the size of a graph with give

A bound on the size of a graph with given order and bondage number

✍ Bert L. Hartnell; Douglas F. Rall 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 266 KB

On the bipartite independence number of

On the bipartite independence number of a balanced bipartite graph

✍ Odile Favaron; Pedro Mago; Oscar Ordaz 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 603 KB

Venezuela Ap. 47567, Caracas Favaron, O., P. Mago and 0. Ordaz, On the bipartite independence number of a balanced bipartite graph, Discrete Mathematics 121 (1993) 55-63. The bipartite independence number GI aIp of a bipartite graph G is the maximum order of a balanced independent set of G. Let 6 b

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

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 \_(