一致与非一致复杂类的模型论性质

自从1965年J.Edmonds和A.Cobham提出P-NP问题以来已有30年的研究历史。目前环绕这个问题的大量学术论文和研究专著已使它发展成为计算机科学中最新和最活跃的研究领域之一,近年来,人们除了对由各种类型的图灵机确定的复杂类(如P,NP,PSPACE等)进行研究外,对一些用其他方法定义的非一致复杂类(如P/poly,P/log,NP/poly等)也越来越有兴趣,而且许     

完全图的循环分解与分划广群

本文使用A.Kotzig引进的分划广群的概念证明了关于完全图循环分解的下列结果。 1.如n为奇数,s为正整数,则完全图K_ns可以分解成边相离的长为n的循环的和。 2.如n_1,n_2…,n_k为奇数n的所有异于1的正因子,则K_n可以分解成边相离的长为,n_1,n_2…,n_k的循环的和。 3.如K_m可以分解成边相离的长为h的循环的和,K_n可以分解为边相离的长为k的循环的和,则K_(mn)可以分解成边相离的长为h,k,d的循环的和。其中d是h与k的最小公倍数。     

正则图的同顶平衡二部子图——关于R·Hggkvist猜测

本文给出了R·Hggkvist猜测的反倒。(让G是有偶数个点的m—正则图,则G含有同顶平衡二部图B.使d_B(v)≥[m/2],对一切v∈V (G))。当修改了原猜测之后,我们证明了当m≤3时,修改后的猜测是正确的。     

关于完全图的循环分解

本文给出关于将完全图分解成边相离的循环的和的几个结果。     

关于图的边色数的临界性

本文给出图的边色数的四种临界概念,并研究它们之间的相互关系。