The kernel in special directed circular graphs

Abstract

A kernel in a directed graph D = (V, A) is a set K of vertices of D such that no two vertices in K are adjacent and for every vertex v in V \ K there is a vertex u in K, such that (v, u) is an arc of D. It is well known that the problem of the existence of a kernel is NP-complete for a general digraph. Bang-Jensen and Gutin pose an interesting problem (Problem 12.3.5) in their book [Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2000]: to characterize all circular digraphs with kernels. In this paper, we study the problem of the existence of the kernel for several special classes of circular digraphs. Moreover, a class of counterexamples is given for the Duchet kernel conjecture (for every connected kernel-less digraph which is not an odd directed cycle, there exists an arc which can be removed and the obtained digraph is still kernel-less).

Keywords

Kernel / directed graph / circular graph / Duchet kernel conjecture

1 Introduction

A directed graph D is defined as an ordered triple (V(D), A(D), ψ(D)), where V(D) is a non-empty set of vertices, A(D) is a set of arcs that does not intersect with V(D), and ψ(D) is an association function that maps each arc in D to an ordered pair of vertices in D. Typically, a directed graph is denoted as D = (V, A). If an arc a = (u, v) exists in D, then u is called the tail of a, and v is called the head of a. It is also said that u controls v, or equivalently, v is controlled (or absorbed) by u.

A kernel K of a directed graph D = (V, A) is a subset of the vertex set V, where any two vertices in K are not adjacent in D (independence), and for every vertex v ∈V \ K, there exists a vertex u ∈ K such that (v, u) is an arc in D (dominance or absorption) [3]. If a directed graph does not have a kernel, it is called kernel-less. Kernels are applied in various important fields such as logic, computational complexity, artificial intelligence, game theory, combinatorial mathematics, and coding theory [2, 4].

Different approaches to defining the concept of a kernel in directed graphs have been introduced in the literature [9, 14]. The concept was first proposed by Von Neumann and Morgenstern [14] when describing the winner in a two-player game, and it is proved that any acyclic directed graph had a unique kernel. However, not every directed graph has a kernel and even if it does, it may not be unique. Richardson [11] proved that every kernel-less directed graph contained at least one odd cycle. Berge and Duchet [4] provided a concise proof of this result. Furthermore, it was demonstrated in [2, 4] that odd cycles and most tournament graphs did not have kernels. But for general directed graphs [6, 13] and planar directed graphs where both the in-degree and out-degree are at most 2 and the total degree is at most 3 [8], the problem of determining the existence of a kernel is NP-complete. Moreover, for certain special classes of directed graphs, the problem of determining the number of kernels is NP-hard [12]. On the other hand, every finite directed graph in which all cycles have even length has a kernel [11]. This implies that an odd cycle is the simplest type of kernel-less directed graph, and it possesses the following property: If an arc is removed from a directed odd cycle, the resulting acyclic directed graph will have a unique kernel.

In 1980, Duchet conjectured that except for directed odd cycles, no other connected directed graph possessed the aforementioned property [7] (referred to as the Duchet Kernel Conjecture). In other words, for any kernel-less connected directed graph that is not an odd cycle there must exist at least one arc whose removal still results in a kernel-less directed graph. However, Apartsin et al. [1] provided a counterexample to this conjecture: the circulant graph C₄₃(1, 7, 8) was kernel-less, but after the removal of any single arc, the resulting graph had a kernel. In 1998, Boros and Gurvich refined this conjecture [5], proposing that an odd hole (an undirected odd cycle of length at least 5) was the only type of connected graph that was not itself kernel-solvable (see [2]), yet becomes kernel-solvable after the removal of any single edge.

In [1], Apartsin et al. disproved the Duchet Kernel Conjecture by presenting a counterexample using circulant graphs. However, the characterization of kernel existence in circulant graphs has remained an open problem. Bang-Jensen and Gutin, in their classic work on directed graphs [2], explicitly list this as an open problem. In this paper, we provide an initial discussion on the kernels of certain special circulant digraphs and apply the corresponding results to construct a counterexample to the Duchet Kernel Conjecture. Below, the definition of a circulant digraph is as follows:

