𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the number of distinct induced subgraphs of a graph

✍ Scribed by P. Erdős; A. Hajnal

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
582 KB
Volume
75
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Graphs with a small number of distinct i
Graphs with a small number of distinct induced subgraphs
✍ Noga Alon; Béla Bollobás 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 514 KB

Let G be a graph on n vertices. We show that if the total number of isomorphism types of induced subgraphs of G is at most &II', where E < lo-\*', then either G or its complement contain an independent set on at least (1 -4e)n vertices. This settles a problem of Erdiis and Hajnal.

On the number of maximal bipartite subgr
On the number of maximal bipartite subgraphs of a graph
✍ Jesper Makholm Byskov; Bolette Ammitzbøll Madsen; Bjarke Skjernaa 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ¼ O(1:8613 n ) and give an algorithm that finds all maximal

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

Finite Induced Graph Ramsey Theory: On P
Finite Induced Graph Ramsey Theory: On Partitions of Subgraphs
✍ D.S. Gunderson; V. Rodl; N.W. Sauer 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 425 KB

For given finite (unordered) graphs \(G\) and \(H\), we examine the existence of a Ramsey graph \(F\) for which the strong Ramsey arrow \(F \rightarrow(G)_{r}^{\prime \prime}\) holds. We concentrate on the situation when \(H\) is not a complete graph. The set of graphs \(G\) for which there exists a

The minimum number of subgraphs in a gra
The minimum number of subgraphs in a graph and its complement
✍ Lane Clark 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB 👁 2 views

## Abstract For a graphb __F__ without isolated vertices, let __M__(__F__; __n__) denote the minimum number of monochromatic copies of __F__ in any 2‐coloring of the edges of __K__~__n__~. Burr and Rosta conjectured that when __F__ has order __t__, size __u__, and __a__ automorphisms. Independent