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
    This makes a lot sense than my class notes. I do not know the floor function. Is it common function to use for discrete mathematics?2012-11-07
  • 0
    @Uka: Yes, definitely; so is the ceiling function. [This article](http://en.wikipedia.org/wiki/Floor_and_ceiling_functions) is a pretty decent introduction to both of them.2012-11-07
  • 0
    Thank you for the link and your help!2012-11-07
  • 0
    @Uka: You’re very welcome!2012-11-07