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