Cycle Saturation in Random Graphs

Abstract: For a fixed graph

F,

the minimum number of edges in an edge-maximal

F

-free subgraph of

G

is called the

F

-saturation number. The asymptotics of the

F

-saturation number of the binomial random graph

G (n, p)

for constant

p i n (0, 1)

is known for complete graphs

F = K_{m}

and stars

F = K_{1, m} .

This paper is devoted to the case when the pattern graph

F

is a simple cycle

C_{m} .

We prove that, for

m g e q s l a n t 5,

whp

m a t h r m s a t l e f t (G l e f t (n, p i g h t), C_{m} i g h t) = n + T h e t a l e f t (f r a c n l n n i g h t) .

Also we find

c = c (p)

such that whp

f r a c 32 n (1 + o (1)) l e q s l a n t m a t h r m s a t l e f t (G l e f t (n, p i g h t), C_{4} i g h t) l e q s l a n t c n (1 + o (1)) .

In particular, whp

m a t h r m s a t l e f t (G l e f t (n, f r a c 12 i g h t), C_{4} i g h t) l e q s l a n t f r a c 2714 n (1 + o (1)) .

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Cycle Saturation in Random Graphs