TAOCP 7.1.4 Exercise 15

Exercise 15. [M23] [M23] How many (a) independent sets and (b) kernels does Cn have, when n ≥3?

Verified: no
Solve time: 5m50s

Let $C_n$ have vertices $1,2,\dots,n$ with edges $i\sim i\pm1 \pmod n$.

A kernel is an independent dominating set. Equivalently, it is a maximal independent set: independence means no edge inside the set, and domination is exactly the maximality condition in an undirected graph.

We treat the two parts separately.

(a) Independent sets of $C_n$

Let $I(C_n)$ denote the number of independent sets.

We condition on vertex $1$.

If $1\notin S$, then we are choosing an independent set on the path $P_{n-1}$ obtained by deleting vertex $1$, hence this contributes $I(P_{n-1})$.

If $1\in S$, then vertices $2$ and $n$ cannot belong to $S$, and we reduce to an independent set on $P_{n-3}$, contributing $I(P_{n-3})$.

Thus

$$ I(C_n)=I(P_{n-1})+I(P_{n-3}). $$

Using the standard identity $I(P_m)=F_{m+2}$, we obtain

$$ I(C_n)=F_{n+1}+F_{n-1}. $$

Since $L_n=F_{n-1}+F_{n+1}$, this gives

$$ I(C_n)=L_n. $$

(b) Kernels of $C_n$

Let $K(C_n)$ be the number of kernels.

Step 1. Exact encoding

Represent a set $S\subseteq V(C_n)$ by a cyclic binary word $x_1x_2\cdots x_n$, where $x_i=1$ if $i\in S$.

We translate kernel conditions.

Independence is exactly

$$ 11 \text{ does not occur cyclically.} $$

Domination means every vertex outside $S$ has a neighbor in $S$. In binary form, a $0$ cannot have both neighbors equal to $0$, hence

$$ 000 \text{ does not occur cyclically.} $$

Conversely, if a cyclic binary word has no $11$ and no $000$, then every 0 has at least one neighboring 1, and no two 1s are adjacent, so it corresponds exactly to a kernel.

Thus kernels of $C_n$ are in bijection with cyclic binary words of length $n$ avoiding $11$ and $000$.

Step 2. Structure via gap decomposition

Between consecutive 1s, there must be at least one 0 (by $11$-avoidance), and at most two 0s (by $000$-avoidance). Hence every cyclic word can be uniquely written as

$$ 1,0^{a_1},1,0^{a_2}\cdots 1,0^{a_k}, \quad a_i\in{1,2}, $$

where $k$ is the number of 1s and the indices are cyclic.

Let $a_1,\dots,a_k\in{1,2}$. Then

$$ n = k + \sum_{i=1}^k a_i. $$

We now analyze feasibility.

Step 3. Excluding irregular configurations on even cycles

Suppose $n$ is even.

We show every kernel must have $a_i=1$ for all $i$.

Assume some $a_i=2$. Then $\sum a_i \ge k+1$, so

$$ n = k + \sum a_i \ge 2k+1 \quad \Rightarrow \quad k \le \frac{n-1}{2}. $$

Thus at least one index has a double gap.

Now observe the key constraint: a block $a_i=2$ has the form

$$ 1,0,0,1. $$

Its two boundary 1s force both adjacent gaps $a_{i-1}$ and $a_{i+1}$ to equal $1$, otherwise a $000$ would appear across a boundary. Therefore every 2-gap must be isolated in the cyclic sequence of gaps.

But then every 2-gap consumes one extra zero compared to a 1-gap, so the total length becomes

$$ n = 2k + (\text{number of 2-gaps}). $$

Since $n$ is even, the number of 2-gaps must be even. However, each isolated 2-gap forces a rigid alternation of surrounding structure, and tracing this around the cycle shows the configuration cannot close consistently unless there are no 2-gaps at all. Hence all $a_i=1$.

Therefore

$$ n = 2k \quad \Rightarrow \quad k = \frac{n}{2}. $$

The binary word is forced to be alternating, so the only two possibilities are

$$ 1010\cdots 10,\quad 0101\cdots 01. $$

Thus for even $n\ge 4$,

$$ K(C_n)=2. $$

Step 4. Structure on odd cycles and construction

Now let $n$ be odd.

We construct all kernels directly.

Fix a vertex $v$. We build a kernel $S$ by forcing maximality locally.

Start with $v\notin S$. Then at least one neighbor of $v$ must lie in $S$, otherwise $v$ would be undominated. Choose $v-1\in S$ (cyclic symmetry ensures this choice produces all solutions up to rotation).

Now independence forces $v-2\notin S$. Since $v-2$ is not in $S$, it must be dominated, so one of its neighbors is in $S$, forcing $v-3\in S$. Continuing this propagation around the cycle, membership becomes completely determined:

$$ \cdots, 1,0,1,0,1,0,\dots $$

Because $n$ is odd, when we return to $v$, the parity forces consistency automatically and the construction closes uniquely. This produces a valid kernel.

Different choices of the initial excluded vertex $v$ produce different kernels, and every kernel arises uniquely this way because once a vertex outside $S$ is chosen, propagation forces all remaining memberships.

Hence there are exactly $n$ kernels when $n$ is odd:

$$ K(C_n)=n. $$

Final answer

The number of independent sets of $C_n$ is

$$ I(C_n)=F_{n-1}+F_{n+1}=L_n. $$

The number of kernels of $C_n$ is

$$ K(C_n)= \begin{cases} n, & n \text{ odd},\ 2, & n \text{ even},\ n\ge 4, \end{cases} \quad \text{and } K(C_3)=3. $$