（基础数学专业论文）有强闭包子图的距离正则图.pdf

摘要 本文研究了距离正则图的强闭包性质主要利用距离正则图的交叉表、距离正则图的 性质以及距离正则图的已有结论，得到以下主要结论， 设r 表示一个直径d 2 的2 一齐次距离正则图令交叉数c 2 1 取定一整数 m ( 1 m a 1 = 0 ，c 2 1 任取x x ，x 3 r 3 ( z ) ，若存在r 3 ( x ) 中的一个连通分支使包含x ，z 3 的直径 为3 的强闭包子图q = 陋，c ， 则f 是4 界的 关键词：距离正则图强闭包子图d 界2 一齐次典型参数 i i i a b s t r a c t i nt h i st h e s i s ，w ec o n s i d e rt h es t r o n g l yc l o s e ds u b g r a p h so fd i s t a n c e - r e g u l a rg r a p h s b y m e a n so fi n t e r s e c t i o nd i a g r a m s ，p r o p e r t i e so ft h ed i s t a n c e r e g u l a rg r a p h sa n dt h ek n o w nc o n c l u s i o n so fd i s t a n c e r e g u l a rg r a p h ，w ep r o v et h ef o l l o w i n gc o n c l u s i o n s ： l e trd e n o t ea2 一h o m o g e n o u sd 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 rd 2a n dc 2 1 f i xai n t e g e rm ( 1 m a l20a n do z 1 f o r a n yz x ，2 7 3 r 3 ( z ) ，i f t h e r ee x i s t s ac o n n e c t e ds u b g r a p hc 7i nf z ( 2 7 ) s u c ht h a tq = k ，c 7 】w h i c hi sas t r o n g l yc l o s e ds u b g r a p h v c o n t a i n i n gz ，黝w i t hd i a m e t e r3 t h e nf i s4 一b o u n d e d k e yw o r d s ：d i s t a n c e - r e g u l a rg r a p hs t r o n g l yc l o s e ds u b g r a p h d - - b o u n d e d2 - h o m o g e n e o u s v i 学位论文原创性声明 本人所提交的学位论文有强闭包子图的距离正则图，是在导师的指导下，独立 进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集 体，均已在文中标明。 本声明的法律后果由本人承担。 论文作签名) 寻丕呢 如夕年钿日卜 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查| ； j 和借阅。本人授权河：i i ：n 范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 做磐引签名儿弘l 疋 劫口9 年6 , 9 日。 指删币。：魏刑 锄哆年石月日 n 钕 趁荔 ) j釉日 签 0 月认确f孵年 i v r ， 溯彬 导 指 引言 距离正则图的概念是上世纪七十年代由英国数学家b i g g sn l 提出的，接着他和一 批数学家g a r d i n e ra d ，s m i t hd h ，b r o u w e ra e ，b a n n a ie 和i t 0t 等建立了距离正则 图的基本理论框架距离正则图是距离可迁图的组合推广，同时又等价于p 一多项式方案 距离正则图可以看作是秩为l 的对称空间的离散化，而秩为l 的对称空间是2 - 点齐 次空间( 2 一p o i n th o m o g e n e o u ss p a c e s ) 在距离正则图的定义中，尽管只假定了组合正则性 而没考虑自同构作用的对称性，但大多数距离正则图有足够大的自同构群，使得它在距离 相等点对集合上的作用是传递的，因此有的专著把距离正则图叫做。无群的群论” 近几十年，距离正则图的研究非常活跃，并且还与设计、编码、有限几何以及纽结不 变量有密切联系，已成为代数组合论的一个重要分支熟知，距离正则图中强闭包子图性质 及应用是距离正则图研究中的一个重要内容我们首先介绍一下关于距离正则图中强闭 包子图的研究情况 1 9 9 6 年，h i r o s h is u z u k i 1 0 】研究了几何围长为5 的强闭包子图，并给出了直径为i 的强闭包子图存在的条件 * 1 9 9 7 年，c h i h w e nw e n g 【4 】对d 一界距离正则图进行了研究 1 9 9 8 年，c h i h w e nw e n g 【5 】5 证明了直径d 2 ，c 2 1 ，n 1 0 的距离正则图r 不含 长t + 1 的平行四边形的充要条件为r 是t 界的 1 9 9 8 年，h i r a k ia k i r a 2 】利用强闭包子图的构造定理研究了距离正则图的性质，得到 了参数间的一些关系 * 2 0 0 6 年，高锁刚、郭军和刘稳【1 2 】研究了d _ 界距离正则图的子空问的计数定理，并 用子空间构作了几何格 2 0 0 7 年，y e h j o n gp a n 和c h i h w e nw e n g 【l l 】证明了结论：设r 是直径d 3 ，典型 参数为( d ，b ，q ，p ) 的距离正则图若0 1 = 0 ，1 2 2 0 ，则r 是3 一界的 直到今天，对强闭包子图的研究还很活跃19 9 8 年，c h i h w e nw e n g 在文献 5 】中证得： 设r 足c 2 1 ，1 2 1 0 的距离正则图r 中不含长小于等于i + 1 的平行四边形的充要条件 是r 是i 界的c h i h w e nw e n g 在文献 3 】中提出公开问题：当c 2 1 ，1 2 2 a l = 0 时，此 充要条件足否成立接着他在【l1 】中证得r 为有典型参数( d ，b ，口，) 的距离正则图时，该 充要条件在i = 3 时成立能否得到i = 4 时该充要条件成立呢? 本文的第四章将对此公 开问题进行研究 c h i h w e nw e n g 在文献【5 】中指出若r 含有一个直径为d 的强闭包子图，则交叉数c i 满足不等式c c i 一1 ( c 2 1 ) + 1 ，( 1 i d ) 显然的，不等式中等号的成立就成为一个 非常重要的问题，本文在第三章就对此问题进行了研究 分类问题一直是距离正则图的重要研究内容，文献【9 】中，k n o m u r a 对二部2 一齐次 和几乎二部2 一齐次距离正则图进行了完全分类本文得到r 是2 一齐次时，等式c i = c i l ( c a 一1 ) + 1 成立的一个充分条件据此我们分c a = 2 ，a d g d 一1 = 0 和c a = 2 ，a d = n d l = 0 两种情况研究了2 一齐次d - 界距离正则图，并且得到了它们的交叉阵列 2 1 预备知识 1 1 距离正则图的基本概念 首先给出图的定义和习惯记号关于距离正则图的其他知识，读者可参考以下专著 a e b r o u w e r , a m c o h e n 和a n e u r n a i e r 【l 】 定义1 1 设x 是一个集合e 足由x 的一些元的无序对构成的集合则称集合对 r ：= ( x ，e ) 是一个图，其中x 称为图r 的顶点集合用v ( f ) 表示而e 称为图r 的边集 合用e ( r ) 表示 本文恒假定图为有限的，即i y r i 1 ( 2 ) q 和d p 之间无边，如果l i p l 1 或l j q i 1 为了使本文自成体系，下面简要介绍在本文出现的概念 定义1 6 限功r 的一个子图称为强闭包的，若对于中的任意两点u ，t ，都有 c ( u ，t ，) ca ，a ( 乱，钉) c 对一个固定点巩称关于点u 是强闭包的j 若对于中的任 意一点v 都有c ( v ，u ) ca ，a ( v ，) ca 定义1 7 限功若对任一满足点对z ，y ，其中o ( z ，y ) = i ，都存在一直径为i 的正则的 强闭包子图包含它们，则称r 为i 一界的若r 对所有的0 i t 均为i 一界的，则称r 为 界的 5 定义1 8 若r 是i 一界的，任取z ，y f ，a ( z ，g ) = t 令q ( z ，! ，) 是直径为i 且包含z ，y 的正则的强闭包子图 定义1 9 价纱设r = ( x ，e ) 是个直径为d 的连通图，整数i 满足1 i d 令 霉= ( 扎，口；加) i u ，t ，w x ，a ( u ，u ) = 2 ，u ， r i ( 叫) ) ， 五= ( “，口；叫) i u ，v ，伽x ，a ( t 正， ) = 2 ，t ，t ，r t ( 叫) ，a ( 伽，c ( t ，u ) ) = i 一1 ) 我们称饥存在溅m 对正存御，若对所有的( u ， ；w ) 霉缄( u ，v ；w ) t o 都有 7 ( u ， ；叫) = i c ( u ，u ) nf i l ( 叫) i = 7 i 因此对正而言的m 存在当且仅当对所有的( t ，u ；伽) 霉有，y ( u ，秒；w ) o ，m ) f 称为2 一 齐次的，若i 2 ，3 ，d 一1 ，时饥存在jr 称为几乎2 一齐次的，若i 2 ，3 ，d 一2 时m 存在 定义1 1 0 们刚不含长为2 的平行四边形的距离正则图称为序为( 8 ，t ) 的，其中 j = 口1 + 1 ，t = b l s 定义1 1 1 职谚对任意的z x ，ccx 定义k ，q ：= t ，x i 存在z c 使 a ( z ，口) + a ( 勘，z ) = a ( z ，名) ) 定义1 1 2 伊钏设r 是直径为d 的距离正则图令a 是阶为i x i 的方阵，其行与列 都足由x 中的点标定，它的( z ，掣) 位置的元素定义为 驴娃们刮佻0 i + f 或i j + 1 例k j i ，严k j g ，l = 硒p ：j 命题1 2 卯刀设r 是一个直径为d 的k 度距离正则图那么 例k = c i + 巩+ 啦厅= 0 ，1 ，驯 纠c o = a o = b d = 0 ，c l = 1 且b o = k 例令：= 醒p 则b i k i = c i + 1 乜+ 1 一= 0 ，l ，d 一砂 例c c i + 1 且玩玩+ 1f ，o i ，j d u 命题1 3 们助设f = ( x ，e ) 是有典型参数( d ，b ，q ，p ) ，直径d 3 的距离正则图 若a 2 n 1 = o ，则f 足，界的 命题1 4 们功设r = ( x ，e ) 是直径d 3 的距离正则图，q 是r 的价为1 的正则 子图，令d ：= m 讥 引，y q + o i ) ，则以下两条等价 似q 至少关于其内一点z 是强闭包的 例q 是直径为d 的强闭包子图 在此情形下，7 = c a + a d r 命题1 5 【5 r = ( x ，e ) 是直径d 2 的距离正则图设c 2 1 ，取r 的子图q ，设 d ( o d d ) 为一整魏则下面( 1 ) ( 2 ) 等价 ( 1 ) q 是直径为d 的强闭包子图 ( 2 ) 存在一点z q 满足以下( 2 q ) 一( 2 d ) ： ( 2 n ) q 关于z 足强闭包的 ( 2 6 ) i qnr l ( x ) i = + c d ( 2 c ) q = p ，c q 对某一c r d ( z ) ( 2 d ) 对所有口q z x ，若z 同时与c ( z ，t ，) 中不同两点相邻，则z q 命题1 6 侧! ) 设r = ( x ，e ) 尾直径d 2 的距离i t i 贝, j 图设c 2 1 ，n 2 0 若r 不 含长3 的平行四边形，则r 是2 界的 命题1 7 用令r = ( x ，e ) 表示一个图，其距离函数为6 q 是r 的一个子图，任取一 点z q 若q 关于x 是强闭包魄并设存在一点z r 1 ( z ) q ，则下面何一砂成立 f 砂对任意的q ，6 ( 名，秒) = 6 ( z ，y ) + 1 例z 是q 中唯一与z 邻接的点 命题1 8 仍切设r = ( x ，e ) 是直径d o ，且价为k 的二部2 一齐次或几乎二部2 一 齐次距离正则图，则r 有如下之一的交叉阵列? f 砂 七；1 ) ，七 0 ( k k + 1 ) 矽 后，七一1 ；1 ，七) ，后 1 ( k k k ) 例 七，七一1 ；1 ，c ) ，七= - y ( - y 2 + 3 7 + 1 ) ，c = ，y ( 7 + 1 ) ，7 0 f 砂 七，七一1 ，1 ；1 ，七一1 ，尼】- ，后 1 f ，2 佛+ 矽一格的卒卜勘 何 4 - ，4 7 1 ，2 7 ，1 ；1 ，2 3 ，4 7 1 ，4 7 ) ，7 0 f ，价后= 4 7 的h a d a m a r d 勘 俐 七，七一1 ，七一c ，c ，1 ；1 ，c ，后一c ，七一1 ，七) ，后= - y ( - y 2 + 3 7 + 1 ) ，c = - y ( - y + 1 ) ，y 0 m i o 的对径二覆盖勘 仍 2 ，1 ，1 ；1 ，1 ，2 ) ，d 1 张为2 d 的聊 俐 2 ，1 ，1 ；l ，1 ，1 ) ，d 1 伥为2 d + 1 的聊 例 意，七一1 ，七一2 ，七一3 ，1 ；1 ，2 ，3 ，七一1 ，七) ，= d ( t - ( ( t ，2 ) ) 门缈【2 d + 1 ，2 d ，2 d 一1 ，2 d 一2 ，d + 2 ；1 ，2 ，3 ，d 一1 ，d 】，d 1 ( 1 4 ( 2 0 + 1 ，矽的折叠 勘 9 命题1 9 m 劬设r 是价k 3 的距离正则图，直径d 2 ，= r ( r ) 则以下成立： 若r 包含一个诱导四边形，则q 一晚g 一1 一玩一1 + a l + 2 ( i = 1 ，d ) 例假设r 是序为伍砂的距离正则图，令g = t0 4 = i ( s 一1 ) ( 1 i d ) ，则r 是 h a m m i n g 阻h ( 1 + l 。s + 1 ) 例设r 是序为向砂的距离正则图，直径d = r + 1 则r 或为h a m m i n g 图目f 2 ，a 1 + 2 ) 或为 直径d 3 ，4 ，6 的序为仅砂的广义2 d 边形的共线性图特别的，c - r - l - 1 = 2 ，+ 1 = 2 a 1 例设a l 1 ，c r + 1 = 2 ，a r + 1 = 2 a l ，则c r + 2 3 进而若r 是序为( s ，2 ) 的且白+ 2 = 3 ，a ，+ 2 = 3 a l ，d = r + 2 ，则r = 1 ，r 是h a m m i n g 图h ( 3 ，a l + 2 ) 命题1 1 0 伽! ) f = ( x ，e ) 表示一个直径为d 的距离正则图设r 是d 一界的，则 玩 瓯+ i ( o i d 一1 ) 命题1 1 1 助r = ( x ，e ) 是直径d 3 的距离正则图，交叉数a 2 a l = 0 且r 不含任意长度的平行四边形任取z r ，q 足r 的直径为2 的强闭包子图假设存在整数 i 和点让qnr i l ( z ) ，若qnr i + l ( x ) 垂，则对所有的t q ，有a ( z ，t ) = i 一1 + o ( u ，t ) 命题1 1 2 伊助设r 关于本原幂等元e 是q - 多项式的，令铝，表示其对 偶特征值，则对所有的整数1 h d ，0si ，歹d 和z ，y x ，o ( x ，y ) = h ， 圣。，、e 岔一圣、e 2 = 砖筹蔫t ( e 岔一e 刃 一一 j 口 一口 、”7 z e x ，a ( x z ) = i ，a ( 可，z ) = jz e x ，a ( x ，：) = j ，a ( y ，z ) = ”“ 命题1 3 们j 刃r 是一直径。3 的距离正则图选取6 兄t 。，令 ： = 1 + b + b 2 + + 6 i ，则以下两条等价? r 关于相伴对偶特征值铝，是q 多项式的，且满足鳄一铭：( 钟一铝) i 2 i b 1 - i , 1 i 1j 俐r 有典型参数( d ，b ，q ，) ，其中口，p 足实常魏 命题1 1 4 以7 切设r = ( x ，e ) 是直径d 3 且典型参数为( d ，b ，口，p ) 的距离正则 图令a 2 a l = 0 任取相邻两点z ，z r ( z ) ，i d ，则b ( x ，z ) = b ( z ，2 ，) 1 0 2 1 基本性质 2d - 界距离正则图 引理2 1 设r 表示一个直径d 2 的2 一齐次距离正则图令交叉数c 2 1 取定一 整数m ( 1sm 0 另一方面c ( z ，z ) 掣) 中每一点与c ( y ，z ) 至多一点相邻为此任取w c ( z ，z ) 秒】，则 由由命题1 7 ，p i ( z ) f 3q = y ) 得w 不属于q ，而c ( u ，z ) f t , 由命题1 7 可得w 至多与 c ( y ，z ) 中一点相邻 下面我们考虑满足条件a ( u ，w ) = o ( u ，y ) = 1 ，o ( x ，u ) = i 一2 的点u 的个数，即c ( y ，z ) 中 与伽相邻的点的个数因为r 足2 齐次的，这个个数恰为m “与w ，x ，y 的选取无关由 命题1 7 得 i 一1 1 11 若一1 = 0 ，则c ( z ，z ) 可) 和c ( u ，z ) 之间边数为零与r 4 一l ( c 2 1 ) 0 矛盾所以 m 一1 = 1 ( 3 i m + 1 ) ， r 4 = 臼一l ( c 2 1 ) + 1 ( 1 i m + 1 ) 口 引理2 2 设r = ( x ，e ) 表示一个直径d 2 的d 界距离正则图令交叉数 c 2 1 ，a l = 0 ，且等式q = c 一1 ( c 2 1 ) + i ( i i d ) 成立若对任意满足o ( x ，y ) = a ( z ，w ) = i 一1 ( 3 i d ) ，o ( w ，y ) = 2 的z ，可，伽x 都有b ( y ，z ) nr l ( w ) 0 ，则r 足 2 齐次的 证明：由a l = 0 得 p 刍= 圭瞵；一，玩一- + 衍。a , - - a i ) + 硝i + 1 c i + 1 - - 纠 = 扣玩- l - k a ；+ 玩c , + 1 翻 = 圭瞰玩- 1 - 1 ) + 玩( c 五+ 1 - 1 ) + ( n ；2 飞) 】 云1 玩( c i + 1 1 ) 0 所以满足 a ( z ，y ) = o ( x ，w ) = i 一1 ( 3 i d ) ，o ( w ，y ) = 2 的z ，可，叫x 是存在的 由题设我们可选取名b ( y ，z ) nr l ( 叫) 因为r 是个d - 界距离正则图，所以( s c ) l 一1 成立设包含z ，y 的直径为i 一1 的强闭包子图是q 则由o ( x ，z ) = i d i a m ( f 2 ) = i 一1 得z 不在q 内又由命题1 7 ( i i ) 得 f l ( z ) nq = y ， w 也不在q 内 下面我们用两种方法计算c ( z ，z ) ! ，) 和c ( y ，z ) 之间的边数 因为c ( y ，z ) 中的任意一点都与c 2 1 个c ( z ，z ) 妇) 中的点相邻，所以c ( z ，z ) y ) 和 c ( y ，z ) 之间的边数为 q l ( c 2 1 ) 0 1 2 又因为 c ( z ，z ) 妇) i = q 一1 ， q = 龟一1 ( c 2 1 ) + 1 ( 1s i5d ) 并且c ( z ，z ) y ) 中点至多与c ( y ，z ) 中一点相邻，所以我们可得c ( z ，z ) y ) 中的每一 个点恰与c ( y ，z ) 中一点相邻所以w 恰与c ( u ，z ) 中一点相邻即 l f i 一2nr l ( 秒) nr l ( 加) i = 1 由z ，y ，w 选择的任意性可知对任意满足条件的z ，y ，w 都有 i f i 一2nr l ) nr 1 ( 叫) l = 1 ( 3 i d ) ， 即3 = 1 ( 2 i d 一1 ) ，所以r 是2 齐次的 口 引理2 3 令f = ( x ，e ) 表示一个d 一界2 一齐次距离正则图设交叉数c 2 = 2 ，a d = o 则r 是二部的 证明；若r 是d 一界的和2 一齐次的，由引理2 1 可得 m = 1 ( 3 i d 一1 ) 与 c i = c i l ( c 2 1 ) + 1 ( 1 i d ) 成立 因为c 2 = z 由c i = 龟一l ( c 2 1 ) + 1 ( 1 i d ) 可得q = i ( x i d ) 又由命题1 1 0 可 得b i k + l ( 0 i d 一1 ) 即 b i b i + x + x ( o i d 一1 ) 因为0 t = k 一玩一c = k b i i ，a i + 1 = k b i + 1 一q + 1 k 一( b i 一1 ) 一( i + 1 ) ，所以 a i + l a i ( 0 i d 一1 ) 由a d = 0 得0 t = o ( 1 i j d ) ，因此r 足二部的 口 1 3 2 2 主要定理及其证明 定理2 4 令r = ( x ，e ) 表示一个直径d 2 的d 界距离正则图，设交叉数c 2 = 2 ，口| d = o 则以下两条等价? 倒r 是2 一齐次的 一砂任取z ，y ，叫满足a ( z ，妙) = a ( z ，w ) = i 一1 ( 2 i d ) ，0 ( w ，y ) = 2 ，均有 b ( u ，z ) n r l ( w ) 谚 证明：( i i ) 兮( i ) ? 由o d 一1 = 0 得a l = 0 由引理2 1 ，2 2 可得1 1 是2 一齐次的 ( i ) 兮( i i ) 由引理2 3 得r 是二部的 因为c c 2 1 ( 2 i d ) ，所以可选取y ，加c ( z ，甄) ，其中a ( z ，i t , i ) = i 由a 1 = 0 得 o ( x ，y ) = a ( z ，叫) = i 一1 ，o ( w ，y ) = 2 因此b ( y ，z ) nr l ( w ) 0 由引理2 2 可得 i r i 一2 ( z ) ar l ( y ) nr l ( w ) l = 1 假设存在三点z ，可，t l j 满足0 ( x ，y ) = 0 ( x ，伽) = i 一1 ( 2 i d ) ，0 ( w ，y ) = 2 ，但s ( y ，z ) n i x ( w ) = d ，则c ( 可，叫) n r i ( x ) = o 任取z c ( y ，叫) ，由a i 一1 = 0 可得o ( x ，z ) = i 一2 ，所以 i r t 一2 ( z ) nr l ( y ) nr l ( w ) l = c 2 因为c 2 1 ，所以对满足0 ( x ，y ) = 0 ( x ，伽) = i 一1 ( 2 i d ) ，o ( w ，y ) = 2 的z ，y ，弛 i r t 一2 ( z ) nr l ( y ) nr 1 ( 叫) i 与z ，秒，伽的选取有关这与，y 是2 齐次的矛盾所以任取满足a ( z ，y ) = a ( z ，伽) = i 一1 ( 2 i d ) ，a ( 伽，y ) = 2 的z ，y ，伽，均有 b ( y ，z ) n r l ( w ) 0 口 注2 5 引理2 2 中的条件时任意满足a ( z ，y ) = o ( x ，训) = i 一1 ( 3 isd ) ，o ( w ，y ) = 2 的z ，可，协x 都有b ( u ，z ) ni l ( w ) o ”足可以达到的h a m m i n 9 图日( 七，2 ) 就满足这 个条件 事实上由文献 7 】和【8 】可得日( 屉，2 ) 是2 - 齐次的和d 一界的日( 七，2 ) 的交叉阵列是 七，七一1 ，1 ；1 ，k 一1 ，七 【其中c 2 = 2 1 由引理2 1 可得 m = 1 ( 2 i 0 所以对所有的满足o ( x ，y ) = a ( z ，t i j ) = i 一1 ( 2 i d ) ，a ( 叫，y ) = 2 的z ，y ，叫均有 b ( y ，z ) n r l ( 伽) 0 定理1 6 令f = ( x ，e ) 表示一个直径d 2 的d 一界距离正则图，设交叉数 c 2 = 2 ，a d = a d 一1 = 0 则r 是d 一界的当且仅当r 是h a m m i n g 图h ( k ，2 ) 证明：由引理2 3 得f 尾二部的由【l 】有 冼= l q ( b i - 1 - 1 ) + 玩( c i + , - 1 ) 1 。 我们可选取满足a ( z ，y ) = a ( z ，w ) = i 一1 ( 2 i d ) ，o ( w ，y ) = 2 的z ，y ，w 因为 l r i 一2 ( z ) nr l ( ) nf 1 ( 叫) l = 一1 = 1 ， c 2 1 ，所以 i r i ( z ) nr 1 ) nr 1 ( 叫) i = c 2 1 0 因此存在名满足 0 ( x ，名) = i ，o ( y ，z ) = o ( w ，z ) = 1 下面用两种方法计算点对( z ，w ) 的个魏 一方面先选乙则z 有b i 一1 种选法任取叫c ( z ，z ) 秒 ，则由a l = 0 可得o ( v ，w ) = 2 另一方面先选叫，则w 有p i 2 - i 一1 1 种选法任取z c ( u ，叫) ，由f 是二部的可得o ( z ，z ) = i 或i 一2 因为m = 1 ( 2 i d 一1 ) ，所以c ( v ，叫) n f i 一2 ( x ) 中的点足唯一的因此若选定 w 则z 有c 2 1 种选法 由以上可得 b i l ( g 一1 ) = 既i - t 1 l ( c 2 1 ) 由 j 】和a i 一1 = 0 得 硭- = 圭k - ( 玩- 2 - 1 ) 她q 一1 ) 】 1 5 又由引理2 1 得 综上化简可得 因此 c = c i l ( c 2 1 ) + 1 b i 一2 1 = 玩一1 ( 2 i d ) b o = k ，5 1 = k 一1 ，b d 一1 = k 一( d 一1 ) 由a d 一1 = 0 得c d l = d 一1 又因为c i = c 一l ( c 2 1 ) + 1 ( 1 i d ) 和a d = 0 ，所以 c d = d b d = k d 进而由6 d = k d = 0 得k = d ，所以r 的交叉阵列为 【七，七一1 ，1 ；1 ，k 一1 ，后) 因为a 1 = 0 ，由定义1 1 0 可得r 足序为( 1 ，k 一1 ) 的距离正则图又因为q = i ，a = 0 ( 1 i d ) ，由命题1 9 得r 是h a m m i n g 图h ( k ，2 ) 充分性：若r 是h a m m i n g 图h ( k ，2 ) ，由【8 可得r 足d - 界的 口 定理2 7 令r = ( x ，e ) 表示一个直径d 2 的d - 界2 一齐次距离正则图，设交叉数 c a = 2 ，a d a d l = 0 则r 的交叉阵列为 2 d + 1 ，2 d ，d + 2 ；1 ，2 ，d ) 证明t 由引理2 3 证明过程可得a i + 1 啦( 0 i d 一1 ) 由a d a d 一1 = 0 得 a i = 0 ( 1 i d 一1 ) ，因此r 足几乎二部的由【l 】有 p z 2 。i = 云1 一l + 魄c i + 1 + 。i ( a i - - a 1 ) 一明 2 毒 色( 6 i 一一1 ) + 饥( c t + 1 - 1 ) + 毗( 啦一1 ) 】 ( 2 1 ) 圭讹一1 ) 一 0 ( 2 i 冬d ) 所以可选取满足o ( x ，y ) = o ( x ，w ) = i 一1 ( 2 i d ) ，0 ( w ，剪) = 2 的z ，可，叫因为 r 一2 ( z ) np i ( y ) nf i ( w ) i = 一1 = 1 且c 2 1 ，所以 r t ( z ) nr l ( s ) nr l ( 加) l = c 2 一l 0 因比存在z 满足a ( z ，z ) = i ，0 ( y ，z ) = a ( 伽，z ) = 1 现在用两种方法计算点对( z ，伽) 得个数与定理2 6 相似可得 兢一2 1 = 玩一1 ( 2 i d ) 所以b o = k ，b l = k 一1 ，b d 一1 = k 一( d 一1 ) 由g d 一1 = 0 得c d l = d 一1 又因为 c = c i l ( c 2 1 ) + 1 ( 15i d ) ，有c d = d 因此r 的交叉阵列为 七，k 一1 ，k 一( d 一1 ) ；1 ，2 ，d 】， 根据命题1 8 对二部和几乎二部2 一齐次距离正则图的分类可得r 的交叉阵列足 2 d + 1 ，2 d ，2 d 一1 ，2 d 一2 ，d + 2 ；1 ，2 ，3 ，d 一1 ，d 口 3 1 基本性质 3 距离正则图的4 一界性质 令r = ( x ，e ) 是典型参数为( d ，b ，q ，p ) ，直径d 4 的距离正则图设a 2 a l = 0 ，0 2 1 1 l 】证得r 足3 一界的由命题1 5 若r 是3 一界的，则存在r s ) 中的一个分支 使包含z ，2 ；3 ，0 ( x ，x 3 ) = 3 的直径为3 的强闭包子图q = p ，】如果是连通分支， 本章证得r 是4 一界的为此首先取定z ，y x ，o ( x ，y ) = 4 令c ：= p r 4 ( x ) l b ( x ，y ) = b ( x ，z ) ) ，a = kq 下面证明是直径为4 的强闭包子图下面先证关于z 是强闭包 的，再证足价为毗+ c 4 的正则子图 引理3 1 令r = ( x ，e ) 是典型参数为( d ，b ，o t ，卢) ，直径d24 的距离正则图，设 a 2 a l = 0 ，c a 1 ，s t u z w 是r 中一五边形，其中s ，t 正r 4 ( z ) ，z r 3 ( z ) ，u b ( z ，) ，则 o ( v ，s ) 3 证明：若o ( v ，8 ) = 3 ，由a l = 0 得o ( z ，8 ) 1 ，所以z ，w ，s ，t ，u q ( z ，s ) ，则有 s q ( z ，s ) nf a ( v ) 又u q ( 名，s ) nr s ( v ) o ，由命题1 1 1 得 o ( v ，z ) = 0 ( v ，5 ) + a ( s ，z ) = 3 + 2 = 5 而由0 ( v ，z ) = 1 ，o ( x ，z ) = 3 得0 ( v ，z ) 4 矛盾 口 引理3 2 令f = ( x ，e ) 是典型参数为( d ，b ，q ，p ) ，直径d 4 的距离正则图， 设a 2 a l = 0 ，c 2 l ，s t u z w 足r 中一五边形，其中s ，“r 4 ( z ) ，z f s ( x ) ，则 b ( x ，s ) = s ( x ，u ) 证明：因为j b ( x ，s ) i = l s ( x ，u ) i = b 4 ，故只需验证b ( z ，8 ) 2b ( x ，t ) 由引理3 1 得 b ( x ，) r 4 ( x ) ur 5 ( z ) 设l b ( x ，t ) nr 4 ( z ) i = m ，i b ( z ，u ) nr 5 ( z ) i = 见则m + 佗= b 4 由命题1 1 2 得 reb(x们肛。、所幽a糍(肛吼reb(u，t )，互) u 1 9 又m + n = b 4 及命题1 1 3 可解得n = 6 4 ，m = 0 ，所以b ( z ，让) b ( x ，s ) ，定理得证 口 引理3 3 令f ：( x ，e ) 是有典型参数( d ，6 ，q ，p ) ，直径d 4 的距离正则图，设 o , 2 a l = 0 ，c 2 1 。s t u z w 是r 中一五边形，z ，“，其中名，w r 3 ( z ) ，t r 4 ( x ) ，则 w a 证明一注意到q ( z ，8 ) nr 2 ) = 口，否则若存在钉a ( z ，8 ) nr 2 ( z ) ，因为a ( z ，s ) n r 4 ) 0 ，由命题1 1 1 得 所以 o ( x ，z ) = a ( z ，口) + a ( t ，名) ，a ( z ，w ) = a ( z ， ) + a ( 秒，伽) ， 这与a l = 0 矛盾同时 a ( 口，名)= a ( ，w ) = a ( z ，w ) = 1 q ( z ，s ) nr 5 ( z ) = 0 否则若存在 q ( z ，8 ) nr 5 ( z ) ，因为 由命题1 1 1 得 矛盾所以 q ( 名，8 ) nf 3 ( x ) o ， a ( z ，乱) = a ( z ，彬) 十a ( 叫，u ) = 3 + 2 = 5 4 8 ，t r 3 ( z ) u r 4 ( z ) ， 易得8 r 4 ( z ) 否则w ，s q ( z ，名) ，有 u a ( z ，8 )q ( z ，z ) 而a ( z ，u ) = 4 与q ( z ，z ) 的直径为3 矛盾由引理3 2 得b ( z ，8 ) = b ( z ，u ) ，由构造可知 s c ，w a 定理得证 口 引理3 4 令r = ( x ，e ) 是有典型参数( d ，b ，q ，p ) ，直径d 4 的距离正则图，设 a 2 a l = 0 ，c 2 1 ，则子图关于z 是强闭包的 证明：任取z a ，易得c ( z ，x ) a 下面只需对任取z a 证明a ( 名，z ) a 分情况讨论： 2 0 当a ( z ，名) = 1 吨由q l = 0 得a ( z ，z ) = 谚 当a ( z ，z ) = 4 时，对任意的 t o 4 ( z ，z ) ，由的定义及命题1 1 4 得b ( z ，y ) = b ( z ，z ) = b ( x ，叫) ，所以a ( z ，z ) a 当a ( z ，名) = 2 吨存在 u 0 c 使 o ( x ，z ) + o ( z ，u o ) = a ，咖) = 4 任取 c ( z ，咖) ，则z c ( v ，z ) 由命题1 3 知r 足3 一界的，由定理条件知存在r 3 ( z ) 的一 个连通分支c 7 使q ( z ， 3 ) = p ，】任取 1 1 3 a ( z ，z ) ，则伽a ( x ，口) ，故存在r 3 ( z ) n c 7 使叫c ( ，z ) 设出从口到 7 在r 3 ) 中的一条路 t ，= 3 0t ，l 仇= 3 7 由0 , 1 = 0 得o ( v l ，乱o ) = 2 取8 0 a ( v x ，u o ) ，t o c ( 锄，s o ) ，由引理3 3 得 u 1 a ，故存在 u l c 使 0 1 c ( u l ，z ) 由o l = 0 得a ( 忱，u 1 ) = 2 取8 1 a ( v 2 ，u 1 ) ，t x c ( u l ，s 1 ) ，由引 理3 3 得7 3 2 a ，敌存在 u 2 c 使 0 2 c ( u 2 ，z ) 依次进行下去可得 a ，所以 1 1 3 c ( v ，z ) a 当a ( z ，z ) = 3 吨对任意的 t o a ( z ，z ) ，必存在乱c 使名c ( u ，z ) 由n l = 0 得 o ( w ，t ) = 2 ，选取s a ( w ，u ) ，t c ( u ，8 ) 则8 t u z w 是r 中的一个五边形，由引理3 3 得 7 0 a ，层pa ( z ，z ) a 弓i 理得讧e 口 引理3 5 令r 是d 3 且有典型参数( d ，6 ，o t ，p ) 的距离正则图设0 2 o l = 0 ，任 取z f 若是直径为3 且关于z 强闭包的子匦o ( z ，x 3 ) = 3 ，zz lz 2z 3 是中的一条 路，则包含z ，z 2 的直径为2 的强闭包子图q 包含于 证明：由引理j 6 得r 足2 一界的，即直径为2 且包含z ，z 2 的强闭包子图q 是存在的 由引理，6 的证明过程知存在i 2 ( z ) 中的一个连通分支c 使包含z ，z 2 的直径为2 的强闭 包子图q = 囟，q 任取耖f t , 则可【z ，c 】，即存在一点z c 使 a ( z ，y ) + o ( y ，z ) = a ( z ，z ) ， 由于c 是i 2 ( x ) 的连通分支，所以z 与：7 2 在r 2 ( z ) 中连通，从而 z a ，a 口 2 1 引理3 6 令r 是直径d 4 且有典型参数( d ，b ，q ，p ) 的距离正则图设a 2 a l = 0 ，c 2 1 ，a 是直径为4 且关于z 强闭包的子图，0 ( x ，x 4 ) = 4 ，z2 ；1x 2