The Structure and Automorphisms of Semi-directed Graphs
Anthony Bonato, Dejan Delić and Changping Wang
Complex real-world networks such as the web graph are often modelled 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 certain on-line random construction of a countably infinite graph without-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 models 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.
Keywords: Universal graphs, semi-directed graphs, web graph, adjacency property, automorphism group, prime model, undecidable universal theory