Trees in random graphs (Q790843): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: Zbigniew Palka / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: John Mitchem / rank
Normal rank
 

Revision as of 02:39, 11 February 2024

scientific article
Language Label Description Also known as
English
Trees in random graphs
scientific article

    Statements

    Trees in random graphs (English)
    0 references
    0 references
    1983
    0 references
    The probability space consisting of all graphs on a set of \(n\) vertices where each edge occurs with probability \(p\), independently of all other edges, is denoted by \(G(n,p)\). Theorem: For each \(\epsilon>0\) almost every graph \(G\in G(n,p)\) is such if \((1+\epsilon)\log n/\log d<r<(2- \epsilon)\log n/\log d\) where \(d=1/(1-p),\) then \(G\) contains a maximal induced tree of order \(d\). Problem: Let \(p\) be a function of \(n\), find such a value of \(p\) for which a graph \(G\in G(n,p)\) has the greatest induced tree.
    0 references
    induced star
    0 references
    maximal induced tree
    0 references

    Identifiers