Kernels on a Directed Cycle
A kernel is a set of vertices that is internally nonadjacent and can be reached in one directed step from every vertex outside the set. On a directed cycle, each vertex has just one outgoing arc, so the absorption condition has a particularly direct form: whenever a vertex is not in the kernel, its successor must be in it. The resulting choices alternate around the cycle. Whether that alternation closes consistently is determined by the parity of the cycle length.
All digraphs considered here are finite and simple. An arc \(u\to v\) is directed from \(u\) to \(v\); it need not be accompanied by an arc \(v\to u\). A consistently oriented directed cycle of length \(n\ge 3\) has distinct vertices \(v_0,\ldots,v_{n-1}\) and precisely the cycle arcs \(v_i\to v_{i+1}\), where indices are taken modulo \(n\). Thus the final arc is \(v_{n-1}\to v_0\). We write this digraph as \(\overrightarrow{C_n}\).
The direction in the absorption condition matters: vertices outside \(K\) must have an arc to \(K\), not merely an arc from \(K\) to them. In \(\overrightarrow{C_n}\), the only outgoing arc from \(v_i\) is \(v_i\to v_{i+1}\). Consequently, for a proposed kernel \(K\), a vertex \(v_i\) outside \(K\) is absorbed exactly when \(v_{i+1}\in K\).
The Alternation Rule
Record membership in a proposed set \(K\) with a binary value \(x_i\): let \(x_i=1\) if \(v_i\in K\), and \(x_i=0\) otherwise. The two kernel conditions force consecutive values to differ.
Proof. Suppose first that \(K\) is a kernel. If \(x_i=1\), then \(v_i\in K\). Independence forbids the arc \(v_i\to v_{i+1}\) from having both endpoints in \(K\), so \(x_{i+1}=0\). If \(x_i=0\), then \(v_i\notin K\). Absorption requires an arc from \(v_i\) to a vertex in \(K\), and its only outgoing arc is \(v_i\to v_{i+1}\), so \(x_{i+1}=1\). These two cases give \(x_{i+1}=1-x_i\).
Conversely, suppose the membership values satisfy the equation at every index, including the index \(n-1\), for which \(i+1\) means \(0\). No two consecutive vertices are both selected, so none of the cycle arcs has both endpoints in \(K\); hence \(K\) is independent. Every unselected vertex \(v_i\) has \(x_i=0\), and the equation gives \(x_{i+1}=1\). Its outgoing arc therefore goes to a vertex in \(K\), so it is absorbed. Both kernel conditions hold. \(\square\)
This lemma reduces the problem to closing an alternating sequence around the cycle. Once \(x_0\) is chosen, every later value is forced: \(x_1=1-x_0\), \(x_2=x_0\), and the values continue to alternate. The final requirement is that the arc from \(v_{n-1}\) back to \(v_0\) also joins opposite membership values.
The Even-Cycle Criterion
Proof. Suppose \(K\) is a kernel. By the lemma, membership alternates at every step. Starting with \(x_0\), after \(n\) steps the value reached must be \(x_n=x_0\), because \(v_n=v_0\). Alternation gives \(x_n=x_0\) when \(n\) is even and \(x_n=1-x_0\) when \(n\) is odd. If \(n\) is odd, the required equality \(x_n=x_0\) would imply \(x_0=1-x_0\), which is impossible for \(x_0\in\{0,1\}\). Thus no kernel exists when \(n\) is odd.
Now suppose \(n\) is even. If \(x_0=1\), alternation selects precisely the even-indexed vertices. The closing step also alternates correctly: \(n-1\) is odd, so \(x_{n-1}=0\) and \(x_0=1\). By the lemma, this assignment gives a kernel. If instead \(x_0=0\), alternation selects precisely the odd-indexed vertices; since \(n-1\) is odd, \(x_{n-1}=1\) and \(x_0=0\), so the closing step again satisfies the lemma. These are two different kernels. There are no others, because every kernel must alternate and its membership is completely determined by the choice of \(x_0\), which has only the two possible values 0 and 1. \(\square\)
The proof gives both an existence test and a complete description, not just an example of a kernel. For an even cycle, either alternating class works; choosing one vertex forces every other membership decision. For an odd cycle, the forced alternation conflicts with the closing arc.
Worked Example: Both Kernels of a Directed 4-Cycle
Let \(D\) have vertex set \(V(D)=\{v_0,v_1,v_2,v_3\}\) and arc set \(A(D)=\{v_0\to v_1,\ v_1\to v_2,\ v_2\to v_3,\ v_3\to v_0\}\). Find all kernels.
Begin with \(v_0\). If \(v_0\) is selected, independence forces \(v_1\) out; since \(v_1\) is out, absorption forces \(v_2\) in; independence then forces \(v_3\) out. The closing arc \(v_3\to v_0\) has an unselected tail and selected head, as required. This gives \(K_0=\{v_0,v_2\}\).
If \(v_0\) is not selected, absorption forces \(v_1\) in; independence forces \(v_2\) out; absorption forces \(v_3\) in. The closing arc \(v_3\to v_0\) has a selected tail and unselected head, so it does not violate independence. This gives \(K_1=\{v_1,v_3\}\).
| Candidate | Independence check | Absorption check |
|---|---|---|
| \(K_0=\{v_0,v_2\}\) | No cycle arc joins two selected vertices. | \(v_1\to v_2\) and \(v_3\to v_0\). |
| \(K_1=\{v_1,v_3\}\) | No cycle arc joins two selected vertices. | \(v_0\to v_1\) and \(v_2\to v_3\). |
Check: each candidate includes 2 vertices, and the two candidates are distinct. There can be no further kernel: the lemma says that a kernel is determined by whether \(v_0\) is in or out, and these two cases have both been checked.
Worked Example: The Two Kernels of a Directed 6-Cycle
Let \(D\) have vertex set \(V(D)=\{v_0,v_1,v_2,v_3,v_4,v_5\}\) and arc set \(A(D)=\{v_0\to v_1,\ v_1\to v_2,\ v_2\to v_3,\ v_3\to v_4,\ v_4\to v_5,\ v_5\to v_0\}\). The length is \(6\), so it is even.
Starting with \(v_0\) selected, the alternating rule gives \(K_0=\{v_0,v_2,v_4\}\). The unselected vertices are \(v_1,v_3,v_5\), and their outgoing arcs are \(v_1\to v_2\), \(v_3\to v_4\), and \(v_5\to v_0\), each of which reaches \(K_0\). The selected vertices are not consecutive on the cycle, including across the closing arc \(v_5\to v_0\), so \(K_0\) is independent.
Starting with \(v_0\) unselected gives \(K_1=\{v_1,v_3,v_5\}\). The outside vertices \(v_0,v_2,v_4\) have arcs \(v_0\to v_1\), \(v_2\to v_3\), and \(v_4\to v_5\) into \(K_1\). No cycle arc joins two members of \(K_1\), including the arc \(v_5\to v_0\), whose head is outside the set.
Check: each set has 3 vertices, the two sets are disjoint, and together they contain all 6 vertices. The theorem also rules out any additional kernel, since the only two possible alternating assignments are the ones just verified.
Worked Example: Why a Directed 5-Cycle Has No Kernel
Let \(D\) have vertex set \(V(D)=\{v_0,v_1,v_2,v_3,v_4\}\) and arc set \(A(D)=\{v_0\to v_1,\ v_1\to v_2,\ v_2\to v_3,\ v_3\to v_4,\ v_4\to v_0\}\). Suppose \(v_0\) belongs to a kernel. Independence forces \(v_1\) out, absorption at \(v_1\) forces \(v_2\) in, independence forces \(v_3\) out, and absorption at \(v_3\) forces \(v_4\) in. But then the closing arc \(v_4\to v_0\) has both endpoints selected, contradicting independence.
If \(v_0\) is outside the proposed kernel, absorption forces \(v_1\) in; the alternating rule then forces \(v_2\) out, \(v_3\) in, and \(v_4\) out. The closing arc \(v_4\to v_0\) now has both endpoints outside. In particular, \(v_4\) is not absorbed, because its only outgoing arc goes to \(v_0\), also outside. Neither choice for \(v_0\) can produce a kernel.
Check: the length is \(5\), which is odd. The theorem predicts no kernel, and the two possible initial membership values have both led to a contradiction or an unabsorbed vertex.
Orientation and Common Pitfalls
The criterion concerns a consistently oriented cycle: every arc points in the same cyclic direction. Reversing all the arcs does not change the parity criterion. In the reversed orientation, a vertex outside a kernel must have its predecessor in the kernel instead of its successor. Membership still has to alternate around the cycle, and the same even-versus-odd closing condition applies.
Do not extend this result to an arbitrary orientation of the edges of an undirected cycle. The local absorption rule depends on which arcs leave each vertex. A vertex with no outgoing arc cannot be absorbed unless it is itself in the kernel, and vertices with more than one outgoing arc may have more than one possible absorbing neighbor. The proof above uses the fact that each vertex has exactly one outgoing arc, directed to its successor.
A common mistake is to choose alternating vertices on an odd cycle and overlook the final arc. For the directed 5-cycle, the tempting set \(\{v_0,v_2,v_4\}\) fails independence because \(v_4\to v_0\) joins two selected vertices. The other alternating choice, \(\{v_1,v_3\}\), fails absorption: \(v_4\) is outside, but its only outgoing arc \(v_4\to v_0\) ends outside the set. The correction is to check the closing arc and absorption for every outside vertex, not only the consecutive pairs before the cycle wraps around.
Kernels are useful because they combine two demands that can otherwise pull in opposite directions: chosen vertices must not directly interact, yet every unchosen vertex must have an immediate directed route into the chosen set. On a consistently oriented cycle, the one-step requirement leaves no flexibility: membership must alternate. The parity criterion is exactly the condition that this local rule is compatible with returning to the starting vertex.
Check Your Understanding
For each question, keep both independence and the direction of absorption in view.
- Write the two kernels of the consistently oriented directed cycle on 8 vertices, indexing its vertices from \(v_0\).
- In a directed cycle, why does an outside vertex \(v_i\) require \(v_{i+1}\) to be in a kernel rather than \(v_{i-1}\)?
- Explain why alternating membership around a directed cycle of odd length cannot satisfy the closing condition.
- For the directed 6-cycle in the worked example, verify directly that \(\{v_0,v_2,v_4\}\) is independent and absorbs every outside vertex.
- Give the specific independence or absorption failure for each alternating choice on a directed 5-cycle.