Random graphs with a fixed maximum degree

Abstract: We study the component structure of the random graph

G = G_{n, m, d}

. Here

d = O (1)

and

G

is sampled uniformly from

{m a t h c a l G}_{n, m, d}

, the set of graphs with vertex set

[n]

,

m

edges and maximum degree at most

d

. If

m = m u n / 2

then we establish a threshold value

m u_{s} t a r

such that if

m u < m u_{s} t a r

then w.h.p. the maximum component size is

O (l o g n)

. If

m u > m u_{s} t a r

then w.h.p. there is a unique giant component of order

n

and the remaining components have size

O (l o g n)

.

Recommendations

Cites Work

Cited In (8)

This page was built for publication: Random graphs with a fixed maximum degree