𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On subgraph number independence in trees

✍ Scribed by R.L Graham; E Szemerédi

Publisher
Elsevier Science
Year
1978
Tongue
English
Weight
428 KB
Volume
24
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On graphs with subgraphs having large in
On graphs with subgraphs having large independence numbers
✍ Noga Alon; Benny Sudakov 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

## Abstract Let __G__ be a graph on __n__ vertices in which every induced subgraph on ${s}={\log}^{3}\, {n}$ vertices has an independent set of size at least ${t}={\log}\, {n}$. What is the largest ${q}={q}{(n)}$ so that every such __G__ must contain an independent set of size at least __q__? This

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

The structure and maximum number of maxi
The structure and maximum number of maximum independent sets in trees
✍ Jennifer Zito 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 732 KB

A subset of vertices is a maximum independent set if no two of the vertices are joined by an edge and the subset has maximum cardinality. In this paper we answer a question posed by Herb Wilf. We show that the greatest number of maximum independent sets for a tree of n vertices is 2(n-3\* for odd n