A study on properties of random interval graphs and Erd?s-Rényi graph G(n, 2/3)

摘要

In this paper which is based on the M.Sc. thesis of the author, we examine random interval graphs and derive estimates of the number of edges. Next, we study how these edges are spread out, seeing that (for example) the range of degrees for the vertices is much larger than classically. We further investigate the maximum and minimum degree, showing that the former is always very close to the maximum possible value (n - 1) and contrast all these results with the much narrower range of values obtained in the alternative Erd?s-Rényi model of random graphs G (n, 2/3).