A study on properties of random interval graphs and Erdős Rényi graph 𝒢(n, 2/3)
V Iliopoulos - Journal of Discrete Mathematical Sciences and …, 2017 - Taylor & Francis
Journal of Discrete Mathematical Sciences and Cryptography, 2017•Taylor & Francis
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 …
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 …
Abstract
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 𝒢(n, 2/3).
Taylor & Francis Online