Definition 1.1 [2]　A directed graph is called a circulant digraph if its vertex set is given by V=\{1,2,\dots ,n\}, and its arc set is A=\left\{\right(i,i+j\left(\mathrm{m}\mathrm{o}\mathrm{d}n\right)):1\le i\le n,j\in W\}, where n ≥ 2 is an integer, and W\subseteq \{1,2,\dots ,n-1\}. Denote this circulant digraph as C_n\left(W\right). In particular, C_n(\{1,2,\dots ,n-1\}) is the symmetric directed complete graph K_n, and C_n ({1}) represents the directed n-cycle (For simplicity, it may denote C_n\left(\{i,j,\dots ,k\}\right) as C_n\left(i,j,\dots ,k\right)\mathrm{i}\mathrm{n}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}\mathrm{u}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}).

Next, it analyzes the kernels of certain circulant digraphs, and considers simple circulant digraphs, meaning that for any graph C_n\left(i,j,\dots ,k\right), it is assumed: .

2 Kernel of a directed circulant graph C_n (1, s)

Theorem 2.1　 A graph C_n (1, s) has a kernel if and only if n\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}\frac{s+1}{\mathrm{g}\mathrm{c}\mathrm{d}(t_1,t_2)}\right), where s+1=2t_1+3t_2 and t₁, t₂ are any pair of non-negative integers satisfying the equation. Here, \mathrm{g}\mathrm{c}\mathrm{d}(t_1,t_2) denotes the greatest common divisor of t₁ and t₂.

Proof　Necessity: Let K=\{k_1,k_2,\dots ,k_m\} be a kernel of the graph C_n(1,s), where , which will not be explicitly stated further. Define d_i as the distance between the i^th and (i+1)^th elements in K in the graph C_n(1,s), i.e.,

k_{i+1}=k_i+d_i\left(\mathrm{m}\mathrm{o}\mathrm{d}n\right),i=1,2,\dots ,m;k_{m+1}=k_1.

It is noted that the possible values of d_i are only 2 or 3 (throughout this paper, the subscript χ in dχ is taken modulo m, which will not be explicitly stated further). If d_i = 1 or s, then K will not satisfy the independence condition. If d_i ≥ 4, K will not satisfy the absorption condition. In particular, when s = 2, there must be d_i = 3; and when s = 3, there must be d_i = 2.

Since for any i, the element k_i absorbs both k_i + 1 and k_i + s, it follows that k_{i+1}\ne k_i+1, meaning that there must exist an index j such that k_j=k_i+(s+1), where and j is an integer. Thus, it requires to partition the sequence of distances summing to s + 1. Since d_i (i = 1, 2, \dots, m) can only be 2 or 3, and based on the kernel definition, there is

d_j=d_i,d_{j+1}=d_{i+1}, \dots , d_{2j-i-1}=d_{j-1},

and

d_i+d_{i+1}+d_{i+2}+\cdots +d_{j-1}=d_j+d_{j+1}+d_{j+2}+\cdots +d_{2j-i-1}=s+1,

where s+1=2t_1+3t_2, for some non-negative integers t₁, t₂.

If there exists s^{\prime } such that s+1\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}{s}^{\prime }\right), where s^{\prime }=2t_1^{\prime }+3t_2^{\prime }, for some non-negative integers t_1^{\prime },t_2^{\prime }, then there exists an index j^{\prime } such that k_{j^{\prime }}=k_i+s^{\prime }, where , and j^{\prime } is an integer, and

d_{j^{\prime }}=d_i,d_{j^{\prime }+1}=d_{i+1}, \dots , d_{2j^{\prime }-i-1}=d_{j^{\prime }-1}.

Thus,

s^{\prime }\equiv 0 \left(\mathrm{m}\mathrm{o}\mathrm{d}{\displaystyle \frac{s+1}{\mathrm{g}\mathrm{c}\mathrm{d}\left(t_1,t_2\right)}}\right),

which implies that n\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}\frac{s+1}{\mathrm{g}\mathrm{c}\mathrm{d}(t_1,t_2)}\right), where s+1=2t_1+3t_2 and t_1, t_2 are any non-negative integers satisfying the equation.

