Journal of Xinjiang University (Natural Science Edition in Chinese and English)Issue 3, (1999)
作者机构:
作者简介:
基金信息:
DOI:
CLC:O157
Published:1999
稿件说明:
移动端阅览
[1].On a Class of Kernel-Perfect and Kernel-Perfect-Critical Graphs[J].新疆大学学报(自然科学版),1999(03):1-9.
OnaClassofKernel-PerfectandKernel-Perfect-CriticalGraphs[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 1999, (3).
[1].On a Class of Kernel-Perfect and Kernel-Perfect-Critical Graphs[J].新疆大学学报(自然科学版),1999(03):1-9.DOI:
OnaClassofKernel-PerfectandKernel-Perfect-CriticalGraphs[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 1999, (3).DOI:
such that for any vertex u in VwK there is an arc from u to a vertex v in K. G issaid to be kernel-perfect(KP) if every induced subgraph ofGhas a kernel. Gis said to be kernel-perfect-critical(KPC) ifG has no kernelbutevery proper induced subgraph ofGhas a kernel. The digraph G= (V
A)= C→ n(j1
j2
…
jk) isdifined by: V(G)= {0
1
…
n- 1}
A(G)= {uv|v- u≡ji(m od n)for1ik}. In this paper
we investigate the digraph G= C→ n(1
±δd
±2d
…
…sd)
denoted by G(n
d
r
s)
where δ= 1 ford> 1 or δ= 0 ford= 1
and n
d
r
sare positiveintegers with (n
d)= r and n= m r. Itis proved thatif(n
d)= r> 2 and s= 1
then G(n
d
r
s) isa KP graph ifand only ifeither (a)m 5 or m = 3
or (b) m = 2 or4 and r isodd; and G(n
d
r
s) isa KPCgraph ifand only ifm = 2 or4 and r is even. Forthecaseofr= 2 and s= 1