Abstract 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...Abstract 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 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)= $\overrightarrow {C_n }$ (j1,j2,...,jk) is defined by: V(G)={0,1,...,nm1}, A(G)={uv | vmuLj, (mod n) for 1 hihk}.In an earlier work, we investigated the digraph G= $\overrightarrow {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 rS3 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)=rS2 and sS2, then G(n,d,r,s) is a KP graph.展开更多
基金Supported by the National Natural Sciences Foundation of China (No.19831080).
文摘Abstract 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 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)= $\overrightarrow {C_n }$ (j1,j2,...,jk) is defined by: V(G)={0,1,...,nm1}, A(G)={uv | vmuLj, (mod n) for 1 hihk}.In an earlier work, we investigated the digraph G= $\overrightarrow {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 rS3 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)=rS2 and sS2, then G(n,d,r,s) is a KP graph.
