（基础数学专业论文）序为（25）且cr1≥4的距离正则图.pdf

中文摘要 本文利用距离正则图的交叉表、圈搜索技巧等方法对序为( 2 ，5 ) 且c 。4 的距离正则图进行了分类，得到如下结论 设r 是一个有序对为( 2 ，5 ) 且c 。4 的距离正则图令，= ，( r ) ，那么 1 c r + 】6 2 如果c 。= 5 则d 2 r + 1 ，且下列叙述之一成立 ( 1 ) u ，+ l = 6 ，c d = 1 2 ，且，+ 2 d = r + ，+ 2 2 r + 1 ( 2 ) a r + i = 5 ，a c m 一一l = 5 ，c d = 6 ，r 是l - 齐次图， ，+ 2 d = r + s + l 2 r + 1且，2 3 如果c 。= 4 ，则下列叙述之一成立 ( 1 ) q “= 8 ，d = ，+ 1 ； ( 2 ) ( 气l ，a r b r + 1 ) = ( 4 ，6 ，2 ) ； ( 3 ) ( c h ，a r m b r + 1 ) = ( 4 ，5 ，3 ) ，d = ，+ 2 或者当d ，+ 3 时，c 。! = 5 ，6 或8 ( 4 ) ( c ，o r b ) = ( 4 ，4 ，4 ) ，则c m = 4 ，5 ，或6 ，特别的，若c m = 5 ，则 口，+ 2 t z7 关键词：距离f 则图，有序对( j ，0 ，交叉数，点类型，团模式，点邻域 a b s t r a c t i nt h i s t 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 a n dc i r c u i t c h a s i n g t e c h n i q u e s ，w eg i v eac l a s s i f i c a t i o no fd i s t a n c e r e g u l a rg r a p h so fo r d e r ( 2 ，5 ) a n d c 。4g e t t h er e s u l t sa sf o l l o w s l e trb ead i s t a n c e r e g u l a r g r a p ho fo r d e r 口，彭a n dc 川4 l e t f ，( r ) ，t h e n 1 ，c ，+ 1 6 2 i fc 。1 = 5 ，t h e n d 2 r + 1 ，a n do n eo f t h ef o l l o w i n gh o l d s ( 1 ) a ，+ 1 = 6 ，c d = 1 2 ，a n d ，+ 2 d = r + t + 2 茎2 r + 1 ( 2 ) a r “= 5 ，0 + 2 一= t ，- l = 5 ，c d = 6 ，f i s a1 一h o m o g e n e o u sg r a p h ， r + 2 d = ，+ s + 1 2 r + 1 a n d ，2 3 i fc 。i = 4 ，t h e no n eo f t h e f o l l o w i n gh o l d s ( 1 ) a h = 8 ，d = r + 1 ； ( 2 ) ( c h ，a r + l , b ) = ( 4 ，6 ，2 ) ( 3 ) ( c ，+ i ，a ，“，6 ，+ 1 ) = ( 4 ，5 ，3 ) ，d = r + 2 o r w h e nd r + 3 ，c ，+ 2 = 5 ，6o r8 ( 4 ) ( c ，a t + i , b ) = ( 4 ，4 ，4 ) ，t h e nc m = 4 ，5 ，o f6 ；p a r t i c u l a r l y ，i f c ，+ 2 = 5 ，t h e na ，+ 2 7 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 ，i n t e r s e c t i o nd i a g r a m ，o r d e r ( s ，t ) ，v e r t e xt y p e ， c l i q u ep a t t e r , v e r t e xn e i g h b o r h o o d 第一章绪论 1 1课题背景及其发展概况 距离正则图( d i s t a n c e - r e g u l a rg r a p h s ) 这一概念是由英国数学家n l b i g g s 于上世纪七十年代初提出来的。接着他和一批数学家a d g a r d i n e r , d h ，s m i t h s ，a e b a r m a i 和t i t o 等建立了距离正则图的基本理论框架另一方面，为了 解决码论中的问题，p h d e l s a r t 在文献凹中研究了p 一多项式方案 ( p - p o l y n o m i a la s s o c i a t i o ns c h e m e s ) 而p 一多项式方案实质上就是距离正则 图 近几十年，距离正则图的研究非常活跃，并且与有限群、有限几何、码论、 设计、网络和纽结不变量等其它数学分支有着密切的联系，已成为代数组合论 的一个重要分支熟知，距离正则图的分类是距离j 下则图研究中的一个重要研 究内容我们首先介绍一下有序对为0 的距离正则图的研究情况： 1 9 8 5 年，b m o h a r 和j s h a w e - t a y l o rd 2 i 正明了有序对为向矽的距离 正则图是线图，并且对此类图进彳亍了分类 1 9 8 2 1 9 8 8 年，t t t o 1l 】，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 3 及 e b a n n a i 和t i t o 2 把度为3 的距离j 下则图完全分类而且证明出，在同构意以 下，度为3 的距离正则图只有1 3 个从而有序对为( 1 ，2 ) 的距离正则图也得到 完全分类 1 9 9 5 年，n y a m a z a k i 1 6 汪明出有序对为向2 ，且d ( r ) 2r ( r ) + 3 的距离 j 下则图是度为3 的距离正则图的距离2 图，其中s 3 2 0 0 0 年，a h i r a k i ，k n o m u r a 和h s u z u k i 9 对有序对为( 2 ，2 ) 的距离正则 图，即后= 6 且珥= 1 的距离正则图进行了完全分类，并且证明，在同构意以下，有 序对为( 2 ，2 ) 的距离正则图只有4 个 2 0 0 4 年，a h i r a k i 和j k o o l e n 1 刀给出了序为( s ，2 ) 的正则拟多边形的完 全分类 到现在为止，对有序对( s ，1 ) ( s ，2 ) 的距离正则图的研究已经基本结束，但 对于岛 _ l 或度不小于7 的距离正则图的分类都没完全解决本文对有序对为 ( 2 ，5 ) 的距离正则图进行了研究，且只对c r + ，4 的情形作初步的讨论这对于有 序对为( 2 ，5 ) 距离正则图的完全分类将具有重要的意义 1 2本文主要研究的内容与结构 本文分五章，第一章阐述了课题背景及其发展概况第二章为预备知识，着 重介绍后面几章中要用到的一些符号、概念和基本结论第三、四、五章分别 讨论在c ，+ = 6 ，5 和4 的条件下，有序对为( 2 ，5 ) 的距离正则图的分类 本文的主要结论如下： 设r 是个有序对为( 2 ，5 ) 1 ；1c , 。4 的距离正则图令，= - ，( d ，那么 1 c ，十l 6 2 如果c r + l = 5 则d s 2 r + l ，且下列叙述之一成立： ( 1 ) q “= 6 ，白= 1 2 ，且r + 2 s d = r + r + 2 2 r + l ； ( 2 ) q “= 5 ，且q + 2 一= 白一l = 5 ，白= 6 ，r 是l 齐次图， ，+ 2 d = ，+ j + l s 2 r + 1 且，2 3 如果c r + 。= 4 ，则下列叙述之一成立： ( 1 ) q “= 8 ，d = ，+ l ； ( 2 ) ( q + ，q + l ，6 ，“) = ( 4 ，6 ，2 ) ； ( 3 ) ( q + i q + l ，6 ，+ 1 ) = ( 4 ，5 ，3 ) ，d = ，+ 2 或者当d ，+ 3 时，c r + 2 = 5 ，6 a z 戈8 ； ( 4 ) 心+ l ，q + l ，6 ，+ 1 ) = ( 4 ，4 ，4 ) ，则o + 2 = 4 ，5 ，或6 ，特别的，若q + 2 = 5 ，则 q + 2 7 2 第二章预备知识 2 1 距离正则图的基本概念和性质 本节给出距离正则图的一些基本概念和性质关于距离正则图更详尽的 性质见文献 1 ，4 】 定义2 1 一个图( g r a p h ) r 定义为一个偶对( x ，e ) ，记作r = ( x ，e ) ， 其中 仃，) x 是一个集合，其元素称为顶点； 臼) e 是无序积的一个子集合，其元素称为边 我们分别用玎和e f 表示图r 的顶点集合x 和边集合e 如果汀和盯都 是有限集合，则r 称为有限图；否则称为无限图 在本文我们恒假设图r 为有限图 定义2 2 设r = ( x ，e ) 和r ，= ( z ，e ) 是两个图 ( 1 ) 一个双射o ：x j 称为图r 到图r ，的一个同构( i s o m o r p h i s m ) ， 如果x y e 当且仅当 盯( z 弦( j ，) e ( 2 ) 若r = r ，则从图r 到图r ，的同构称为图r 的自同构 ( a u t o m o r p h i s m ) ( 3 )图r 的所有自同构构成的集合对于映射的合成运算构成一个群，我 们把这个群称为图r 的自同构群( a u t o m o r p h i s mg r o u p ) ，记作a u t ( c ) 本文对同构的图不加以区别 定义2 3 令r = ( z e ) 是一个图图r 的两个顶点x 和y 称为相邻的 ( a d j a c e n t ) ，如果x y e 记为x y 设u 和v 是图r 的两个顶点，我们有 ( 1 ) 图r 中从顶点u 到顶点 ，的长为，的一条途径( w a l k ) 是r 中h 1 个顶点序列( u = w o ，w i 一w i = v ) 使得 l l ；w o 1 i ，1 ，= ， 3 ( 2 ) 图r 的一条途径( u = w o ，w i j - 一w l = l - ) 称为路( p a t h ) ，如果对所有的 i d ( i d = l ，i - i ) , 都有w ，坳，一条路( 越= w o ，w i w 尸y ) 称为约简的( r e d u c e d ) ， 如果对任一个i ( 净l 一，1 - 1 ) ，都有嵋一l9 w 。 ( 3 )图r 中顶点u 和顶点v 的距离( d i s t a n c e ) 是r 中连接u 和1 ，的最 短路的长，记为砟( 甜，v ) = 0 0 ( 4 ) 图r 称为连通的( c o n n e c t e d ) ，如果r 中任意两点x 和弘在r 中都 存在连接x 和y 的路 ( 5 )连通图r 的直径( d i a m e t e r ) 是r 中任意两点间距离的最大值，记 作d = 吠r ) ( 6 )设x ev f 点x 的价或度( v a l e n c y 或d e g r e e ) 后 ) ：= 醑g ) 是r 中与x 相邻的点数若对任意一点x r ，j ：砘是一个常数，则r 称为七度 正则的( r e g u l a r ) 设i 是一个图且u , x , y f 令 r ，( 都) = v r ia r ( 甜，1 ，) = f ，且r ( “) = r i ( 甜) ， # j ( x ，j ，) = r ，( x ) n r ，( j ，) ，其中，= o r ( 材，1 ，) 如不特殊指出，本文中记o ( x ，j ，) = o r ( x ，y ) ，其中x ，) ， 定义2 4 一个直径为d 的连通图r = ( x ，) 称为距离正则的( d i s t a n c e r e g u l a r ) ，如果对r 中任意两个距离为，的点x 和y ，l e l , ( x ，j ，) 1 只与和，有关， 而与x ，y x 的选取无关，其中0 s f ，歹，d 设r 是一个直径为d 的距离正则图。记一，= 陋? ( x ，y ) 1 称以为r 的交叉 数( i n t e r s e c t i o n n u m b e r s ) ，其中0 f ，歹，f d 特另q ，记q = 纠，l ，q = 叫且匆= p s ，o = o ，1 ，d ) 令r 是一个直径为d 的距离正则图对r 中任意两个距离为i 的点u 和1 ， ( 0 i d ) ，定义 4 c ( u ，功= c i ，力= r ， ) n i ( v ) ， a ( u ，v ) = 4 ， ，) = r 。 ) n r ( v ) ， a ( u ，v ) = 置( ”，= r ( ”) n r ( ，) 则显然有 c = i c ，v ) l q = 1 4 ，v ) i 和岛= l 皿( 甜，) 1 定义2 5 个距离正则图r 的交叉数组( 砌啪e d 如拧a r r a y ) 定义为 rq q ，勺1 l ( r ) = a o q q a a ia a 【b o6 l 岛一。+ j 例如，考虑立方图q 3 ，它是一个直径为3 的距离正则图由图2 1 ，我们有它的 交叉数组f ( q ) 123 1 o o0 2 1 + j 定义2 6 定义 ，( c ，口，6 ) = l fj ( c ，q ，匆) = ( c ，口，6 ) i ，= r ( r ) = i ( c 1 ，q ，6 1 ) 一个2 度的距离正则图仅是一个多边形( p o l y g o n ) 下面恒设度数大于2 为使本文自成体系，我们将简要介绍在本文中出现的概念 定义2 7 图r 中顶点x 的邻域是指r 在子集r ( x ) o z 矿( r ) 上的诱导子图 定义2 8 距离正则图r 称为有序对为( 占，) 的图，如果对图r 中任意顶点 a 都满足r ) = ( ，+ 1 ) k 由文献所知，如果距离正则图r 不包含同构于吃的诱导子图，那么对于 某个正整数s 和，r 是有序对为( s ，f ) 的图特别的，当，一o 时，r 是完全图 5 o 3 ，j、【 = )q 定义2 9 距离正则图r 称为有序对为( s ，r ) 的正则拟多边形，如果它是一 个有序对为( s ，t ) 的距离正则图，且对所有的1 i d 一1 ，有q m - q ( s - 1 ) 进一 步，一个有序对为( j ，) 的正则拟多边r 是正则拟2 d 一边形，当且仅当 a a = 白p 一1 ) 定义2 1 0 图r 称为团( 或完全图) ，如果图r 中的任意两顶点都邻接 并把有刀个顶点的完全图记作岛 图r 称为余团，如果图r 中的任意两顶点都不邻接 定义2 1 1 一个连通图r 称为f 一齐次图，如果对所有整数c 墨以及对所 有顶点u , v , 1 4 ：v ，其中o ( u ，d = o ( u ，v ) = ，下面条件成立： 若x d j ( “，1 ，) ，j d f ( 甜，v ) ，贝u 有e ( x ，彰( “，v ) ) = p ( x ，彰( “，) ) d 一齐次图是距离正则图 命题2 1 2 ( ，z ，) 设r 是一个直径为d 的距离正则图令置= p o ，那么我们 有下述结果： ( 1 ) 或= 力，( o - i + ， f + ，或f y + l ； ( 4 ) k 。p ：f = k j p 0 = k f 矗。j 命题2 1 3 ( ，z ，) 设r 是一个直径为d 的k 度距离正则图那么 ( 1 ) k = q + 包+ qo = o , 1 ，d ； ( 2 ) c o = a o = = 0 ，q = 1 且b o = k ； ( 3 ) 令毛_ p o ，n b , k , = q + i 置“o = o ，l ，d - 1 ) ； ( 4 ) 设“和v 是【的两个点且w c ( v ，群) ，那么c ( 枇v ) c c ( u ，v ) 且 6 b ( w ，v ) b ( u ，v ) ； ( 5 ) c j q + l 且匆岛+ l ( 0 f ，d 1 ) ； ( 6 ) 设，v ，w v v 如果啡( “，v ) = a r ( “，们+ 钟( w ，v ) ，那么 c ( u ，w ) 亡b ( v ，忉； ( 7 ) 匆2 c ，如果i + _ ，d 2 2 交叉表及性质 本节我们介绍距离正则图的交叉表( i n t e r s e c t i o nd i a g r a m s ) ，它是研究距离 正则图结构的主要工具( 参见文献- 6 , 1 4 ) 令“和1 ，是图r 中相邻的两个点， 并记彰= r ，( 甜) n r ，( v ) ( o s l ，d ) 关于边( 甜， ，) 的交叉表是由点集 “( o f ，j d ) 构成，其中点集之间有线相连，如果两个点集q 和研之间 可能存在边，那么在这两个点集之间划一条线： d ：一纠 否则，不画线如果髟- - - - 0 ，则去掉这个点集 由定义我们有如下结果 ( 1 ) 彰- - - - - 0 ，如果f f 一卅 1 ( 2 ) 纠和掰之间无边，女口果 i - p j l 或l j - q i 1 本文中，为了叙述方便，我们把“关于边 ，1 ，) 的交叉表”记成“( “，) 一表”， 而把“关于r 中任意一条边( 甜，) 的交叉表”记成“每个( 材，v ) 一表” 距离正则图的每个( “，) 一表如图2 2 所示 7 受 钟 f 埘 定义2 1 4 对顶点集彳和b ，用e ( a ，仞表示集合4 和b 之间的边数如果爿= ， 则记e ( “) ，b ) = 8 动 命题2 1 5 ( 砸7 j 钐) 在每个( “ v ) 一表中，如果x 叫且y 研“ ( 0 t d 1 ) ，那么我们有如下结果： ( 1 ) p ( 工，d _ i ) + e ( x ，d ：t + + 1 1 ) = 6 ，； ( 2 ) p ( x ，上鼍1 ) + p ( 戈，d f ) + p ( x ，上碓1 ) = q ； ( 3 ) p ( x ，d l i ) + p ( x ，j e 留) = q ； ( 4 ) p ( y ，三搿) = 匆“； ( 5 ) p ( y ，研“) + p ( 夕，删t + + 1 1 ) = 口，“； ( 6 ) e ( y ，以1 ) + e ( y ，研) + e ( y ，硪i ) = q “； ( 7 ) p ( y ， 薯等) + p ( y ，e 斜) + e ( y ，嚷1 ) = 6 ，； ( 8 ) p ( j ，d j ) + p ( j ，叫“) = q ； ( 9 ) e ( y ，硪。) = q ； ( 1 0 ) e ( x ，硪1 ) = e ( x ，叫“) ； ( 1 1 ) e ( x ，雕1 ) = e ( x ，巧1 ) ； 0 2 ) b , = 6 ，+ 。当且仅当p ( 巧“，) = p ( 叫，纠“) = p ( 倒t “，剧t + + 。1 ) = 0 ； ( 1 3 ) q = q 钉当且仅当e ( 研”，科) = 暑( 纠t + ，科“) = p ( 科“，g ：) = 0 ； ( 1 4 ) 科= a 当且仅当q = 0 8 2 3 若干符号及性质 为了叙述方便，本文中给出了一些新的概念和符号，以及证明中常用的结 论 令e ( a ，四表示r 的两个子集a 和b 之间的边数，且对任意的x y r ，令 p ( x ，彳) = e ( x ，彳) 定义2 1 6 图r 中的任意两个不同的顶点x 和y ，讹y ) _ 其中l i d ， 我们称图r 在f 。 ) n r ( 1 ) 上的诱导子图为c ，一图，或称e 一图 r 。 ) n r ( v ) 4 一图和e 一图可类似定义 定义2 1 7 设a = 缸，厉”是一个团，则顶点x ( 关于( a ，) ) 的类型记为 孑= ( a ( x ，口) - r ，o ( x ，) 一r ，a ( x ，) 一，) 顶点x 的团模式，是指f ( x ) 中的点的类型的集合以及其中的边的关系如不 特殊指出，本文中出现的点的类型均为关于 ，) 的点的类型 我们在本文中固定下面的记法： a ( a ，f 1 ) = 1 ，q = f l ( a ) n r ，( ) ，叫= 厂) 命题2 1 8 ( j ! 乃设r 是一个直径为d 的距离正则图，其中对r 中的每条 边u , v ，科( “，v ) 是团，则r 是1 一齐次图，当且仅当f 是正则拟2 d 一边形 命题2 1 9 ( 0 3 3 设r 是一个直径为4 价为k 的距离正则图，假如对某个 i i ，有b l = c d l ，6 2 = 气一2 ，匆= q 一2 ，贝u f 歹日成立： ( 1 ) 屯一l = q ，一2 = c 2 ，一，= q ； ( 2 ) 若a a 0 贝船= 乃( + 1 ) ，岛= 6 2 = = 岛= 口2 ，l = q = = q = q “ 命题2 2 0 ( 川) 设r 是一个直径为d 的距离正则图，若q o ，n a , o ，其 中l i d 1 9 命题2 2 1 ( 侈引理2 5 d设r 是一个有序对为( s ，f ) 的距离正则图， ，= 厂( r ) ，对r 中满足a ( x ，口) = r + l 的任意顶a 和五c r + l 一图r ，位) n r ( x ) 是余 引理2 2 2 设r 是序为( 2 ，5 ) 的距离正则图，且，= r ( 1 1 ) ，则下列成立： ( 1 ) c r “s 6 ，特别地，如果c ，+ l = 6 ，则d = r + l ； ( 2 ) 若钆j = 5 ，则l 5 ； ( 3 ) 若c r “= 4 ，贝q 口，+ l 4 引理2 2 3 巨彰理2 j d 下列叙述成立： ( 1 ) p ( 捌- 1 ，尉) = “q - l ，三 f ：二：) = “捌一，砚) = 改，q ) = g ( 砚，三捌- i ) = o 2 is ，； ( 2 ) 对1 歹r ，设x ，y 叫“，z 琢l ，若y x z ，则y z ； ( 3 ) “耳，矽1 ) = 反耳，z y + ，) = o ； ( 4 ) 若c r 。= 1 ，贝e ( ， 矿) = o 命题2 2 4 ( 毋俞题刀) 令r 是一个直径为d 的距离正则图，具有交叉列阵 卵，也二1t 一1 2 c d ( 1 ) 如果白= 1 ，则咖2 ； ( 2 ) 如果c a = f + l ，则d 2 ，3 ，4 ，6 ，而且，如果s 2 ，则d 6 ，且下列成立： ( i ) 如果d = - 2 ，则5 t 2 且f s s 2 ； ( i i ) 如果d = 3 ，则s t 是一个平方数，且s t 3t s 3 ； ( i i i ) 如果d - - 4 ，则2 s t 是一个平方数，且则j sr 2r t s 2 1 0 图r 的一个特征值即指其邻接矩阵a 的特征值，且相应的重数也相等定 义如下的多项式“( 功，0 i d m ( x ) = l ，( 功- 且q 嵋一i ( x ) + q 砷( x ) + 6 ，甜f + i ( x ) = x u t ( x ) ，i = 1 ，2 ，d 一1 令k = o o b 易一。 吃是a 的特征值，且所( q ) 为e 的重数，其中 = o ，i ，1 一，d 我们已知a 的特征值恰为下面的( d + 1 ) x ( d + 1 ) 对角矩阵的特 征值 t , o 0 c la t6 l 0 c 2a 2 00 0o 0 00 00 0 以一l c aa a 且m ( 只) - 丁删一 t q ( 9 ) 2 最后，为书写方便，我们再定义下面的符号 5 = i ( c r + l ，q 十l ，印+ 1 ) r = ，( q + ，a r + ，6 ，+ ) = ，( c ，+ 。+ l ，口，+ 。+ i ，o r + 。+ i ) 其中6 ，“0 且6 ，l o ，t r + ，“0 第三章q + 。= 6 的情形 定理3 1 设i 是序为( 2 ，5 ) 的距离正则图，且，= r ( r ) ，则c ，“6 证明：若c r + l - - - 6 ，则由引理2 2 2 得d = r + l 且 盯，： ：1 _ ：1 。：l 1 1 21 0 1 0 + j 又有命题2 2 4 ( 2 ) 可知，d 6 且d 2 ，3 ，4 ，) 但经简单计算可知( i ) ( i i ) ( i i i ) 均不成立，即d 2 ，3 ，4 ，) 矛盾，故c 6 一 1 2 第四章q + 。= 5 的情形 本节主要证明下面的定理4 1 定理4 1 设r 是序为( 2 ，5 ) 的距离正则图，且r = ，( r ) ，如果c r + = 5 ，则 d 2 r + 1 。且下列叙述之一成立 ( 1 ) 口，“= 6 ，且c a = 1 2 ，+ 2 d = r + f + 2 2 r + 1 ； ( 2 ) a r 十l = 5 ，且c r + 2 = = 白一l = 5 ，c d = 6 ，f 是l 一齐次图， ，+ 2 d = r + j + l 2 r + l 且r 2 由引理2 2 2 ( 2 ) ，c r + 。= 5 时，则a r “= 5 ，6 ，7 故需证明定理4 1 ，我们首先证明 a t + ，7 为此，我们先引入下面的引理： 引理4 2 设r 是序为( 2 ，5 ) l n g 巨离正则图，且，= ，( r ) ，则对任意x d 爿，有 e ( x ，研) 1 特别的，当( q + 1 钆1 ) = ( 5 ，5 ) 时“= ”成立 证明：假设存在x 础，使得p ( 五研) 1 设只，刁r ( 功n 珥因为对 1 s f 蔓r 一1 ，有乞+ l = 1 所以设 ”一 = r ( ”i ) n 明， 刁一， = r ( z 。+ 1 ) n 皑显然y 。z r ，特别的，m 刁且咒，z i 纠，这与q = 1 矛 盾，因此对任意x 列，有e ( x ，研) 1 当( o + ，口，+ 。) = ( 5 ，5 ) 时，用两种方法计算p ( 群，r + + 。1 ) 一方面，设 一锈铲 显然0 如虬铲方面，对任意膳札啪吐故 有f 硝l 所= i 珥i 印，整理可得m 2 嚣q 代入( c ，一q + 1 ) = ( 5 ，5 ) 及砟2 l ，有 1 3 m = 1 即p ( 蟛，v r r + l ，、= i 制i 从而对任意的x e 喇，当( 钆。，口，。) - - ( 5 ，5 ) 时，有 e ( x ，研) = 1 引理4 3 设r 是序为( 2 ，5 ) 的距离正则图，且，= ，( r ) ，如果钆l = 5 ，则 g r “7 证明：假设l = 7 ，n d = r + 1 我们断言任意的x e 制，有p ( x ，研) = 1 若否，即存在x 剜，使得e ( x ，彤) = 0 则有a ( x ，y ) = ，+ 1 又由于o + 。= 5 ， 令 w l ，w 3 ，w 4 ， = 取1n r ( 石) ， 确，现，r 3 ，r 4 ，r ， _ 研“n r ( x ) 由命题2 2 1 每个c ，+ l 一图是余团，必有a ( w j ，) = a ( 研，) = ，+ 1 ，f = l ，2 ，5 故 ，w 2 ，鸭，w 4 ，比，r h ，r h ，r h ，r 4 ， 4 + l ( 工，) 与q “= 7 矛盾故对任意的 x 明，有p ( 工，髟) = 1 断言成立 再计算彤和列之间的边数 e ( 。：，研r + l = l 珥l 6 r = l 明l t l ，得1 = 詈不可能从而必有g r + i ：g ：7 - 由引理4 3 可得d r + 2 下面先讨论( c ，+ l q + l 以+ 1 ) = ( 5 ，6 ，1 ) 的情形 当( o 。q + p k 。) = ( 5 ，6 ，1 ) 时，由命题2 2 1 对任意的x f ，+ 1 以) ，其领域结构 如图4 1 所示 ， ，十1，+ 2 图4 1 由图4 1 可知，每个c + ：一图是若干个k 的并又因为每个c ，+ ：一图都包含 某个c r + 一图，且每个c ，。一图是顶点数为5 的余团，故c r + ：= 1 0 或1 2 1 4 引理4 4 令r 是序为( 2 ，5 ) 的距离正则图，且，= r ( r ) ，令( q + l ，a r + i ，6 ，+ ，) = ( 5 ，6 ，1 ) ，假设d = ，+ 2 ，则有c ，+ 2 = 1 2 证明：若否，则c r + 2 = 1 0 由图4 1 可知，r 中不存在关于任意一条边的( 1 ，1 ，1 ) 和( 1 ，2 ，2 ) 类型点，故对 任意的x 碟u p 等有o ( x ，y ) = ，+ 1 且对任意的x p 箸，有o ( x ，) = ，+ 2 ； 石d 搿，有i o ( x ，) ，+ 1 故对任意的x e 鹾，有c ，+ ：( x ，) c 簖k - ) r + 2 又由于o + ：= 1 0 及鹾中 点的对称性可得e ( x ，喇) = e ( x ，r 。+ 2 ) = 5 ，与钆，= 2 矛盾，故q + ：1 0 ，从而 c ，+ 2 = 1 2 定理4 1 ( 1 ) 的证明： 证明：设 ，+ 1 ，a r + 1 6 ，+ 。) = ( 5 ，6 ，1 ) 当d = ，+ 2 时，由引理4 4 得，c 。2 = 1 2 ，并且 此时t = 0 ，即d = ，+ f + 2 ，结论成立。 当d r + 3 时，有命题2 2 0 ，a m 0 从而有( c ，+ 2 ，口，+ 2 ，6 ，+ 2 ) = ( 1 0 ，l ，1 ) 从而对 任意的x f ，+ 2 ) ，其邻域如图4 2 所示 ，+ zr + 2 ，q - 3 盈昏孕2 由图4 2 可知，每个c ，+ ，一图是若干个的并，又知每个c ，+ ，一图都包含某 个c ，+ 2 一图，且q + 2 = 1 0 ，于是q + 3 = 1 0 或1 2 通过类似讨论，显然有( + 3 ，3 ，6 r + ，) = 一( 白_ ”a a - l ，一1 ) = ( 1 0 ，1 ，1 ) 且 1 5 白= 1 0 或1 2 如果白= 1 0 ，则= 2 0 则由命2 1 9 ( 2 ) ，k = ( 嘞+ 1 ) = 6 1 2 矛盾因此白= 1 2 由屯= 急篓三等= 揣及如的整数性，可知t = r o ) n 列以上这些点中，有 w 1 ，心，编，仍，u 2 r ，+ l ( ，) 考虑毋( x ，y ) 及6 ，= 1 0 可得，屯，舅，奶中必有 两个点，不妨设m ，y 2 ，缉( x ，) ，从而有勇= 死= ( 1 ，1 ，1 ) 与上面的断言础中不 存在( 1 ，1 ，1 ) 类型点矛盾从而可得爿中也不存在( 1 ，0 ，1 ) 类型点 但考虑研和刚之间的边数，有6 ，= 0 得矛盾从而可推知当q + = 4 时， 贝u 口，“7 定理5 1 ( 3 ) 的证明： 证明：当d = r + 2 时，结论自然成立因此假设d 3 ，显然钆2 1 2 峨，= 甓鬻= 等甄：的整她可：钉j 1 1 因为( q + l ，口，+ l ，6 ，+ 1 ) = ( 4 ，5 ，3 ) 且c + 广图是余团，则对任意的x r ，+ l ) ，其 邻域如图5 2 所示断言q + 2 1 0 否则由命题2 5 知2 0 故有 ( c ，十2 ，g r + 2 ，b e + 2 ) = ( 1 0 ，l ，1 ) ，且对任意的x e f ，+ 2 位) ，其邻域如图5 3 所示 一一 邕p 由图5 2 可知，耳+ 。一图= 毛u 岛因此，对任意的x 研”，设以，耽，y 3 = v ( x ) n 蝣且y m ，咒儿y 另一方面，由图5 3 可知c ，+ ：一图= 5 屯因为 x c r + ： ，j ，) ，所以一定存在z r ) n 酬使得x z ，这样，z ，y 4 ( x ，j ，) 与 口l = 1 矛盾( 见图5 4 ) 故得c ，+ 2 1 0 断言q + ：4 ，若否c 。= o + ：= 4 由于每个e + ：一图都包含某个c ，+ 。一图且 e + 。一图是余团，所以可知c ，+ ：一图也是余团但由图5 2 知f 中存在a 川，其 中x ，w j r ，+ l ( 口) ，w 2 f ，+ 2 ( c r ) ，即石，f ，+ l ( a ) n r ( w 2 ) = c r + 2 ( 口，w 2 ) 且x 一嵋， 矛盾故c ，+ 2 4 断言c r + 2 9 若否，由命题2 2 0 知，口，+ 2 0 ，则对i = l ，2 , - - - , d l 有 q m i n b , ，q ) 可得( q 。a r 。6 ，+ ：) = ( 9 ，2 ，1 ) 且对任意的x f ，+ 2 ) ，其邻域由 图5 5 给出 2 1 渗拿 由图5 5 可知，每个c + 3 一图是若干个k 2 的并，又c r + 2 = 9 ，故c r + 3 = 1 0 - 2 戈1 2 ， 又由七，+ ，= 芋羰及颤+ ，的整数性可知。+ ，1 2 从而c ，+ ，= l o 若d = ，+ 3 ，即a r + ，= 2 首先断言p ( 赠，彰r + + ：3 ) = 0 由e + ，一图= 5 岛及 c r + ：= 9 可得又由于以+ - - 1 ，故对任意的x 鹾，有e ( x ，纠r + + ，3 ) = 1 又因为 a r + ，= 2 ，所以对任意的x 明，有口( x ，纠r + + 2 3 ) 2 下面来计算碟和硝之间的边数有f d 2 3j 2 i d r + 3j ，整理后可得 c r + 3 2 c i r + 3 ，即1 0 2 2 = 4 矛盾从而d ，+ 3 若d r + 4 ，必有( c r + 3 ，a r + 3 ，6 ，+ 3 ) 一一( 白十a a - i ，一1 ) = ( 1 0 ，1 ，1 ) ，且每个g 一 图是墨的并，从而c a = 1 0 或1 2 若白= 1 0 ，则a d = 2 由命题2 1 9 ( 2 ) 有 k - = a d ( a a + 1 ) = 6 与k - - 1 2 矛盾，故白置1 2 此时如= # 曼是揣= 而罢矗不是整数，矛盾故必有c ，+ z 9 因此，综上可知，当d ，+ 3 时，c ，+ 2 = 5 ，6 或8 定理5 1 ( 3 ) 证毕 - 定理5 1 ( 4 ) 的证明： 证明：若( c ，+ ，a t + ，6 ，+ ，) = ( 4 ，4 ，4 ) 及每个c ，+ ，一图是余团，可知对任意的 x r 。 ) ，其邻域如图5 6 所示 螯 - d 毒迫! 幻 亏；萄、 ：r j 由图5 6 可以看出，每个g + ：一图是余团又每个c + ：一图都包含某个c ，+ 。一 图，故有4 sc ，+ 2s 6 下面就来证明若c r + 2 = 5 ，则a r + 2 7 假设( q + 2 ，a r + 2 ) = ( 5 ，7 ) ，则d = ，+ 2 由图5 6 可知，r 中不存在关于任一条边 的( 1 ，1 ，2 ) 类型点，故能u d r + 2c r m ( 力又由引理5 2 可知，对任意的x 三纠 有i = ( 1 ，o ，1 ) 我们断言对任意的y 硝，有e ( y ，纠r + + 1 1 ) 1 即对所有的y 磷， 有夕= ( 2 ，1 ，2 ) 若否，即存在y 蟛使得e ( y ，纠r + + 。1 ) = 0 从而歹= ( 2 ，2 ，2 ) 由于 q + 2 = 5 ，从而不妨设 m ，w 2 ，w 3 ，w 4 ，w s = r ( y ) n r + 。l ， r 1 ，r 2 ，仉，r 4 ，r s = r ) 1 7 r + 。2 ，且a ( w ，y ) = a ( 吃，y ) = r + 2 ，i = l ，2 ，5 从而有w ，r , 4 + 2 0 ，y ) ， i = l ，2 ，5 与c r + ：= 7 矛盾故对任意的y d ；2 ，有歹= ( 2 ，1 ，2 ) 下面考虑 c + 。( y ，y ) ，必有c + l ( y ，) 明由q + = 4 ，有e ( y ，喇) = 4 又因为 三喇c r ，( ，明u d r + 7 c r ，+ 2 ( 厂) ，故有口( 彰r + l ，+ l 五名) = p ( r + l ，+ l 彰r “+ 2 ) = 0 又因 为6 ，“= 4 ，从而对任意的x d r r + l 有e ( x ，纠r + + 2 2 ) = 4 考虑集合制和硝之间的边数我们有i 刚i k 。一- - i q r + + ：2 i 4 即 l r + + l 一- - l 坼r + + ：2 1 经计算整理可得口，+ = 口m ，即4 = i 4 7 矛盾从而当c r + ：= 5 v r + 2 一 时，有a h 。7 参考文献 1 e b a r m a la n dt i t o a l g e b r a i cc o m b i n a t o r i c si b e n j a m i n c u m m i n g s ， c a l i f o r n i a , 1 9 8 4 2 eb a n n a ia n dt n o o nd i s t a n c e r e g u l a rg r a p h sw i t hf i x e dv a l e n c y ，l ig r a p h s a n dc o m h i r u 3 nl b i g g s a g b o s h i e ra n dj s h a w e - t a y l o r , c u b i cd i s t a n o e - r e g u l a rg r a p h s j l o n d o nm a t h s e e ，1 9 8 6 , 3 3 ( 2 ) ：3 8 5 3 9 5 4 ae b r o u w e r , amc o h e n ，a n da n e u m a l e r , d i s t a n e - r e g u l a rg r a p h s ，s p r i n g - e rv e d a y , b e r l i n ，5 h e i d e l b e r g ，1 9 8 9 5 n i b i g g s a l g e b r a i cg r a p ht h e o r y , c a m b r i d g eu n i v e r s i t yp r e 船, c a m b r i d g e , 1 9 7 4 6 a h i r a k i ac i r c u i tc h a s i n gt e c h n i q i l ei nd i s t a n c e - r e g u l a rg r a p l i sw i t ht r i a n g l e s e u r o p j c o m b i n 1 9 9 3 , 1 4 ：4 1 3 4 2 0 ， 7 a h i r a k i ，c i r c u i tc h a s i n gt e c h n