Xiao Feng GUO, Huang YI
应用数学学报(英文版). 2003, 19(1): 41-46.
An ordered circular permutation S of u's and v' s is called an ordered circular sequence of u' s and v' s. A kernel of a digraph G=(V,A) is an independent subset of V, say K, such that for any vertex vi in V\K there is an arc from v_i to a vertex v_j in K. G is said to be kernel-perfect (KP) if every induced subgraph of G has a kernel. G is said to be kernel-perfect-critical (KPC) if G has no kernel but every proper induced subgraph of G has a kernel. The digraph G = (V,A) = C_n(j_1,j_x,…,j_k) is defined by: V(G) = {0,1,…,n-1}, A(G) = {uv | v-u≡j_i (mod n) for 1 ≤ i ≤ k}. In an earlier work, we investigated the digraph G = C_n (1,±δd,±2d,±3d,…,±sd), denoted by G(n,d,r,s), where δ = 1 for d > 1 or δ = 0 for d = 1, and n,d,r,s are positive integers with (n,d) = r and n = mr, and gave some necessary and sufficient conditions for G(n,d,r,s) with r ≥ 3 and s = 1 to be KP or KPC. In this paper, we prove a combinatorial theorem on ordered circular sequences of n_1 u's and n_2 v's. By using the theorem, we prove that, if (n,d) = r ≥ 2 and s ≥ 2, then G(n,d,r,s) is a KP graph.