Sufficiency: Conversely, if n\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}\frac{s+1}{\mathrm{g}\mathrm{c}\mathrm{d}(t_1,t_2)}\right), where s+1=2t_1+3t_2 and t_1, t_2 are non-negative integers satisfying the equation, it requires to find one kernel to establish sufficiency. Clearly, any subset \{k_1,k_2,\dots ,k_m\}\subseteq V\left(C_n\left(1,s\right)\right) forms a kernel of the directed cycle graph C_n(1, s), where k_{i+1}-k_i(i=1,2,\dots ,m) is either 2 or 3 (with k_{m+1}=k_1), and the sequence [k_2-k_1,k_3-k_2,\dots ,k_m-k_{m-1},k_1-k_m] follows a cyclic pattern with period \frac{s+1}{\mathrm{g}\mathrm{c}\mathrm{d}(t_1,t_2)}. Here, the “period” refers to the length of a repeating segment in a cyclic sequence of distances. That is, if \{k_1,k_2,\dots ,k_m\} forms a kernel, the corresponding sequence of distances is \left[d_1,d_2,\dots ,d_m\right], where d_i=k_{i+1}-k_i, and k_{m+1}=k_1. If this sequence forms a cyclic pattern with repeating segment \left[d_i,d_{i+1},\dots ,d_j\right], then its period is given by d_i+d_{i+1}+\cdots +d_j. The same convention applies throughout the rest of the paper and will not be reiterated explicitly.

3 Kernels of a directed cyclic graph C_n(1, s, s+1)

Theorem 3.1　(1) The graph C_n(1, 2, 3) has a kernel if and only if n\equiv 0(mod 4);

(2) Graph C_n(1, 3, 4) has a kernel if and only if n\equiv 0 (mod 7);

(3) Graph C_n(1, 4, 5) has a kernel if and only if n\equiv 0 (mod 3) or n\equiv 0 (mod 8);

(4) Graph C_n(1, 5, 6) has a kernel if and only if n\equiv 0 (mod 7) or n\equiv 0 (mod 11).

Proof　Let K=\{k_1,k_2,\dots ,k_m\} be a kernel of graph C_n(1, s, s + 1). Define d_i as the distance between the i^th and (i + 1)^th elements in K within C_n(1, s, s + 1), i.e.,

k_{i+1}=k_i+d_i\left(\mathrm{m}\mathrm{o}\mathrm{d}n\right),i=1,2,\dots ,m;k_{m+1}=k_1.

(1) For graph C_n(1, 2, 3), it is observed that the possible values for d_i are restricted to 4. If d_i takes the values 1, 2, or 3, then the set K fails to satisfy the independence condition. If d_i > 4, then K fails to satisfy the absorption condition. The cyclic sequence of distances corresponding to the kernel of C_n(1, 2, 3) consists of [4], meaning that the kernel is given by \left\{4,8,\dots ,4t\right\}, where n=4t, for t=2,3,4,\dots. Since the sufficiency is also evident, it follows that graph C_n(1, 2, 3) has a kernel if and only if n\equiv 0(mod 4).

(2) For graph C_n(1, 3, 4), similarly, the possible values for d_i are 2 and 5. Based on the independence and absorption conditions of the kernel, there is: if d_i =2, then d_{i+1}=5. Thus, the cyclic sequence of distances corresponding to the kernel of C_n(1, 3, 4) is [2, 5], meaning that the kernel is given by \{2,7,\dots ,7t+2,7t+7\}, where n=7\left(t+1\right), for t=1,2,3,\dots. Since sufficiency is also evident, it follows that graph C_n (1, 3, 4) has a kernel if and only if n\equiv 0(mod 7).

(3) For graph C_n(1, 4, 5), the possible values for d_i are 2, 3, and 6. Based on the independence and absorption conditions of the kernel, there is: If d_i =2, then d_{i+1}=6; If d_i = 3, then d_{i+1}=3. Thus, the cyclic sequence of distances corresponding to the kernel of C_n(1, 4, 5) consists of either [3] or [2, 6], meaning that the kernel is given by \left\{3,\dots ,3t\right\},n=3t,t=4,5,6,\dots or \{2,8,\dots ,8t+2,8t+8\},n=8(t+1), t=1,2,3,\dots. Since sufficiency is also evident, it follows that graph C_n(1, 4, 5) has a kernel if and only if n\equiv 0(mod 3) or n\equiv 0 (mod 8).

