论文部分内容阅读
图论是近几十年来发展十分迅速的一个新兴的数学分支.从古老的5个柏拉图立体开始,对称和正则图形始终是数学中最引人入胜的一个研究方向.即使是现在,这个领域仍有很多富有挑战性的问题.许多正则性质自然的表现为结合方案,其中P-多项式方案实质上就是距离正则图.
上世纪七十年代初,英国数学家Biggs首先提出距离正则图这一概念,接着他和一批数学家Gardiner,Smiths,Brouwer,Bannai和Ito等建立了距离正则图的基本理论.近几十年,距离正则图理论的研究非常活跃,并且与图论,设计理论,码论,几何论和群论都有密切的联系,是代数组合论的一个重要分支.
距离正则图的分类问题一直是距离正则图研究中的一个重要的问题.Ivanov指出距离正则图Г的直径d(Г)由价k和r(Г)的函数定界,从而为了对固定价k的距离正则图进行分类,主要的工作就在于确定r(Г)的上界.
对于一个距离正则图Г,当α1=1或c2=1时,每一个极大团的大小都为s+1=α1+2,不存在同构于K2,1,1的导出子图,从而我们可以在此情形下只考虑阶为(s,t)的距离正则图.
对于阶为(s,t)的距离正则图.t=0,1,2时,Mohar,,Ito,Biggs,Boshier,Shawe-Taylor,Bannai,Hiraki,Nomura,Suzuki和Yamazaki等数学家经过二三十年的研究,已经完全解决了.t=3时并没有太多相关分类的结论.当s=1时,阶为(1,3)的距离正则图是价为4,α1=0的图.上世纪八十年代末,Bannai和Ito证明了价为4的距离正则图的直径存在界,但当时并没有得到完整的分类.直到1999年,Brouwer和Koolen应用计算机搜索,得到了这类图的完全分类.Suzuki指出:s>1是一个限制性很强的条件,在t=3时,对阶为(2,3),(3,3),(4,3)的距离正则图的研究是很有意义的.
目前尚未解决的最小的情形就是阶为(2,3)的距离正则图,本文我们所考虑的就是阶为(2,3)并且几何围长为偶数,即cr+1>1的距离正则图的分类情况.
本文主要应用组合和代数两种方法.首先用组合方法分析交叉表中所有可能的参数,将不存在的交叉数排除,剩下有限多个仅依赖于r的交叉表的情形;第二步就是用代数方法进行相关计算,得到r的上界;再应用计算机对剩下的有限种情况一一计算,利用图特征值重数的整数性排除不可能的交叉表,从而大大压缩了直径d可能的范围,为阶为(2,3),几何围长是偶数的距离正则图的完全分类起了重大的作用。
文章共分为三章.
第一章主要介绍了有关距离正则图的基本概念,性质,以及研究背景和发展现状.
第二章利用组合方法分析了所有满足基本必要条件的交叉数,排除了不可能存在的交叉表参数,剩下的情形直径d只与r和s的大小有关.
第三章主要应用代数方法和特征值理论,针对第二章剩下的各情形计算,得到r和s的上界,从而确定直径d的范围.进一步利用计算机计算图特征值的重数,排除重数非整数的情形,为阶为(2,3),cr+1>1的距离正则图的完全分类作了必要的准备.