An evolution of interval graphs (Q912869)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An evolution of interval graphs |
scientific article |
Statements
An evolution of interval graphs (English)
0 references
1990
0 references
A random interval is defined as \([x-e,x+e]\) with x chosen uniformly in [0,1] and e chosen uniformly in [0,r] where r is a parameter. The interval graph of n such intervals has n points, any pair of which is connected if the two interval overlap. The evolution of an interval graph gives an idea of how the expected properties of the graph change with increasing r. Among properties studied are the degree and chromatic number of the graph; the connecting and number of components. The history of these changes with increasing r is similar to that of random graphs as studied by Erdős and Renyi.
0 references
random interval
0 references
interval graph
0 references
evolution
0 references
0 references