A Combinatorial Theorem on Ordered Circular Sequences of n_1 u's and n_2 v's with Application to Kernel-perfect Graphs

Abstract An ordered circular permutation S of u's and v's is called an ordered circular sequence of u's andv's.A kernel of a digraph G=(V,A)is an independent subset of V,say K,such that for any vertex v_i in V\Kthere 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 Ghas a kernel. G is said to be kernel-perfect-critical(KPC)if G has no kernel but every proper induced subgraphof G has a kernel.The digraph G=(V,A)=(j_1,j_2,…,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 eariler work, we investigated the digraph G=(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 necessaryand 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 usingthe theorem,we prove that,if(n,d)=r≥2 and s≥2,then G(n,d,r,s,)is

A Combinatorial Theorem on Ordered Circular Sequences of n_1 u's and n_2 v's with Application to Kernel-perfect Graphs