(4) For graph C_n(1, 5, 6), the possible values for d_i are 2, 3, 4, and 7. Based on the independence and absorption conditions of the kernel, there is: If d_i = 2, then d_{i+1}=2 and d_{i+2}=7; If d_i = 3, then d_{i+1}=4. Thus, the cyclic sequence of distances corresponding to the kernel of C_n(1, 5, 6) consists of either [2, 2, 7] or [3, 4], meaning that the kernel is given by \{2,4,11,\dots ,11t+2,11t+4,11t+11\},n=11\left(t+1\right),t=1,2,3,\dots or \left\{3,7,\dots ,7t+3,7t+7\right\},n=7\left(t+1\right),t=1,2,3,\dots. Since sufficiency is also evident, it follows that graph C_n(1, 5, 6) has a kernel if and only if n\equiv 0(mod 7) or n\equiv 0 (mod 11). □

Theorem 3.2　(1) Graph C_n(1, 6, 7) has a kernel if and only if n\equiv 0 (mod 4) or n\equiv 0 (mod 13);

(2) Graph C_n(1, 8, 9) has a kernel if and only if n\equiv 0 (mod 10) or n\equiv 0 (mod 16) or n\equiv 0 (mod 17).

Proof　Let K=\{k_1,k_2,\dots ,k_m\} be a kernel of graph C_n(1, s, s + 1). Define d_i as the distance between the i^th and the (i+1)^th vertices in K within C_n(1, s, s +1), i.e.,

k_{i+1}=k_i+d_i\left(\mathrm{m}\mathrm{o}\mathrm{d}n\right),i=1,2,\dots ,m;k_{m+1}=k_1.

(1) For graph C_n(1, 6, 7), it is noted that the possible values of d_i can only be 2, 3, 4, 5, or 8. If d_i = 1, 6, or 7, K would violate the independence condition. If d_i > 8, K will violate the absorption condition.

From the kernel conditions, it is derived:

If d_i = 2, then d_{i+1}=2, d_{i+2}=8;

If d_i = 3, then d_{i+1}=2, d_{i+2}=3;

If d_i = 4, then d_{i+1}=4;

If d_i = 5, then d_{i+1}=3, d_{i+2}=2;

If d_i = 8, then d_{i+1}=2, d_{i+2}=2.

Thus, the cyclic distance sequences corresponding to the kernel are [2, 2, 8] or [3, 2, 3, 5] or [4]. All the possible kernels are \{2,4,12,\dots ,12t+2,12t+4,12t+12\}, n=12(t+1), t=1,2,3,\dots or \{3,5,8,13,\dots ,13t+3,13t+5,13t+8,13t+13\}, n=13(t+1), t=0,1,2,\dots or \{4,\dots ,4t\},n=4t,t=4,5,6,\dots.

Since sufficiency is also evident, graph C_n(1, 6, 7) has a kernel if and only if n\equiv 0 (mod 4) or n\equiv 0 (mod 13).

(2) Similarly, for graph C_n(1, 8, 9), it is noted that the possible values of d_i are only 2, 3, 4, 5, 6, 7, or 10. If d_i = 1, 8, or 9, then K will not satisfy independence. If d_i > 10, then K will not satisfy absorbance.

According to the definition of a kernel, there is:

If d_i = 2, then d_{i+1}=2,d_{i+2}=2,d_{i+3}=10;

If d_i = 3, then d_{i+1}=2,d_{i+2}=2,d_{i+3}=3; or d_{i+1}=2,d_{i+2}=5; or d_{i+1}=3,d_{i+2}=4; or d_{i+1}=4,d_{i+2}=3; or d_{i+1}=7; if d_i = 4, then d_{i+1}=2,d_{i+2}=4; or d_{i+1}=3,d_{i+2}=3; or d_{i+1}=6; if d_i = 5, then d_{i+1}=2,d_{i+2}=3; or d_{i+1}=5;

If d_i = 6, then d_{i+1}=4;

If d_i = 7, then d_{i+1}=3.

