The saturation number of C₆

Abstract: A graph

G

is called

C_{k}

-saturated if

G

is

C_{k}

-free but

G + e

not for any

e i n E (o v e r l i n e G)

. The saturation number of

C_{k}

, denoted

s a t (n, C_{k})

, is the minimum number of edges in a

C_{k}

-saturated graph on

n

vertices. Finding the exact values of

s a t (n, C_{k})

has been one of the most intriguing open problems in extremal graph theory. In this paper, we study the saturation number of

C_{6}

. We prove that

4 n / 3 - 2 l e s a t (n, C_{6}) l e (4 n + 1) / 3

for

n g e 9

, which significantly improves the existing lower and upper bounds for

s a t (n, C_{6})

.

This page was built for publication: The saturation number of $C_6$