Random threshold graphs (Q2380296)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Random threshold graphs
scientific article

    Statements

    Random threshold graphs (English)
    0 references
    26 March 2010
    0 references
    Summary: We introduce a pair of natural, equivalent models for random threshold graphs and use these models to deduce a variety of properties of random threshold graphs. Specifically, a random threshold graph \(G\) is generated by choosing \(n\) IID values \(x_1, \dots, x_n\) uniformly in \([0, 1]\); distinct vertices \(i, j\) of \(G\) are adjacent exactly when \(x_i + x_j \geqslant 1\). We examine various properties of random threshold graphs such as chromatic number, algebraic connectivity, and the existence of Hamiltonian cycles and perfect matchings.
    0 references
    chromatic number, algebraic connectivity
    0 references
    Hamiltonian cycles
    0 references
    perfect matchings
    0 references

    Identifiers