The connected components
3
The connected components
Molloy and Reed [1995] showed that for a
random graph with 
vertices
of degree i, where 
are non-negative values which sum to 1, the
giant component emerges when
So
long as the maximum degree is less than 
They also show that almost surely there is no
giant component when 
and
maximum degree less than 
Here
we compute Q for our 
graphs.
We
are thus led to consider the value 
which is a solution to
If
We
first summarize the results here:
1.
When 
the random graph a. s. has no giant component.
When there is almost surely a unique giant
component.
2.
When
almost surely the second largest components
have size 
there is almost surely a component of size x.
3.
When 
almost surely the second largest components
are of size
For any 
there is almost surely a component of size x.
4.
When 
the second largest components are a. s. of
size 
The graph is almost surely not connected.
5.
When 0 <β< 1, the graph is almost surely
connected.
6.
For
β = β0 = 3.47875 ..., this is a very complicated case. It corresponds to the
double jump of random graph G(n, p) with p = 1 n. For β = 1, there is a nontrivial
probability for either cases that the graph is connected or disconnected.
7.
For
this case is complicated case. It corresponds
to the double jump of random graph 
with 
.
8.
For
, there is a nontrivial
probability for either cases that the graph is connected or disconnected.
We
remark that for β > 8, Molloy and Reed’s result immediately implies that
almost surely there is no giant component. When β ≤ 8, additional analysis is
needed to deal with the degree constraints. We will prove in Theorem 4.2 that
almost surely there is no giant component when 
In section 5, we will deal with the range 
We will show theorem5.1 that almost surely
there is a unique giant component when 
furthermore,
we will determine the size of the second largest components within a constant
factor.
Comments
Post a Comment