ACombinatorialTheoremonOrderedCircularSequencesofn1u'sandn2v'swithApplicationtoKernel-perfectGraphs

<正> 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 vi in V\Kthere is an arc from vi to a vertex vj 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）=（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 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 n1 u's and n2 v's.By usingthe theorem,we prove that,if（n,d）=r≥2 and s≥2,then G（n,d,r,s,）is