Thus, all possible distance sequences of length s+2 within the kernel are: [3, 2, 2, 3, 3, 2, 5, 3, 3, 4, 3, 4, 3, 3, 7, 4, 2, 4, 4, 3, 3, 4, 6, 5, 2, 3, 5, 5, 6, 4, 7, 3]. This means the kernel's repeating distance cycle sequences must be one of: [2, 2, 2, 10, 3, 2, 5, 5, 2, 3, 3, 4, 3, 7, 3, 2, 2, 4, 2, 6, 4]. In other words, all possible kernels are: {2, 4, 6, 16, ..., 16t+2, 16t+4, 16t+6, 16t+16}, n=16(t+1), t = 1, 2, 3, ... or {3, 5, 10, 15, 17, ..., 17t+3, 17t+5, 17t+10, 17t+15, 17t+17}, n=17(t+1), t = 1, 2, 3, ... or {3, 6, 10, ..., 10t+3, 10t+6, 10t +10}, n=10(t+1), t = 1, 2, 3, ... or {3, 10, 13, 15, 17, ..., 17t + 3, 17t + 10, 17t + 13, 17t + 15, 17t +17}, n=17(t+1), t = 1, 2, 3, ... or {4, 6, 12, 16, ..., 16t + 4, 16t + 6, 16t + 12, 16t + 16}, n=16(t+1), t = 1, 2, 3, .... Since sufficiency is also evident, graph C_n(1, 8, 9) has a kernel if and only if n\equiv 0 (mod 10) or n\equiv 0 (mod 16) or n\equiv 0 (mod 17). □

Theorem 3.3　 For graph C_n(1, s, s + 1), the following conclusions hold:

(1) When s is an odd number, graph C_n(1, s, s + 1) has a kernel if and only if n\equiv 0 (mod s + 2) or n\equiv 0 (mod 2s + 1) or n\equiv 0 (mod 4s + 1);

(2) When s is an even number, graph C_n(1, s, s + 1) has a kernel if and only if n\equiv 0 (mod s + 2) or n\equiv 0 (mod 2s) or n\equiv 0 (mod 2s + 1).

Proof　Suppose K=\{k_1,k_2,\dots ,k_m\} is a subset of V\left(C_n\left(1,s,s+1\right)\right), where d_i represents the distance between the i^th and (i+1)^th points in K within C_n(1, s, s +1), i.e.,

k_{i+1}=k_i+d_i\left(\mathrm{m}\mathrm{o}\mathrm{d}n\right),i=1,2,\dots ,m;k_{m+1}=k_1.

(1) When s is an odd number:

If n\equiv 0 (mod 2s + 1), define K=\{2,4,6,\dots ,s-1,2s+1,\dots ,t(2s+1)+2,t(2s+1)+4,\dots ,t(2s+1)+(2s+1\left)\right\}\subseteq V\left(C_n\right(1,s,s+1\left)\right), where n=(t+1)(2s+1), t=1,2,3\dots. For such a set K, the corresponding sequence [d₁, d₂, ..., d_m] forms a cyclic sequence with period 2s + 1. The repeating segment of length 2s + 1 is [\underset{\frac{s-1}{2}}{\underbrace{2,2,\dots ,2}},s+2]Observing K, it is noted that \{2,4,6,\dots ,s-1\}\subseteq K absorbs all points not in K from the set {2, 3, 4, ..., 2s, 2s +1}, and that \{2s+1,2s+3,2s+5,\dots ,4s+1\}\subseteq K absorbs all points not in K from {2s + 2, 2s + 3, ..., 4s + 1, 4s + 2}. By extending this pattern, every point in K absorbs all points in V \ K, thereby satisfying the absorption property of a kernel. Additionally, since k_i absorbs k_i + 1, k_i + s, and k_i + s + 1, there are no arcs between any two points in K. Thus, K satisfies the independence property of a kernel. Therefore, K is a kernel of graph C_n(1, s, s + 1). Hence, when n\equiv 0 (mod 2s + 1), graph C_n(1, s, s + 1) has a kernel.

If n\equiv 0(mod s + 2), choose any K=\{k_1,k_2,\dots ,k_m\}\subseteq V\left(C_n\left(1,s,s+1\right)\right), where k_i+1-k_i\left(i=1,2,\dots ,m\right) is either 3 or 4, and the sequence [d₁, d₂, ..., d_m] forms a cyclic sequence with period s + 2. Given that s+2=3t_1+4t_2, where t₁, and t₂ are any nonnegative integers satisfying this equation. According to the definition of circulant graphs, since k_i absorbs k_i + 1, k_i + s, and k_i + s +1, there must exist an index j such that

k_j=k_i+\left(s+2\right),

