Random threshold graphs

Authors Elizabeth Reilly, Edward Scheinerman

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/230571, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r130.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic number, algebraic connectivity Hamiltonian cycles perfect matchings

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Random graphs (graph-theoretic aspects) (05C80)

Review text

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.

Recommendations

Cited in

(11)

This page was built for publication: Random threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380296)