A combinatorial theorem on ordered circular sequences of n1 u's and n2 v's with application to kernel-perfect graphs

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 VK there is an arc from vi to a vertex vj 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(j1,j2,⋯,jk) is defined by: V (G)={0,1,⋯,n-1}, A(G)={uv | v-u≡ji (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 n1 u's and n2 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. © Springer-Verlag 2003.