Random Threshold Graphs - Reilly, Elizabeth Perez; Scheinerman, Edward R. (The Electronic Journal of Combinatorics, 2009)
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,…,x_n uniformly in [0,1]; distinct vertices i,j of G are adjacent exactly when x_i + x_j 1. We examine various properties of random threshold graphs such as chromatic number, algebraic connectivity, and the existence of Hamiltonian cycles and perfect matchings.