×

Erdős-Rényi theory for asymmetric digraphs. (English) Zbl 1422.05095

Summary: We introduce the concept of the asymmetry number for finite digraphs, as a natural generalization of that for undirected graphs by P. Erdős and A. Rényi [Acta Math. Acad. Sci. Hung. 14, 295–315 (1963; Zbl 0118.18901)]. We prove an upper bound for the asymmetry number of finite digraphs and give a condition for equality. We show that our bound is asymptotically best for digraphs with sufficiently large order. We also consider the random oriented graph \(RO\), and make some remarks on \(\operatorname{Aut}(RO)\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0118.18901
PDFBibTeX XMLCite