next up previous contents
Next: Other Classes of Graphs Up: Specific Class of Graphs Previous: Treewidth Bounded Graphs   Contents

Random Graphs

The class $\cG_{n,p}$ denotes the classic model of n-node random graphs, where p represents the probability to have an edge between any two nodes.

\item Let $p = n^{-1...
...ox{with probability $1-o(1)$.}

The next result includes the case p=1/2, and shows that almost all n-node graphs have constant compactness.

For sufficiently large $n$, with probabili...
interval per arc, except for $O(\log^3{n})$\ arcs per node.

Open question 10    
- Do almost all n-node graphs have compactness 1?