The Structure and Automorphisms of Semi-directed Graphs.
Anthony Bonato, Dejan Delić, Changping Wang · 2016
Abstract. Complex real-world networks such as the web graph are often mod-elled as directed graphs evolving over time, where new vertices are joined to a constant m number of existing vertices of prescribed type. We consider a cer-tain on-line random construction of a countably infinite graph with out-degree m, and show that with probability 1 the construction gives rise to a unique isomorphism type. We show that random semi-directed graphs are prime mod-els in a certain first-order theory. We study algebraic properties of random semi-directed graphs; in particular, we prove that their automorphism groups embed all countable groups. 1.