（基础数学专业论文）关于a＞2cr11且型为（a13）的距离正则图.pdf

摘要 本文利用距离正则图的交叉表，研究了直径为d 且o 2 ，c r + 。= 1 的型为 缸+ l ，3 ) 的距离正则图，得到了该图的一些局部性质和参数间的一些关系主 要结论如下： 定理1 设r = ( v r ，e r ) 是直径为d 且型为( n + 1 ，3 ) 的距离正则图，如果 n 2 ，c r + - = 1 ，则子图g + 2 不是余团 定理2 设r = ( v r ，e f ) 是直径为d 且型为 o 2 ，c r + l = 1 ，则子图g + 2 j o ( 1 m d + 1 ) 定理3 设r = ( v f ，e f ) 是直径为d 且型为 口 2 ，c r + 1 = 1 ，则c r + 2 1 ，2 ，3 ( 口+ l ，3 ) 的距离正则图，如果 ( 口+ 1 ，3 ) 的距离正则图，如果 定理4 设r = ( v r ，e r ) 是直径为d 且型为( 口+ i ，3 ) 的距离正则图，如果 o 2 ，臼+ l = 1 ，则6 r + l 1 关键词：距离正则图，交叉表，团，点邻域 d i s t a n c e - r e g u l a rg r a p ho fo r d e r ( a + 1 ，3 ) w i t ha 2 a n dc r + 1 1 a b s t r a c t i nt h i st h e s i s ，b ym e a n so fi n t e r s e c t i o nd i a g r a m s ，w es t u d yt h ep r o p e r t i e so ft h e d i s t a n c e - r e g u l a rg r a p hw i t hd i a m e t e rda n do r d e r ( a + 1 ，3 ) w eo b t a i ns o m el o c a lp r o p - e r t i e s o f t h i s t y p e g r a p h z a t d s o m er e l a t i o n so f i n t e r s e c t i o n n u m b e r s i f a 2 a n d 岛囊21 ， w eg e tt h er e s u l t s8 8f o l l o w s t h e o r e m1 l e tr = ( y r ，e f ) b ead i s t a n e e l - r e g u l a rg r a p hw i t hd i a m e t e rda n d o r d e r ( a + 1 ，3 ) i f a 2a n dc r + l = l ，t h e nt h es u b g r a p h ( i + 2i sn o tac o c l i q u e t h e o r e m2 l e tr = ( v f ，e f ) b cad i s t m i c e - r e g u l a rg r a p hw i t hd i a m e t e rda n d o r d e r + 1 ；3 ) i f 口 2a n dc r + 1 = 1 ，t h e nt h es u b g r a p hc r + 2 k ( 1 m a + 1 ) t h e o r e m3 l e tr = ( v f ，e r ) b ead i s t a n c e - r e g u l a rg r a p hw i t hd i a m e t e rda n d o r d e r ( a + 1 ，3 ) i f n 2a n da r + l 一1 ，t h e n 岛+ 2 1 ，2 ，3 t h e o r e m4 l e tr = ( v f ，e f ) b ead i s t a n c e - r e g u l a rg r a p hw i t hd i a m e t e rda n d o r d e r 缸+ 1 ，3 ) i f a 2 a n dc r + 1 1 ，t h e n6 r + l 1 k e y w o r d s ：d i s t a n c e - r e g u l a rg r a p h s ，i n t e r s e c t i o nd i a g r a m s ，c l i q u e s ，v e r t e xn e i g h b o r - h o o d s 2 0 关于n 2 辞+ 】= 1 且型为( 口+ 1 ，3 ) 的距离正则囤 第一章绪论 1 1 课题背景与发展概况 二十世纪七十年代，英国数学家n l b i g g s 提出了距离正则图的概念1 6 1 接着他与一批数学家a e b r o u w e r ，d h s m i t h ，t i t o ，e b a n n a i 和a d g a r d i n e r 等建立了距离正则图的基本理论框架另一方面，距离正则图在解决码论中 二 的问题时得到了应用，p h d e l s a r t 研究了p - 多项式方案 1 8 】，7p 一多项式方案 实质上就是距离正则图因此，从某种意义上可以说距离正则图等价于只多 项式方案【1 】? 在最近的几十年，距离正则图得到了广泛的研究，它在诸如有限群，网络、 扭结不变量、编码、设计和有限几何等方面都有密切联系，已成为代数组合 论的一个重要分支 距离正则图可以看作是秩为1 的对称空间的离散化，而秩为1 的对称空间 是2 - 点齐次空间在距离正则图的定义中，尽管我们只假设组合正则性，而 没有考虑自同构群作用的对称性，但是大多数距离正则图有足够大的自同构 群，使得它在距离相等点对集合上的作用是传递的因此有人把距离正则图 称为“无群的群论”f 7 】 在对距离正则图的研究中，重要问题是对其参数性质及特征的刻划，但人们 对一般性的讨论比较困难，所以在讨论距离正则图时大多是加一定条件的 比如：具有固定价的距离正则图【8 1 1 】，参数具有某种性质的距离正则图等 【3 5 ，1 4 1 对于型为( s ，f ) 的距离正则图，我们知道对任意的n f 有r ( n ) 2 ( h 1 ) 虬 下面我们介绍以下与本文有联系的距离正则图的研究情况 关于d 2 c r + l = 1 且型为( n + 1 ，3 ) 的距离正则图2 1 9 8 5 年，b m o h a r 和j s h a w e - t a y l o r 证明出了型为( 毛1 ) 的距离正则图是线 图，并对此类图作了分类【6 】 二十世纪八十年代，n l b i g g s ，a g b o s h i e r ，j s h a w e t a y l o r 讨论出了在型 为( 1 ，2 ) ，o = 0 的情况下正则图的分类【1 5 e b a n n a i 和t i t o 证明出了在同构 意义下，度为3 的距离正则图只有1 3 个，从而型为( 1 ，2 ) 的距离正则图也得到 了完全分类【9 ，1 9 ， n y 抽a z a k i 证明出在s 3 情况下，型为( s ，2 ) 且d ( r ) r ( r ) + 3 的距离正 则图是度为3 的距离正则图的距离一2 图【l7 】 a h i r a k i ，hs u z u k i 和k ，n o m u r a 对型为( 2 ，2 ) ，即k = 6 ，n = 1 的距离正则图 进行了完全分类，并且证明出在同构意义下，型为( 2 ，2 ) 的距离正则图只有4 个【4 j 步玉恩在2 0 0 4 年的河北师大硕士论文中对备+ - = 2 ，3 且( o + 1 ，3 ) 型的距离 正则图进行了讨论，得到了许多重要的结果f 2 0 j 本文对o 2 ，c r + l = 1 且( a + 1 ，3 ) 型的距离正则图进行讨论，得出了这类 图的一些性质 1 2 本文内容简单介绍 本文共分4 章第1 章阐述了课题背景及发展概况第2 章为预备知识，着 重介绍了后面章节中要用到的一些符号、概念和基本结论第3 章介绍了型 为( o + 1 ，3 ) 的距离正则图的若干基本性质和交叉表第4 章利用交叉表讨论 了型为( a + 1 ，3 ) 的距离正则图，在n 2 ，c ，+ - = 1 条件下，得到了如下结果： 定理1 设r = ( v f ，e f ) 是直径为d 且型为( a + 1 3 ) 的距离正则图，如果 关于口 2 c r + j = 1 且型为( n + 1 3 ) 的距离正则图3 a 2 ，c r + l = 1 ，则子图口+ 2 不是余团 定理2 设r = ( v f ，e f ) 是直径为d 且型为 a 2 ，g + l = 1 ，贝u 子图( 弄+ 2 匠。( 1 竹lsn + 1 ) 定理3 设f = ( v f ，e f ) 是直径为以且型为 a 2 ，臼+ l = 1 ，则o + 2 1 ，2 ，3 ( a + 1 ，3 ) 的距离正则图，如果 ( a + 1 ，3 ) 的距离正则图，如果 定理4 设r = ( v r ，e r ) 是直径为d 且型为m + 二1 ，3 ) 的距离正则图，如果 a 2 ，c r + l l ，则6 r + l 1 关于a 2 c r + 1 = 1 且型为( a + 1 ，3 ) 的距离正则图4 第2 章预备知识 本章我们主要介绍距离正则图的基本概念和基本性质 2 1 距离正则图的基本概念 下面我们给出距离正则图的定义和习惯记号关于距离正则图的其它知 识，读者可参考专著【1 】 定义2 1 设a ，b 是两个集合，由a a ，b b 所组成的形如( a ，6 ) 的所有有 序对构成的集合，称为a 和b 的笛卡积或直积，记作a b 定义2 2 设a ，b 是两个集合，由a a ，b b 所组成的无序对构成的集 合，称为a 和b 的无序积，记作a & b 定义2 3 一个图定义为一个偶对( x ，e ) ，记作f = ( x ，层) ，其中 ( a ) x 是一个集合，其元素称为顶点； ( 2 ) e 是无序积x & x 的一个子集合，其元素称为边 我们常用y r 表示图r 的顶点集合x ，e i 表示图r 的边集合e 如果y r 和 e f 都是有限集合，则称r 为有限图，否则称为无限图 在本文中我们所讨论的图恒假定为有限的 定义2 4 设f = ( x ，e ) 是一个图图r 的两个顶点牡和w 叫做邻接的，如 果u e ，记为“一饥否则，“和可叫做不邻接的，记为“” 设t l 和”是图r 的两个顶点： ( 1 ) 图r 中从顶点u 到顶点t ，的长为l 的一条途径是r 中z + 1 个顶点序列 。一撕，w l ，w l = t ，) 使得 “2 蛳g u l 。+ u 一口 关于口 2 c r + j = l 且型为( 口+ 1 3 ) 的距离正则图 5 ( 2 ) 图r 的一条途径( t = “t 一，枷一 ) 称为道路，如果对任一个 ( = 1 ，l 一1 ) ，都有 。一1 坝+ 1 一条道路( u w 0 ，伽l i 一，铆= v ) 称为约简的，如 果对任一个i 0 1 ，j ，z 一1 ) 都有毗一l 与毗+ l 不邻接 ( 3 ) 图r 中的顶点u 和”的距离是r 中连接u 和”的最短路的长，记为 o ( u ，”) 如果在i 中不存在连接“和”的路，那么规定o ( u ，”) = o o ( 4 ) 一个图r 叫做连通的，若对r 中任意两个顶点“和”，在r 中都有连接 和”的道路 ( 5 ) 图r 的直径是r 中任意两点间距离的最大值，记为d = d ( r ) 定义2 5 一个图r = ( x ，e ) 中，两个顶点相同的边叫做环；两条具有相同 端点的边叫做重边即无环又无重边的图, t t q 吱简单图 定义2 6 ，一个图r 叫做一个团，如果它的任意两个顶点是邻接的有。个 顶点的完全图( 团) 我们用玩表示一个图r 叫做一个余团，如果它的任意 两个顶点都不是邻接的 定义2 7 设”y r ，r 中与顶点t ，关联的边的数目称为”的度或价，如果一 个图的每一个顶点都具有相同的度，则称这个图是正则的每个顶点的度均 为k 的正则图，称为k 一正则图 定义2 8 设a ，bcx ，定义o ( a ，b ) = m i n o ( x ，) p a ，y b 定义2 9 一个直径为d 的连通图f = ( x ，e ) 称为距离正则的，如果对r 中 任意两个距离为z 的点“和”，1 只，( u ，”) 1 只与l ，j 和z 有关，而与“，t ，x 的选 取无关，其中0 ，j ，f d 设r 是个直径为d 的距离正则图记一j = 1 只，( u ，t f ) i 称。为r 的交叉 数，其中0 i ，j ，d 特别记 关于a 2 ，e , - + l = 1 且型为( 口+ 1 ，3 ) 的距离正则图 6 q = p i 卜1 ( 1 i d ) ，a t 一研 ( 0 t d ) ，如= 硝。+ i ( 1 l d 一1 ) 对r 中任意两个距离为t 的点“和v ( osi d ) i 定义 c ( u ， ) = a ( u ， ) = r i l ( u ) n r ( t ，) ， a ( u ， ) = = a t ( t ， ) = f ( “) n r ( 口) ， b ( u ，1 3 ) = 最( ， ) = r i + l ( ) n r ( ) 则显然有 q i g ( u ， ) l ，口。= = i a t ( 缸，”) l 和坟= i b i ( u ，v ) 1 。 我们把c i ，啦，玩叫做r 的交叉数 ， 定义2 1 0 对o ，z f ，a ( n ，z ) = l ，我们称 n 一，( a ) i q r ( x ) 是关于( 口z ) 的g 图，有时也将其记做g ( 口，z ) ； r l ( a ) n r ( x ) 是关于( 口) 的a 图，有时也将其记做a ( n ，童) ； n + 一( a ) n r ( x ) 是关于( o ，z ) 的最图，有时也将其记做最( 口，z ) 并且记q ( o ，x ) = f c ：( 口，z ) i 吼( n ，z ) = i 4 ( 口，z ) i ，6 l ( n ，z ) 一f 最( 口，茁) j 定义2 1 1 我们称 印，= 融叠 c d 0 , d 木 关于n 2 c r + l = 1 且型为( n + 1 3 ) 的距离正则图7 例如，考虑立方体q 。，它是一个直径为3 的距离正则图，由图2 1 ，其交叉 阵列为。( q 3 ) 卦 2 2 距离正则图的基本性质 我们将介绍距离正则图的交叉数的一些基本性质 命题2 ，1 2 ( 1 1 】) 设r 是个直径为d 的距离正则图令一艘；，那么我们有 下述结果 ( i ) p l ，“l = 臼，硝，。= a 且西，件l = 玟( i = 0 ，1 ，t ，d ) ( 2 ) 程，j = 0 ，如果l i + j 或歹 i + l 或。 j + f ( 3 ) 硅，= 砖i ( o t ，j ，k d ) ( 4 ) 岛p ；，l = 白f il 一岛疵 命题2 1 3 ，( 【1 】) 设r 是一个直径为d 的价为k 的距离正则图那么 ( 1 ) k = g + b i + 吼( i = 0 ，l ，- 一，d ) ( 2 ) c o = n o = “= 0 ，c 1 = 1 且b o = k ( 3 ) 令k i ：= 嫂f 则5 ；岛一铒1 赶+ l ( = 0 ，1 ，- ，d 一1 ) ( 4 ) c lsq + 1 目6 l 岛+ t ( 0 isd 一1 ) ( 5 ) 6 l 白，如果t + j d ( 6 ) 设札和u 是r 的两个点且w c ( v ，) 那么c ( w r ) cc ( u ，t ) 且且( ，r ) ) b ( u ，”) 2 0 l l o 2 0 3 = ) 3q( 关于a 2 ，c r + 1 = 1 且型为( + 1 3 ) 的距离正则图8 ( 7 ) 设“m r 如果 曲( “，t ，) = o r ( t l ，叫) + o r ( 叫，u ) 秀5 么g ( u ， ) cb ( v ，”) ( 8 ) b ，如果0 i j 且i + j d ( 9 ) 这些也具有单峰性，即存在整数h 和l ( 1 h 冬z d ) 使得 1 = k o k i 1 ( 1 0 ) 设0 t 2 c r + l = 1 且型为( 口十1 ，3 ) 的距离正- j l 图9 若叼= d ，则去掉这个点集由定义我们有如下结果 ( 2 ) q 和d ：之间无边，如果l i p l l 或i s 一口l 1 在本文，为了叙述方便，我们把“关于边( a ，p ) 的交叉表”记成“( o ，口) 表”， 恤阌f 污j ：菊一。：豸矜： 巧( n ，卢) 命题2 1 4 【2 】在每个( 口，) 表中，如果。删且y d ；+ 1 ( 0st d 一1 ) ，那么 ( 1 ) e ( z ，n i 一1 ) + e ( x ，d ；一- - 1 1 ) = a t ( 2 1e ( z ，d ；+ 1 ) + e ( z ，d i ) + e ( 。，d 一1 ) = a t ( 3 ) e ( z ，d 0 1 ) + e 扛，d t + t + 1 1 ) = 6 t ( 4 ) e ( u ，d ；+ 1 ) + e ( y ，磁) + e ( y ，d ：一1 ) = c a + t ( 5 ) e ( ，d ：+ 1 ) + e ( 可，五：；) 一n t + 1 ( 6 ) e ( u ，纠t + + 2 1 ) = b l + 1 ( 7 ) e ( u ，d ；一i ) 一岛 关于a 2 c r + l = 1 且型为( 口+ 1 ，3 ) 的距离9 - j i , l 图 l o ( 8 ) e ( y ，d ；) + e ( y ，删“) = ( 9 ) e ( ，d t t + + 2 1 ) + e ( v ，d f t + + 1 1 ) + e ( v ，d ；+ 1 ) = b t ( 1 0 ) e ( z ，o i + 1 ) = e ( z ，d l + 1 ) ( 1 1 ) p ( z ，磁一1 ) = e ( 茁，谚- 1 ) ( 1 2 ) c t c t + l 当且仅当e ( d f + l ，捌) 一e ( d ：+ l d i + 1 ) = 0 ( 1 3 ) 6 l = b t + 1 当且仅当e ( d ：+ 1 ，删+ 1 ) = e ( d t + l t + l ，d ；+ 1 ) = 0 ( 1 4 ) d ；= o 当且仅当a t = 0 关于n 2 ，c ，+ 1 = 1 且型为( 口+ 1 ，3 ) 的距离正则圈 1 l 第3 章关于型为( a + 1 ，3 ) 的距离正则图 3 1 型为( 口+ 1 ，3 ) 的距离正则图的若干性质 命题3 1 2 0 j 设r = ( v f ，e v ) 是一个直径为d 且型为( a + l ，3 ) 的距离正则 图则对任意n ，f ，且n ，有d 是团 对固定的顶点n ，显然有l 研i a ，令d = ( - y 。，他，) 命题3 2 ，【1 7 设r = ( 矿r ，e r ) 是一个直径为d 且型为( o 十1 ，3 ) 的距离正则 图，则下列( 1 ) ( 5 ) 成立 ( 1 ) e ( 巧，删) = e ( 硝，联二 ) = e ( 巧，鼋一。) = e ( d t - d t ) = e ( 谚一l ，谚二i ) = 0 ( 2 i r ) ； ( 2 ) 设z ，y e q “，且j 彰一1 ( 1g r ) ，如果y z 。，则y 蜀 ( 3 ) e ( 研，d ：“) = e ( 研，研+ 1 ) 一o ； ( 4 ) 每个口+ t 图是一个余团； ( 5 ) 如果c r + l = 1 ，则e ( d r + 1 ，研“) 一0 tci，=；。+。，；。+。，；j!：1+。，三：!j!； 关于n 2 ，o r + l = 1 且型为( n + 1 3 ) 的距离正则图 1 2 再由南定义知，n 脚= n 3 2 型为( 口+ 1 ，3 ) 的距离正则图的交叉表 如果c r + l = 1 ，则交叉表如图3 1 所示 缸1 乒 ，) ；瑞d 一一研一l 图3 1 口 关于口 2 。岛+ j = l 且型为( a 十1 ，3 ) 的距离正则因1 3 第4 章 关于o 2 ，白+ t 一1 且型为( n + 1 ，3 ) 的距离正则图 本章主要证明下面的定理 定理1 设f = ( v r ，e r ) 是直径为d 且型为( o + 1 ，3 ) 的距离正则图，如果 a 2 ，白+ l = 1 ，则子图g + 2 不是余团 定理2 设f = ( v r ，e f ) 是直径为d 且型为( a + 1 ，3 l 的距离正则图，如果 a 2 ，臼+ 1 1 ，贝q 子图c i + 2 ；( 1 m a + 1 ) 定理3 设f = ( v f ，e f ) 是直径为d 且型为( a + 1 ，3 ) 的距离正则图，如果 a 2 ，c r + l = l ，则c ，+ 2 1 ，2 ，3 定理4 设f = ( v f ，e f ) 是直径为d 且型为( a + 1 ，3 ) 的距离正则图，如果 口 2 ，c r + l 一1 ，则6 r + l 1 要证明上述定理，我们先证下面几个引理 引理4 1 设f = ( v f ，e f ) 是直径为d 且型为( a + 1 ，3 ) 的距离正则图，其中 a 2 ，c r + l = 1 ，则任意z 研r + 1 ，+ l 都有e ( z ，研) 1 进一步，在职i 中存在点蜀 使得e ( x ，研) = 0 证明由c r + t = 1 ，可以直接得到e ( z ，研) 1 下面证明在璐 中，存在点叠使得e ( z ，研) 一0 若不然，设不存在这样的点z ，使得e ( z ，珥) = 0 也就是说，对任意的y d ：r 。+ l 一定有e ( 3 ，研) = 1 因为c r + l 一1 ，故e ( s ，研+ 1 ) 一e ( y ，研+ 1 ) = 0 即e ( 巧+ 1 ，群r + + 1 1 ) 一 e ( 研一，彤髫) = 0 则交叉表如图4 1 所示 关于d 2 ，c r + 1 = 1 且型为( 口+ 1 3 ) 的距离正则图1 4 伽瑚f i 、n 芒j ：1 0 y 菘, 隔i n 7 + ：d - - i 套。d i 一蚱一蟛陟弋7 弋眵。 p ) = 础d 2 一一研一- _ 睇+ 1 d ：；卜一 一讲一i 图4 1 再由命题2 1 4 ( 1 2 ) 与( 1 3 ) ，有c r + l = c r ，口r + l = n r ，“+ l = 6 r ，与r 的定义矛盾口 由引理4 ，1 ，我们可以将研嚣分拆成a 和b ，其中 a = z d ，r + + l l l e ( z ，d ；) ：= 1 ，e ( x ，d r + 1 ) 一e ( x ，d ：+ 1 ) = o ) b = 扣d t m e z ，d ：) = 0 ，e ( x ，d r + 1 ) = e ( x ，d ：+ 1 ) 一1 ) 并且a o ，b 毋，a u b 一。d ；r + + 1 l ，a n b = ；毋 由e ( 研r + l + l 研) = e ( a ，缉) = i a i e ( 研，研r + + l t ) = i d 0 1 6 r ，我们得到 k l a i = k l d ：1 b , - 一辟口，6 r = 辟+ 1 0 + l n ，= a 肆+ l ( 1 ) k l b i = 七l 珥r + + l l i k l a i k + l n ，+ l a k r + l = o r + l ( 口，+ i n )( 2 ) 任意选取z a ，因为l g + - ( z 刮一1 ，所以对于任意z a ，有j i r w - - 4 点 d ( 口p ) ，使得a ( z ，乍) = r ，从而任意d l ( a ，p ) d i ) ，a ( 7 j ，z ) = r + 1 为后面证明的需要，我们再定义 a i = x l x a ，a ( ：r ，乍) = r ) o = 1 ，2 ，o ) 贝 a 1u a 2 u u 也= a 且任意f a ，o ( z ，7 j ) = r + l ( i j ) 引理4 2 设f = ( v r ，e f ) 是直径为d 且型为( n + 1 ，3 ) 的距离正则图，其中 关于口 2 ，c r + 1 = 1 且型为( 口+ 1 ，3 ) 的距离j r - 且 l 图 1 5 h 卜彳乒j ! 葶买隰：哭碜 ) = 础一- d 一一筝一t 1 珥+ 1 力；丰卜一础一1 z l ，暑，l ，z 1 ) ，其中z l d ；+ l ，y l d r ，+ + 2 l ，z l d ；丰j x 2 ，妇，勿) ，其中z 2 d r + r + l l ，y 2 d ，r + + 2 l ，钇d 耸 关于n 2 ，c r + l = 1 且型为( n + 1 ，3 ) 的距离正则图 1 6 ( 4 ) a _ ，蛐，z 4 。 ，其中z 4 d ，r + + l l ，y 4 d ，r + + 2 l ，z 4 d ；r + + 1 1 ( 5 ) z 5 ，y s ，磊) ，其中z 5 d ，r + + l l ，y s d ，r + + l l ，z 5 d ，r + + 2 2 证明( 1 ) 若不然，假设存在团 x l ，y l ，z - ) ，其中z ，d ：+ l y l 研箍 z l 研r ”+ l 则z 1 ，。1 g + 2 ( p ，鲈1 ) 且z l z l ，与g + 2 图是余团矛盾 参见下图4 , 3 交叉表： n 卜彳乒! ! 葶买隰：哭诊 言r ( y ) n r ( 功b 否则，若存在z r ( y ) n f ( x ) n a 由引理4 2 ( 1 ) 知，z ，z 臼+ l = 1 知，r ( y ) n r ( 剪1 ) n 研+ l = 0 ；由引理4 3 ( 1 ) 知，r ( y ) n r ( y 1 ) nd r 书= o 故 r ( 剪) n r ( y 。) 研r + 1 + l 同理r ( y ) n r ( 2 ) d r r ”+ l 进一步，由a ，b 型点定义知道， 关于n 2 。c r + l = 1 且型为( n + 1 ，3 ) 的距离正则图1 7 故耳+ 1 ( n 。y ) 研r + 2 ，+ 2 研+ l ( ，) 研r + 2 ，+ 2 所以对此y b ，y 的邻域结构如图4 4 u 一 暑， j o d ：( z ，分) b 团4 ，4 由图4 4 知道，e ( s ，a ) 1 口 引理4 5 设f = ( v f ，e f ) 是直径为d 且型为( a + 1 ，3 ) 的距离正则图，其中 口 2 ，c r + t 一1 ，若g + 。是余团，则任意z a ，有e ( z ，珲嚣u 璐2 ) = 0 ， 证明 若不然，设z a ，。群r + 2 + lz z 不妨设$ a l ，则a ( z ，y 1 ) 一r ， a ( ：，一y 1 ) = r + 1 所以一r l 珥+ l ( 茁，名) ，d d ，r + + l l ( z ，：) ，p 研嚣( 。，。) ，、并且 口：，y 1 ) 是团与引理4 ，3 ( 1 ) 矛盾 口 引理4 6 设f = ( v f ，e l ) 是直径为d 且型为( a + 1 ，3 ) 的距离正则图，其中 口 2 ，岛+ l 一1 ，着d + 2 是余团，则e ( a ，b ) = 0 证明若不然，设存在y b ，z a ，z y ，则y 的邻域结构如上图4 4 所 示由距离正则图定义，脚+ ，的大小与点的选取无关，故n r + l = n r + ，( n ! ，) ，由 图4 4 可得，n ，+ l = ( n + - ) + ( n + 1 ) + a = 3 a + 2 由引理4 5 ，任意z a ，e ( z ，珥r + + 2 lud r r + + 1 2 ) = 0 ，从而a r + l ( n ，z ) 研r + l ，+ l 又由引理 4 2 ( 2 ) ，e 仁，a ) = a ，所以e ( z ，b ) = a ，+ l a = 3 a + 2 一a = 2 ( a + 1 ) 由( 1 ) 式有 k e ( a ，b ) = k 2 ( n + 1 ) i aj 一2 ( a + 1 ) a b + l ( 3 ) 关于n 2 ，c r + 1 = 1 且型为( a - i - 1 ，3 ) 的距离正则图 1 8 由引理4 4 ，任意y b ，e ( 剪，a ) 1 ，再由( 2 ) 式，有 a ，e ( $ ，d 冀i u 研r + + 2 i ) ：0 ，由引理4 6 知e ( a ，b ) = 0 但任意z a ，“+ l ( ，z ) 三 e ( x ，研r + + 1 1 ) + e ( z ，研+ 1 ) + e ( z ，研r 十+ 2 1 ) = e ( x ，研r + + 1 1 ) = e ( z ，a ) = a ，矛盾 口 珥冀，l r ( z ) n d o l i = 1 ，而g + 2 ( 卢，z ) ! k m ，e ( a ，研+ 。) = 0 ，e ( 研+ i ，研r + + ，2 ) = 0 ，故 因为任意的z d r + 1 d i ，有a ( 。，m ) = r + l ；任意y b ，o ( y ，) r + 1 ，所 以8 ( z ，乍) 一r + 2 即d 4 + z ( ：；l ：，) 注意到r t g + 2 ( z ，所，如果g + 2 0 ，p ) 与n 形成团的话，则必定有d 中的点与n 构成团，这是不可能的如图4 5 扛声i = j ! 孺! 髯。s i 。- k ：d d - 1 - - - l _ _ d 。d i 容彳么 f 夕2 ，厂一研夕鞲、7 i “ 故若g + 。= ，则m = 1 ，即图是余团，又与定理1 矛盾，故g + 。k , n 口 推论1 设r = ( v r ，e r ) 是直径为d 且型为( 8 + l ，3 ) 的距离正则图，其中口 2 ， 关于1 7 , 2 c r + 1 = 1 且型为( + 1 ，3 ) 的距离正则图 1 9 证明若不然，则g + 222 k l 或g + z ! 鲍若g + 2 = 2 k l ，则g + 2 图是余 团，与定理1 矛盾若g + 21k 2 ，与定理2 矛盾 口 推论2 设r = ( v i ，e l ) 是直径为d 且毽! 为( o + 1 ，3 ) 的距离正则图，其中o 2 ， c r + l = 1 ，若c r + 2 = 3 ，则c i + 22j 毛u k l 证明因为白+ 2 3 所以g + 21k 2 u k l 或g + 213 k 1 或g + 2 = 蚝若 g + 223 k 1 ，则g + 2 图是余团，与定理l 矛盾若g + 22 恐，与定理2 矛盾。；口 。 ，一： 推论3 设r = ( y r ，五町是直径为d 且型为( o + 1 ，3 ) 的距离正则图，其中a 2 ， c r + 1 = 1 ，岛+ 2 = 3 ，则e ( a ，b ) 一0 从而任意y b ，任意，y d ，有0 ( y ，7 ) = r + 2 证明 因为e ( a ，d ，r + 1 ) = 0 ，r ( z ) 14 + l 所以任意y b ，e ( y ，a ) 2 ，即 至多和2 个d 中点的距离为r + 1 因为a 2 ，所以存在7 d ；，o ( u ，y ) = r + 2 若y z a ，不妨设z a l = r r ( 7 1 ) n 研扎则y f r + l ( 7 1 ) 设y y l l ，考虑 ( y ，y 1 ) 多芝叉习毫贝qa d ；+ l ( l ，量，) ，p d ，r + + l l ( 耋，1 ，暑，) ，y l d ，r + + 1 l ( 可l ，可) ，7 ，d ，r + + 2 l ( 秒l ，) ， 所以n ，m g + 2 ( ，y 7 ) ，并且 n p ，饥 是一个团，与g + 2 恐矛盾所以 e ( a ，b ) = 0 从而任意y b ，任意7 d i ，有o ( u ，7 ) 一r + 2 r - 1 定理3 的证明 由定理2 和推论2 1 知道，岛+ 2 1 ，白+ 2 2 ，下面要证明的是c r + 2 3 证明任取z 研+ l ，因为脚( a ，$ ) 一口，所以i r ( x ) n 研+ 。i = a 而脚+ 1 ( p ，z ) = i r ) n d ；+ l i + l r ( z ) n d r + r + l l i = a + l r ( z ) n d r + r + l l i ，所以i r ( z ) n d 冀 f ；口，+ l 一口由弓l 理3 3 ，l r ( z ) n d r + r + 1 lj 0 设z 研+ l y ，。研 ie l f ( x ) ，我们断言y 。若不然，假设y z 考虑 ( z ，y ) 交叉表，我们有r t d 0 。( z ，! ，) ，f l e 研革 ( z ，掣) ，并且z y ，所以，b ( z ：可) ， 。d ；( z ，) ，a ( 口。) = r + 1 与推论2 3 矛盾因为e ( z ，d ，+ l r + 1 ) = o r + l o ，并且 关于n 2 ，c r + l = 1 且型为( 口+ l ，3 ) 的距离正则图2 0 r ( x ) 24 k + l ，所以嘶+ l a + 3 断言n r + z o + 3 ，否则，任取z r ，- ( o ) ，令 = r ( 功n r ，( o ) ，e = r ( z ) n r ( x ) n r r + l ( d ) ，r 徊) n r ，+ 2 ( q ) = e l u 易u e 3 ， z l ，2 2 ，2 3 = ( r ( z ) nr r + l ( 口) ) e 则x 的邻域结构如图4 6 ，4 7 ，4 8 之一( 和。距离) 若有图4 6 ，则任取y e 1 ，有y r r + 2 ( 口) ，且缸，z i ，z 2 ，z 3 ，g + 2 ( 口，矿) ，与 4 + 2 = 3 矛盾 r r + 1r + 2 z o 若有图4 8 ，则任取y r m ( “) ，g + 21 l 恐与c r + 2 = 3 矛盾 关于n 2 ，c r + l = 1 且型为( a + 1 ，3 ) 的距离正则图2 1 r + 2 图4 8 所以口r + i = a + 1 或a r + l = a + 2 下面证明在臼+ 2 = 3 时，a r + l a + 1 ，a r + l a + 2 ，从而证明c r + 2 3 ( 1 ) 若n r + l = a + 1 ，则任意的z r r + l ( o ) ，z 的邻域结构如图4 9 ( 和口的距离) r r + 1r + 2 图4 9 e za t 照 e 2a + 1 个点 e 3d + 1 个点 令 z o ) = r ( z ) n r ，( 口) ，e l = r ( z ) n r ( z o ) n r ，+ l ( o ) ， 石) = ( r ( x ) n r ，+ l ( 口) ) e i ， r 0 ) n r ，+ 2 ( o ) = z 乙u e 2 u 1 1 3 令c = u 出+ ，( 。】忍，设d 为o + 2 ( q ) 中所有点构成的集合 则任意y c ，都有y d ，所以ccd 关于d 2 ，c , - + j = 1 且型为( a - i - 1 ，3 ) 的距离正则图 任意y d ，因为g + z ( a ，y ) 2k 2 u k l ，所以y 的部分邻域结构如图4 1 0 r + 1r + 2 z l x l x 2 由图4 9 和图4 1 0 知y 忍。其中z 1 f 件l ( 口) ，所以y e ，即d c 所以 d = c 因为i r r + 。( a ) 卜b + l ，且由图4 9 知z 和一对应同一个忍，断言所有b 的个 数为生产事实上，对任意。n + - ( n ) ，一定存在一个z 7 f r + 1 ( r j ) ，使得z z 且z 不与其余。个4 + ，( a ，z ) 中的点邻，显然边z 。决定一个历对于 r r + ，( n ) z ，z 7 ) 中任意y ，一定存在边y y ，使得y 7 不与其余n 个4 + - ( o ，y ) 中 的点邻，则y 乒伽，z 若否，不妨设y = z 7 ，则z 和z 的邻域结构如图4 1 1 ， 与y 的取法矛盾 r + 2 关于口 2 ，c r + l = 1 且型为陋+ 1 ，3 ) 的距离正则圈2 3 所以r r + - ( 口) 中存在虹21 个这种类型的边，而且每一个这样的边对应一个e 下边证每个不同的b 不交，其中z i - ，+ i c a ) 若否，如果存在边z $ 。 y y ，使得忍n 日口，也就是存在：使得z b n 日，如图4 1 2 所示，与 c r + 2 = 3 矛盾，断言成立 z ! ， ! ， 而每个忍中有口个点，故蚓= 。2 i d i = r r + ：( a ) 一麓+ 。= 曼磐尹= 笾孕血由于i oj = i d i ，所以a 字= 垒2 孕血得；= 学，即6 a + 4 = 3 a 矛 盾 ( 2 ) 若脚+ ，= 。+ 2 ，则任意的z f r + l ( a ) ，z 的邻域结构如图4 1 3 ( 和。的距离) rr + lr + 2 z 1 么 _ ， o 。个点 4 个点 44 - 1 个点 照( 1 ) ，同理可得 i f t 十2 ( o ) i = ( n4 - 1 ) i f ，+ l ( o ) j = ( a4 - 1 ) - k ，+ l 关于n 2 ，c r + 1 = 1 且型为似+ 1 ，3 ) 的距离正则图 2 4 而 l r ，+ z ( 。) i = 辟+ z 一生专兰= 墨! 掣 所以有妇删3 = ( 口+ 1 ) 辟+ 1 得到3 a + 1 3 ( 口+ 1 ) = 3 a + 3 矛盾 故a r + l a + 1 且口r + l a + 2 ，故c r + 2 3 口 定理4 的证明 若不然，设c r + l = 6 r + l = 1 首先证明任意y r r 十2 ，有g + 22m + 1 因为任意z r r + l ( o ) ， 辞+ t = 6 r + t = 1 ，所以x 的邻域结构如图4 1 4 所示( 和n 距离) r r + 1f - + 2 o 个点 由图4 1 4 可看出，任意y r r + 2 ( a ) ，任意z f r + l ( q ) n r ( v ) ，i r ( v ) n r ( x ) nr r + 1 ( n ) i _ a ，所以任意y r r + 2 ( n ) ，g + 21m + 1 由r ( x ) 14 k o + l 知， m = 1 ，2 ，3 或4 ， 由定理2 知，m 1 我们断言m 2 且m 3 若不然，任意y 研r + 2 ，+ lr ( ) n d ，r + 4 i 至多为3 个团的 并，并且由e ( v ，) = 1 知，有一