Full Subgraphs

Markström, Klas , Victor Falgas-Ravry & Jaques Verstraete | 2017

Journal of Graph theory 88, no 3, p.411-427.

Sammanfattning

Let urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0001 be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0002. Let urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0003 denote the order of a largest full subgraph of G. If urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0004 is a nonnegative integer, define

Erdős, Łuczak, and Spencer proved that for urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0006,

In this article, we prove the following lower bound: for urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0008,

Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0010. In contrast, we show that for any n‐vertex graph G, either G or urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0011 contains a full subgraph on urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0012 vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.

Läs mer om artikeln: Full Subgraphs

Journal of Graph theory 88, no 3, p.411-427.

Sammanfattning

Let urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0001 be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0002. Let urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0003 denote the order of a largest full subgraph of G. If urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0004 is a nonnegative integer, define

Erdős, Łuczak, and Spencer proved that for urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0006,

In this article, we prove the following lower bound: for urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0008,

Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0010. In contrast, we show that for any n‐vertex graph G, either G or urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0011 contains a full subgraph on urn:x-wiley:03649024:media:jgt22221:jgt22221-math-0012 vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.

Läs mer om artikeln: Full Subgraphs