where and j is an integer. Noting that when d_i = 3, i.e., k_{i+1}=k_i+3, then k_{i+1} absorbs k_i +4, k_i + s + 3 and k_i + s + 4. Thus, there is

k_{j+1}=k_i+s+5,

which implies

d_j=d_i=3.

Similarly, when d_i = 4, it follows that d_j=d_i=4. Thus, if all elements in the segment of length s+2, denoted as d_l(l=i,i+1,\dots ,j-1), take values of either 3 or 4, then there must be:

d_j=d_i,d_{j+1}=d_{i+1},d_{j+2}=d_{i+2}, \dots , d_{2j-i-1}=d_{j-1}.

Since K satisfies both the independence and absorption properties, it is a kernel of graph C_n(1, s, s + 1). Therefore, when n\equiv 0 (mod s + 2), graph C_n(1,s, s +1) has a kernel.

If n\equiv 0 (mod 4s+1), define K=\{3,5,s+2,s+7,s+9,s+11,\dots ,2s,2s+4,2s+6,3s+2,3s+8,3s+10,3s+12,\dots, 4s+1,\dots ,(4s+1)t+3,(4s+1)t+5,(4s+1)t+(s+2),\dots ,(4s+1)t+(4s+1\left)\right\}, where n=(4s+1)(t+1) and t=0,1,2,\dots. For such K, the corresponding sequence \left[d_1,d_2,\dots ,d_m\right] forms a cyclic sequence with period 4s + 1. The repeating segment of length 4s +1 is [3,2,(s-3),5,\underset{\frac{s-7}{2}}{\underbrace{2,2,\dots ,2}},4,2,(s-4),6,\underset{\frac{s-7}{2}}{\underbrace{2,2,\dots ,2}}]. Observing \left[d_1,d_2,\dots ,d_m\right], for any l\in \{1,2,\dots ,m\}, it is noted that d_l+d_{l+1}+\dots +d_{l+r}\ne 1 or s or s+1, where r = 0, 1, 2, ..., m − 1. This ensures the independence property of the kernel. Additionally, within K, based on the definition of circulant graphs: 3 absorbs 4, s + 3 and s + 4; 5 absorbs 6, s + 5, and s + 6; s + 2 absorbs s + 3, 2s + 2, and 2s + 3... Thus, all points in K absorb all points in V \ K, satisfying the absorption property. Therefore, when n\equiv 0 (mod 4s + 1), graph C_n(1, s, s + 1) has a kernel.

Similarly, it can identify other cyclic segments of period 4s + 1, such as [3,s-1,3,\underset{\frac{s-5}{2}}{\underbrace{2,2,\dots ,2}},4,s-2,4,\underset{\frac{s-5}{2}}{\underbrace{2,2,\dots ,2}}] and [s-5,7,\underset{\frac{s-9}{2}}{\underbrace{2,2,\dots ,2}},4,2,2,s-6,8,\underset{\frac{s-9}{2}}{\underbrace{2,2,\dots ,2}},3,2,2]. Thus, graph C_n(1, s, s + 1) has a kernel.

(2) When s is an even number:

Similarly, it follows that when n\equiv 0 (mod s + 2), any set {k₁, k₂, ..., k_m} forms a kernel of graph C_n(1, s, s + 1), where s+2=3t_1+4t_2, with t₁, t₂ being any non-negative integers satisfying this equation. k_{i+1}-k_i is either 3 or 4, and the sequence [d₁, d₂, ..., d_m] forms a cyclic sequence with period s + 2.

When n\equiv 0 (mod 2s), define K=\{2,4,6,\dots ,s-2,2s,\dots ,t\cdot 2s+2,t\cdot 2s+4,\dots ,t\cdot 2s+2s\}, where n=2s(t+1), and t = 0, 1, 2, ... This set K forms a kernel of graph C_n(1, s, s + 1). The corresponding sequence [d₁, d₂, ..., d_m] forms a cyclic sequence with period 2s, and the repeating segment of length 2s is [\underset{\frac{s-2}{2}}{\underbrace{2,2,\dots ,2}},s+2].

