A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar things recently.

In the same vein, might there be a good reference on random directed graphs that includes a section on the properties of almost all directed graphs? I must add that I'm looking for a text that is self-contained.


To clarify what I mean by property it may be useful to provide a few examples in the case of simple graphs. Almost all simple graphs have diameter 2, are connected and are Hamiltonian [1].


  1. Anuj Dawar and Erich Grädel. Properties of Almost All Graphs and Generalized Quantifiers. 2010.
  2. Edward T. Bullmore and Danielle S. Bassett. Brain Graphs: Graphical Models of the Human Brain Connectome. 2011.
  3. Danielle S. Bassett and Edward T. Bullmore. Small-World Brain Networks Revisited. 2017.
  • 2
    $\begingroup$ Just one result, so not an answer to your question: Almost every $r$-regular digraph is Hamiltonian for $r \ge 3$. Cooper, Colin, Alan Frieze, and Michael Molloy. "Hamilton cycles in random regular digraphs." Combinatorics, Probability and Computing 3, no. 1 (1994): 39-49. $\endgroup$ – Joseph O'Rourke Jul 30 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.