On the asymptotic behavior of the independence number of a random \((n,n)\)-tree (Q1911235)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the asymptotic behavior of the independence number of a random \((n,n)\)-tree
scientific article

    Statements

    On the asymptotic behavior of the independence number of a random \((n,n)\)-tree (English)
    0 references
    0 references
    26 August 1996
    0 references
    Let \(T\) denote a bipartite tree with \(n\) labelled dark nodes and \(n\) labelled light nodes. The authors show that the node independence number of \(T\) lies between \(n\) and \((1.27974)n\) for almost all such trees \(T\) as \(n \to \infty\).
    0 references
    asymptotic behavior
    0 references
    random
    0 references
    bipartite tree
    0 references
    node independence number
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references