When n\equiv 0 (mod 2s + 1), K = {3, 5, s + 2, s + 7, s + 9, s + 11, ..., 2s + 1, ..., (2s + 1)t + 3, (2s + 1)t + 5, ..., (2s + 1)t + (2s + 1)} or K = {3, s + 2, s + 5, s + 7, s + 9, ..., 2s + 1, ..., (2s + 1)t + 3, (2s + 1)t + (s + 2), ..., (2s + 1)t + (2s + 1)}, where n=(2s+1)(t+1), and t = 1, 2, 3, ... This set K forms a kernel of graph C_n(1, s, s + 1). The corresponding sequence [d₁, d₂, ..., d_m] forms a cyclic sequence with period 2s +1, with the repeating segment of length 2s + 1 being [3,2,s-3,5,\underset{\frac{s-6}{2}}{\underbrace{2,2,\dots ,2}}] or [3,s-1,3,\underset{\frac{s-4}{2}}{\underbrace{2,2,\dots ,2}}]. □

Note 3.1　In graph C_n(1, s, s +1), the cyclic sequences having been found are, in fact, composed of multiple segments of length s + 2, which are then connected by multiple 2s. Since it is impossible to enumerate all segments of length s + 2 when s is very large, this method cannot establish a necessary and sufficient condition for the existence of a kernel. Moreover, for a given value of n, the periodic cyclic segments we identify are not unique. As s increases, the number of possible cyclic segments corresponding to a specific n also increases. Therefore, a better method remains to be found.

Theorem 3.4　 The necessary and sufficient condition for graph C_n(1, 2, ..., s) to have a kernel is n\equiv 0 (mod s + 1).

Proof　Let K=\{k_1,k_2,\dots ,k_m\} be a kernel of graph C_n(1, 2, ..., s), and let d_i denote the distance between the i^th and (i +1)^th points in K within C_n(1, 2, ..., s), i.e.,

k_{i+1}=k_i+d_i\left(\mathrm{m}\mathrm{o}\mathrm{d}n\right),i=1,2,\dots ,m;k_{m+1}=k_1.

For the graph C_n(1, 2, ..., s), based on the independence and absorption properties of the kernel, it is concluded that d_i can only take the value s + 1. It can obtain a cyclic segment of length s + 1 for the distance sequence corresponding to its kernel, which is [s + 1].

Conversely, if n\equiv 0 (mod s + 1), then any set \{k_1,k_2,\dots ,k_m\} forms a kernel of graph C_n (1, 2, ..., s), where k_{i+1}-k_i=s+1(i=1,2,\dots ,m), k_{m+1}=k_1. Moreover, the sequence \left[k_2-k_1,k_3-k_2,\dots ,k_m-k_{m-1},k_1-k_m\right] forms a cyclic sequence with period s + 1.

Thus, the necessary and sufficient condition for C_n(1, 2, ..., s) to have a kernel is n\equiv 0(mod s + 1). □

Theorem 3.5 [1]　 Graph C₄₃(1, 7, 8) has no kernel, but if any one of its arcs is removed, the resulting graph has a kernel.

Theorem 3.6　 For n = 43 + 435k, where k is a non-negative integer, graph C_n(1, 7, 8) itself has no kernel, but after the removal of any single arc, it has a kernel.

Proof　According to Theorem 3.5, when n = 43, graph C_n(1, 7, 8) itself has no kernel, but after removing any single arc, it has a kernel. The kernels obtained by removing the arcs (43,1), (43, 7), and (43, 8) are

K_1=\{1,5,10,14,16,19,25,28,30,34,39,43\},

K_7=\{7,9,11,13,22,24,26,28,37,39,41,43\},

K_8=\{3,5,8,14,17,19,23,28,32,34,37,43\}.

The corresponding distance sequences for these kernels are: (4, 5, 4, 2, 3, 6, 3, 2, 4, 5, 4, 1), (2, 2, 2, 9, 2, 2, 2, 9, 2, 2, 2, 7), (2, 3, 6, 3, 2, 4, 5, 4, 2, 3, 6, 3). Notably, when cyclic segments L_1=\left[6,3,2,4,5,4,2,3\right],L_2=\left[2,2,2,9\right],L_3=\left[6,3,2,4,5,4,2,3\right] are inserted k₁, k₂, k₃ (k₁, k₂, k₃ being non-negative integers) times at alternating cycle points, the existence of the kernel remains unaffected. That is, the modified sequences (4,5,4,2,3,\underset{k_1}{\underbrace{L_1,L_1,\dots ,L_1}},6,3,2,4,5,4,1), (2,2,2,9,\underset{k_2}{\underbrace{L_2,L_2,\dots ,L_2}},2,2,2,9,2,2,2,7), (2,3,6,3,2,4,5,4,2,3,\underset{k_3}{\underbrace{L_3,L_3,\dots ,L_3}},6,3) must satisfy the equation:

