On random irregular subgraphs

Abstract: Let

G

be a

d

-regular graph on

n

vertices. Frieze, Gould, Karo'nski and Pfender began the study of the following random spanning subgraph model

H = H (G)

. Assign independently to each vertex

v

of

G

a uniform random number

x (v) i n [0, 1]

, and an edge

(u, v)

of

G

is an edge of

H

if and only if

x (u) + x (v) g e q 1

. Addressing a problem of Alon and Wei, we prove that if

d = o (n / (l o g n)^{12})

, then with high probability, for each nonnegative integer

k l e q d

, there are

(1 + o (1)) n / (d + 1)

vertices of degree

k

in

H

.

Recommendations

Cited in

(3)

This page was built for publication: On random irregular subgraphs