×

On vertex, edge, and vertex-edge random graphs. (English) Zbl 1217.05205

Summary: We consider three classes of random graphs: edge random graphs, vertex random graphs, and vertex-edge random graphs. Edge random graphs are Erdős-Rényi random graphs, vertex random graphs are generalizations of geometric random graphs, and vertexedge random graphs generalize both. The names of these three types of random graphs describe where the randomness in the models lies: in the edges, in the vertices, or in both.
We show that vertex-edge random graphs, ostensibly the most general of the three models, can be approximated arbitrarily closely by vertex random graphs, but that the two categories are distinct.

MSC:

05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS