Few H copies in F-saturated graphs

recovers the well-studied saturation function. We provide a first investigation into this general function focusing on the cases where the host graph is either

K_{s}

or

C_{k}

-saturated. Some representative interesting behavior is: (a) For any natural number

m

, there are graphs

H

and

F

such that

m a t h r m s a t (n, H, F) = T h e t a (n^{m})

. (b) For many pairs

k

and

l

, we show

m a t h r m s a t (n, C_{l}, C_{k}) = 0

. In particular, we prove that there exists a triangle-free

C_{k}

-saturated graph on

n

vertices for any

k > 4

and large enough

n

. (c)

m a t h r m s a t (n, K_{3}, K_{4}) = n - 2

,

m a t h r m s a t (n, C_{4}, K_{4}) s i m f r a c n^{2} 2

, and

m a t h r m s a t (n, C_{6}, K_{5}) s i m n^{3}

. We discuss several intriguing problems which remain unsolved.

Recommendations

Cited in

(7)

This page was built for publication: Few \(H\) copies in \(F\)-saturated graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066892)