1
$\begingroup$

I see that:

For a cycle graph $n\ge3$, $C_3$ has $1$ independent set, $C_4$ has $2$ independent set, $C_5$ s set, $C_6$ $3$ set, $C_7$ $3$ set, $C_8$ $4$ set, $C_9$ $4$ set.

I can't show this trend as an equation or a mathematic expression. Is it possible to show in one?

1 Answers 1

2

I assume that ‘s’ is a typo for $2$ as the size of a maximal independent set in $C_5$.

If $i(n)$ is the maximal size of an independent set of vertices in $C_n$, you have:

$\begin{array}{rcc} n:&3&4&5&6&7&8&9\\ i(n):&1&2&2&3&3&4&4 \end{array}$

You can express this in many ways. The most straightforward is simply to use a two-part definition:

$i(n)=\begin{cases}\frac{n}2,&\text{if }n\text{ is even}\\\\ \frac{n-1}2,&\text{if }n\text{ is odd}\;.\end{cases}$

If you know the floor function, also called the greatest integer function, you can simply write

$i(n)=\left\lfloor\frac{n}2\right\rfloor\;.$

Other ways are more complicated. For instance, you can easily check that

$i(n)=\frac12\left(n-\frac{1-(-1)^n}2\right)$

gives the same result as the two-part definition, though I don’t recommend using this form!

  • 0
    @Uka: You’re very welcome!2012-11-07