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.


\begin{theorem}[\cite{FvLS95a}]\mbox{}
\beginsmall{itemize}
\item Let $p = n^{-1...
...ox{with probability $1-o(1)$.}
\end{displaymath}\endsmall{itemize}
\end{theorem}

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


\begin{theorem}[\cite{GP98a}]\mbox{}
For sufficiently large $n$, with probabili...
...ingle
interval per arc, except for $O(\log^3{n})$\ arcs per node.
\end{theorem}

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




2000-03-21