29k_1=15k_2=29k_3.

Thus,

n=43+\mathrm{l}\mathrm{c}\mathrm{m}\left(15,29\right)\cdot k,

where k is a non-negative integer and lcm (15, 29) represents the least common multiple of 15 and 29, i.e., when n = 43 + 435k, graph C_n(1, 7, 8) itself has no kernel, but after the removal of any single arc, it has a kernel. □

Conjecture 3.1　 For graph C_n(1, s, s + 1), when s is an odd number and n\equiv 0(mod ks + 1), where k is a positive even integer satisfying k\le 2\lfloor \frac{s+1}{4}\rfloor, graph C_n(1, s, s + 1) has a kernel.

4 Conclusion

In this paper, we have studied the existence of kernels in several special types of directed circulant graphs, characterized the existence of kernels in the graph C_n(1, s), and provided a class of counterexamples to Duchet’s kernel conjecture. However, for general directed circulant graphs, better methods are still required to characterize the existence of kernels. In the directed circulant graph C_n(W), when W contains only two elements, Duchet’s kernel conjecture may hold. At the very least, for the directed circulant graph C_n(1, s), it has been proven that this conjecture is valid for n ≤ 10⁷. The following open questions for further research are proposed in this paper:

(1) Does Duchet’s kernel conjecture hold for directed graph C_n(1, s)? See reference [1].

(2) What is the number of kernels in directed graph C_n(1, s)? See reference [10].

(3) Characterizing the existence of kernels in directed graph C_n(1, s, s +1), and analyzing the validity of Duchet’s conjecture in C_n(1, s, s + 1). Can we fully describe the class of counterexample graphs for C_n(1, s, s + 1)?

References

[1] Apartsin A., Ferapontova, E. , Gurvich, V. . A circular graph—counterexample to the Duchet kernel conjecture. Discrete Math. 1998; 178(1/2/3): 229–231

[2] Bang-JensenJ.GutinG., Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2000

[3] BergeC., Graphs, Volume 6, Amsterdam: North Holland Publishing Co., 1985

[4] Berge C. , Duchet, P. . Recent problems and results about kernels in directed graphs. Discrete Math. 1990; 86(1/2/3): 27–31

[5] Boros E. , Gurvich, V. . A corrected version of the Duchet kernel conjecture. Discrete Math. 1998; 179(1/2/3): 231–233

[6] ChvátalV., On the computational complexity of finding a kernel, Report NO. CRM-300, Centre de Recherches Mathématiques, Montreal: Université de Montréal, 1973

[7] Duchet P. . Graphes noyau-parfaits. Ann. Discrete Math. 1980; 9: 93–101

[8] Fraenkel A. . Planar kernel and Grundy with d ≤ 3, d_out ≤ 2, d_in ≤ 2 are NP-complete. Discrete Appl. Math. 1981; 3(4): 257–262

[9] Kwaśnik . The generalization of Richardson theorem. Discuss. Math. 1981; 4: 11–14

[10] ManuelP., Rajasingh, I., Rajan, B.. and Punitha, J., Kernel in oriented circulant graphs, In: Combinatorial Algorithms, Lecture Notes in Comput. Sci., Vol. 5874, Berlin: Springer-Verlag, 2009, 396–407

[11] Richardson M. . Solutions of irreflexive relations. Ann. of Math. (2) 1953; 58: 573–590

[12] Szwarcfiter J. , Chaty, G. . Enumerating the kernels of a directed graph with no odd circuits. Inform. Process. Lett. 1994; 51(3): 149–153

[13] Van LeeuwenJ., Having a Grundy-numbering is NP-complete, Report No. 207, Computer Science Dept., University Park, PA: Pennsylvania State University, 1976

[14] Von NeumannJ.. and Morgenstern, O., Theory of Games and Economic Behaviour, Princeton: Princeton Univ. Press, 1994

RIGHTS & PERMISSIONS

Higher Education Press 2025