（基础数学专业论文）d界距离正则图中强闭包子图的一些性质.pdf

可北师范大学硕士学位论文 中文摘要 本文研究r 是直径为d 的出界距离正则图给出了r 中强闭包子图的一些性质，强 闭包子图计数所得结论如下； 1 设r = ( x ，e ) 是直径d 歹的出界距离正则图。和，是r 的两个强闭包子 图设 j = m x a ( 茹，) f a ，暑，) ， 则包含和7 的最小强闭包子图的直径是歹特别地。当n ，妒时。有 j d ( a ) + d ( z x ) 一d ( a n ) 2 ，设足r 的个直径为t 的子空间，0 t d i - t 算- z a 的补子空间的个数 关键词： 距离正则图，击界，强闭包子图，子空间。补子空间 d 一界距离正则图中强闭包子图的一些性质 a b s t r a c t i nt h i sp a p e r ，w es t u d yt h ed - b o u n d e dd i s t a n c e - r e g u l a rg r a p hrw i t hd i a m e t e rd w e o b t a i ns o m ep r o p e r t i e so fs t r o n g l yd o s e ds u b g r a p h si nra n dt h ef o r m u l ao fc a l c u l a t i o n o fs t r o n g l yc l o s e ds u b g r a p h s t h em a i nr e s u l t sa r e 鹪f o h o w s 1 l e tfd e n o t e8d - b o u n d e dd i 窘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 ja n dl e t a n d b et w os t r o n g l yc l o s e ds u b g r a p t m s u p p o s e 歹= m a x 0 ( x ，暑，) i $ ，| ， t h e nt h ed i a m e t e ro fm i n i m a ls t r o n g l yc l o s e ds u b g r a p hc o n t a i n i n g a n da | i s m o r e - o v e r ，i f n 7 毋，t h e n j d ( a ) + d ( a ) 一d ( a n ) 2 l e t b eas u b s p a c ew i t hd i a m e t e rio fr ，w h e r e0 d w eo b t a i nt h en u m b e r o fc o m p l e m e n t a r ys u b s p a c e so f 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 ，d - b o u n d e d ，s t r o n g l yc l o s e ds u b g r a p h s ，s u b s p a c e s ， c o m p l e m e n t a r ys u b s p a c e s 河北师范大学硕士学位论文1 第一章绪论 1 1 课题背景与发展概况 距离正则的概念是上世纪七十年代，由英国数学家b i g g bn l ，提出的i 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 ot 等建立了 距离正则图的基本理论框架距离正则图是距离可迁图的组合推广，同时又等价于p 一多 项式方案 2 1 ，在距离正则图的定义中，尽管只假定了组合正则性而没考虑自同构作用的 对称性，但大多数距离正则图有足够大的自同构群，使得它在距离相等点对集合上的作 用是传递的，因此有的专著把距离正则图q 做。无群的群论嘲距离正则图还与设计 7 l ，编码陋1 1 1 ，有限几何【1 如1 4 1 ，有密切联系目前距离正则图的研究很活跃，已成为代 数组合论的一个重要分支 我们知道，距离正则图中强闭包子图性质及应用是距离正则图研究中的一个重要内 容我们首先介绍一下关于距离正则图中强闭包子图的研究情况 1 9 9 6 年，s u z u k ih i r o s h i 【1 5 1 研究了几何围长为5 的强闭包子图，并给出了直径为f 的强闭包子图存在的条件 1 9 9 8 年。h i r a ma k i r a 【1 8 l 利用强闭包子图的构造定理研究了距离正则的性质，得 到了参数间的一些关系 w e n gc h i - w e n 1 7 , 1 s 1 在出界距离正则图中研究了正则的强闭包子图( 子空间) ，得到 了关于子空间的许多性质，并利用这些性质得到了直径d 4 ，交叉数c 2 1 且口l 0 时的距离正则图的分类 本文对出界距离正则图子空间的其它一些性质进行了研究，引入了子空间的补空间 的概念，给出了补空间的计数公式 2 d 一界距离正则图中强闭包子图的一些性质 1 2 本文综述 本文共分4 章第1 章阐述了课题背景及发展概况第2 章为预备知识，着重介绍了 后面几章中要用到的一些符号，概念和基本结论第3 章研究了出界距离正则图中强闭 包子图的一些性质及第4 章研究了补子图的计算主要结果是： 定理3 1 1 设r = ( x ，e ) 是直径d j 的出界距离正则图，和是r 的两个 强闭包子图设 歹= m a x a ，u ) l x ，f ， 则包含和的最小强闭包子图的直径是j 特别地。当n 7 妒时，有 j d ( a ) + d ( a ) 一a ( h n 7 ) 定理3 1 9 设r 是一个直径d t + 1 的出界距离正则图取定茁y ( r ) 和 整数 ，t 十1 i d ，如果存在一个直径为t 的子空间，使得关于的形为 一t + s ，i 一+ 占+ 1 ，l 一1 ，蕾) ，0 s t 那么r 一( z ) n 是一些赢径小于等子 s 的子空间的不交并 定理4 1 2 设r = ( x ，司是直径为d 的出界距离正则图，是r 的个直径为i 的子空间，0 i5d 则的补予空间的个数是 ( - + 骞坠堂寄鼍啦型) 矸诵硭茜尚翻 坷北师范大学硕士学位论文 3 第2 章预备知识 本章介绍距离正则图的基本概念和基本性质 2 。1 基本概念 我们给出图的定义和习惯记号关于距离正则图的其它知识。读者可参考专著【2 l ， 定义2 1 1 设x 是个集合，e 是由x 的一些元的无序对构成的集合则我们称 集合对r ：= ( x ，e ) 是个图其中x 称为图r 的顶点集合，用v ( r ) 表示而e 称为 图r 的边集合，用e ( r ) 表示 在本文我们恒假定图为有限的，鄞l x l t + j ，乒 t + l 或t j + z ( 4 ) 西1 = 向p 乏l = 岛矗 命题2 2 2 1 19 l 设r 是一个直径为d 的价为知的距离正则图那么 ( 1 ) 七= q + 玩+ a i = 0 ，1 ，d ) ( 2 ) g o = o , o ；= 0 ，c l = 1 且6 0 = 忌 6 d 一界距离正则图中强闭包子图的一些性质 ( 3 ) 令：= 醒i 则6 = c + 1 七计1 ( 主= 0 ，1 ，d 一1 ) ( 4 ) 设t 和t ，是r 的两个点且加d ( 口，让) 那么g ，t j ) c 口( u ，口) 且日细， ) ) b ( u ，t ，) ( 5 ) c c 4 + x 且6 l 6 + 1 ( 0 l ，歹d 一1 ) ( 6 ) 设t ，t ，f 如果 a r ( u ，”) = o r ( u ， ) + a ( t ， ) 那么c ( 乱，伽) cb ，叫) ( 7 ) 玩2 白，如果i + 歹d ( 8 ) b ，如果0 l j 且+ j d ( 9 ) 这些具有单峰性，即存在整数h 和z ( 1sh z 回使得 1 = k t 幻1 ( a o ) 设0 i 屯+ l ，0si d 一1 图 设z ，z y ( r ) 沿用文献【1 5 1 的记号，用霉，z 表示包含z 和z 的最小强闭包子 8d 一界距离正则图中强闭包子图的一些性质 引理3 1 5 设r 是一个直径为d 的出界距离正贝! l 图那么( 1 ) ，( 2 ) ，( 3 ) 成立 ( 1 ) 对任意善，y 矿( r ) ，包含z 和y 且直径为a ( 毛) 的子空间有且只有一个，它是 $ ，! ， ( 2 ) 设和，是r 的两个子空间，c ，并且存在z ，使得z 在和，中 有相同的价那么= ， ( 3 ) 设是r 的强闭包子图。是的强闭包子图。则是r 的强闭包子图 证明( 1 ) 这是命题3 1 3 ( 3 ) 的直接推论 ( 2 ) 设d ( a ) = d l ，d c a ) = d 2 由命题3 1 3 ( 2 ) 可知，和7 都是距离正则的。并 且 奄( ) = 6 d 一。，k ( h ) 一6 口一五如 又因为z 在和，中价相同，所以七( ) = k ( a ，) 于是b d ，= 6 也再由命题3 1 4 可 知，d i = d 2 最后由( 1 ) 可得，号 ( 3 ) 对任意z ，y a ，因为是的强闭包子图。所以占，yea 于是由是r 的 强闭包子图可知， a ( z ，暑r ) ue ( 。，暮，) ca 因此。是r 的强闭包子图 引理3 l 6 设r 是一个直径为d2 j 的出界距离正则图和，是r 的两个子空 间再设 j = m a x a ( 2 ，f ) i z ，暑，a ， 则存在唯一直径是j 且包含和的子空问 证明设z ，薯，a ，使得a ( 霸暑，) = 歹令= 翰毫，因为y ，n ，所以 ，n 毋于是由命题3 1 3 知，n 是个子空问设t 是，中与y 相邻的任一 点，则a ( 石，t ) = 歹一1 或j 于是由是子空间得，“g ( 戤毫，) u a ( 毛暑，) c 厶说明 中与y 相邻的点都在中因此。玑在n 和，中有相同的价则由引理3 1 5 ( 2 ) 可知，n 厶= ，进而有，c 厶同理可证。 c 厶再由引理3 1 5 ( 1 ) 知，厶是 唯一包含和，且直径为j 的子空间 引理3 1 7 设r 是个直径d t + s + 1 的击界距离正则图，和，分别是直径 为 + s 和 + 1 的子空间，并且d ( h n ) = 0 设是包含和，的最小子空 问，那么 d ( a ) + d ( ) = d ( h n ) + d ( ) 河北师范大学硕士学位论文一 9 证明因为a ( z x n ，) = i ，所以存在z ，l ，n ，使得烈z ，! ) = t 由z ， n c 可知，在中存在点列。= 乱o ，”l ，一z ，使得 t l b ( u ，u l 1 ) n ，1 zs 8 于是，o ( u ，。) = l + s 进而由引理3 1 5 可知，= ! ，z ，n a i = 可，z 因为d ( ) = t + 1 ，所以存在叫b ( 窭，暑，) n ，使得a ( z ，t ，) = t + 1 断言：存在 “b ( z ，掣) n ，使得o ( z ，让) = i + s + 1 事实上如果对任意u b ( z ，| ，) n ，都有 o ( z ，钍) s + s 则由是子空间知，乱g ( z ，! ，) u a ( z ，可) c 于是，b ( ，掣) n ，c n 7 这与n ，的直径是i 矛盾设钍b ( z ，蓦，) n ，使得o ( z ，u ) = i + s + 1 则由 距离的三角不等式可知。 a ( 霉，t ) o ( u ，石) 一a ( z ，z ) = l + 1 注意到d ( a 7 ) = - l ，故a ( 正，= t + 1 进一步，由引理3 1 5 知，a 7 = z ，t 因为z ，u 是包含和且直径为i + s + l 的最小子空间，所以厶= 名。 因此得证 引理3 1 8 设r 是一个直径d 2 i + 8 + t 的击界距离正则图，和，分别是直径 为i + s 和t + t 的子空间，并且a ( z x n ) 一i20 设厶是包含和，的最小子空 问，则 d ( z x ) + a ( z x ) d ( n 7 ) + d ( 厶) 证明对t 用归纳法当t = 0 时结论显然成立由引理3 1 7 知，t = 1 时结论成 立假设t 一1 时结论成立，下证t 时结论成立 与引理3 1 7 的证明类似，可找到霉，弘z ，使得o ( z ，| ，) = i , o ( z ，力= 矗，o ( z ，暑，) = i + 8 再由引理3 1 5 知，z ，! ，= n ，z ，v = 因为d ( ，) = t + t ，所以， 中存在点列| ，= 咖， 1 ，仇一l 满足 q b ( 。，q 1 ) n ，1 z t 一1 于是，a ( z ，仇1 ) = i + t 1 令厶一z ，仇一1 则厶是中包含n 且直径为 l + 一1 的子空间 设包含和厶的最小子空间是因为n 厶c n ，$ ，= n ，所 1 0d 一界距离正则图中强闭包子翻的一些性质 以n ac z ，! ，又因为茁，o 厶，故由引理3 1 5 知， n 厶；z ，暑，于 是，由归纳假设可得 d ( ) sd ( a ) + d ( 厶) 一d ( z x n 厶) ；a + 8 ) + 0 + t 一1 ) 一i = + s + t 1 由上面的讨论容易看出，厶c n a t ，d ( a + ) 0 + t 一1 ) + s ，烈厶) = id - t 一1 ， d ( 7 ) = 0 + t 一1 ) + 1 因为厶c a n 7 c ，所以a a a ，_ 压或，如果岔n a = ， 则，c 于是由i 是包含和厶的最小子空间和厶c 可知，。是包含和 “的最小子空间。并且d ( z x ) t + b + t l i + s + t 如果a n a = 厶，则由引理 3 1 7 得 d ( a ) = d ( a ) + d ( 7 ) 一d ( z x n ) “+ 8 + t 1 ) + a + t ) 一a - i - t 一1 ) = t + 8 + t 其中厶是包含和，的最小子空闯又因为厶是包含和，的子空闯，所以，如 果记1 为包含和，的最小子空间，则a 1c 厶于是，d ( 1 ) d ( a ) i + 8 十t 定理3 1 1 的证明 证明这是引理3 1 ，6 和引理3 1 8 的直接推论 设i 是一个宜径d t 的距离正则图，是r 的直径为t 的强闭包子图取定 o v ( r ) ，设 s = i l o d ，r ( z ) n a 妒) 称s 为关于写的形 定理3 1 9 设r 是一个直径d t + 1 的出界距离正则图取定盂y ( r ) 和 整数t ，t + 1 f 盔如果存在一个直径为t 的子空间，使得关于$ 的形为 i t + s ，i t + s - p 1 ，t 一1 ，硌，日s s t 那么r t 一舢( z ) n 是一些直径小于等于 s 的子空同的不交并 证明设e 是r h + j ( 霉) n 中的个连通分支下证g 是直径ss 的子空间 设 g ，而是包含$ 和伽的直径为 一t + 5 的子空间由引理3 1 5 知， 河北师范大学啊士学位论文1 1 = 正， 对任意t n a i ，由“e ，知，烈z ，“) si t - i - s 再由“知， a ( z ，“) f t + 8 故a ( x ，u ) = l t + s 说明t r i 一“。( $ ) n 由命题3 1 3 0 ) 知， n ，是子空间，从而它是连通的于是，n ，cd 反之，对任意a 在g 中 存在点列t ，= v o ，t l i ，铆= 乱，使得吩与码+ l 相邻。0 歹z 一1 予是，由是子 空问知，码+ l a ( z ，v j ) c ，0 j l 一1 说明t 因此， ac n ，迸一 步。c = n 由引理3 1 6 可知，存在唯一直径为 的子空间厶包含窖和显然厶是包含 和的最小子空间于是，由引理3 1 8 得 d ( a n ) sd ( a ) + d ( a ) 一d ( 厶) = & 1 2d 一界距离正剐图中强闭包子图的一些性质 第4 章补子图的计算 首先给出补子图的定义 定义4 1 1 设r 是直径为d 的出界距离正则图，是r 的一个直径为i 的强闭包 子图，0 i d 称强闭包子图为的补子图，如果( 1 ) ，( 2 ) ，( 3 ) 成立 ( 1 ) d c a ) = d 1 ( 2 ) d ( ana 7 ) = 0 ，即恰相交于一个顶点 ( 3 ) 包含和的最小强闭包子图是r 本章得到下面主要定理 定理4 1 2 设f = ( 五e ) 是直径为d 的击界距离正则图，是r 的个宣径为i 的子空间，0 t d 则的补子空间的个数是 ( - + 骞坠坐兽鼍堕型矿诵硭筠篙翻 证明设z ，暑，a ，o ( x ，毫，) = i 。则由引理3 1 5 ( 1 ) 知，a = 留，分在r 中取点 列蓦，= 锄，“1 ，抛一= 磊使得 铆b b ，一1 ) ，1 z d i 则由理3 1 5 ( 1 ) 知，= | ，u d - 是个直径为d i 的子空间因为在i 中点列 锄，l ，锄一的取法为 氏玩+ l 6 d 一1 ， 并且得到同一个t d t 在r 中只有扣c d q l 龟c 1 个不同的点列，所以r 中共有 e ：垒堡! ：塾生! c l c 2 c d t 个满足a ( 茁，z ) = d ，o ( u ，z ) = d t 的不同点z 因此，得到e 个( 相同的按出现的次效 计) 直径为d i 的子空阀l ，z 我们断言；这些子空间管，名都是a 的补子 空问事实上，定义4 1 1 ( 1 ) 和( 3 ) 显然成立设，是这e 个补子空间中的任个，则 暑，a n ，于是，由命题3 1 3 ( 1 ) 可知，a f l a 是子空间再由引理3 1 8 知， d d ( a - ) + d ( a ) 一d ( n a ) 河北师范大学强士学位论文 = d d ( n ，) 即d ( a n ) 0 说明n = 订因此，定义4 ，1 1 ( 2 ) 成立 下面考虑在上述计数中，的每个补子空间重复的次效设，是的个满足 n a = 妇) 的补子空间。则可毒中取点列三，= 1 l o ， l ，呦_ = 幺使得 1 j b ( u ，坳一1 ) n ，1 歹d i 则与前面同样的道理，并由命题3 1 3 ( 2 ) 可得7 中共有 一：l 鱼= 垒苎= 尘l ! ! 二堕= ! ! ：( 坠= ! = ! = 坠= 尘 c l c 硷。，d i 个满足o ( u ，锄一) = d t 的不同点4 我们断言；a ( $ ，抛_ ) 一d 现在用数学归纳法 证明结论ta ( z ，q ) = t + j ，0 j d i 当j = 0 时结论显然成立当j = 1 时，因o ( u ，t 1 ) = 1 ，所以，i 一1so ( x ，u 1 ) + l 如果t 一1 a ( x ，t 1 ) ，则由a = ，l ，是子空间可得，“l a ( x ，l ，) u c ( $ ，| ，) c 这与n = ) 矛盾因此。a ( z ，让1 ) 一t + 1 假设当j z 时结论成立，即 毋( ，姐) = t + f ，a ( ，撕) = 1 当歹= z + 1 时，因为铆+ i 口( 暑，铆) n 7 ，o ( x ，地) = i + f ，所 以t + z 一1 烈，t 件1 ) + z + 1 如果i + z 一1 a ( 。，蛳+ 1 ) i + z 。那么由。，铆 是子空间知，m + l o ，铆于是，t f + l z ，铆n ，由引理3 1 8 得 d d ( z ，蛳) 4 - d ( 7 ) 一d ( 霉，硼n ，) = + z + d 一一d ( 卫，锄n ) 即d ( z ，铆n a 7 ) 1 因为掣茁，t l ，并且o ( u ，牡1 ) = l ，所以z ，如 n 7 = l ，铆进一步得 t l + 1 暑，t 向 再由蛳+ 1 b ( y ，撕) n ，可知，a ( 暑，t l + 1 ) 一1 + 1 ，这是个矛盾说明a ( $ ，“l + 1 ) = 件h 1 特别地，a ( 。，一i ) = d 说明，上面得到的e 个补子空闯中，每个都重复了一次 设，是满足a n n = 奶瑚a 的个补子空间下面证明；，必是上面e 个补 子空间中的个令 j = m a x a ，删) l 恤) ， 则存在z 刽，使得a ( 。，2 ) ；j 再由引理3 1 6 知，存在唯一直径为j 且包含 对和 的子空间，设为厶由于暑，a c 厶。故a = $ ，l ，c 厶说明厶是一个包含和 1 4 d 一界距离正则图中强闭包子图的一些性质 a 的子空间从而= r 进而歹= d 再由a ( ! ，z ) 0 ( x ，z ) 一a ( ，v ) = d 一 和7 的 直径为d 一可知。a ( y ，。) = d t 于是，由引理3 1 5 知，暑，z = a 是上述e 个 中的一个 因此，满足n 7 = t 订的a 的补予空间a 的个数是参，最后，由命题2 2 2 ( 1 1 ) 和命题3 1 3 ( 2 ) 可知。 l i 叫+ 骞坠地喾掣 因此，的补子空间的个数是 i l 丽= i 预i b i j b i + 云1 f b l d - 1 瓦= = = = 瓦j 河北师范大学啊士学位论文 1 5 参考文献 【1 1 1b i g g sn l ，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 et r a c t si nm a t h 6 7 ， b r i d g eu n i v e r s i t yp r e s s ，c a m b r i d g e1 9 7 4 【2 】2 b r o u w e ra e ，c o h e na m a n dn e u m a i e ra ，d i s t a m e e - r e g u l a xg r a p h s , s p r i n g e rv e r l a g ，b e r l i n ，h e i d e l b e r g1 9 8 9 【3 1 b a n n a ie ，i t ot ，a l g e b r a i cc o m b i n a t o r i c s 工c a l i f o r n i a ，b e n j a m i n - c u m m i n g s 1 9 8 4 4 1 r o s er c a n dm e s n e rd m ，o nl i n e a ra s s o c i a t i v ea l g e b r a se o r r e z ? p o n d i n g 幻 a s s o c i a t i o ns c h e m e so f p a r t i a l l yb a l a n c e dd e s i g n s , a n n m a t h s t a t i s t 1 9 5 9 ，3 0 ：2 1 3 8 【5 】5 b i g g sn l ，d e s i g n s , f a c t o r sa n dc o d e si ng r a p h s q u a r t j m a t h o x f o r d 1 9 7 5 ，2 6 ( 2 ) ：1 1 3 - 1 1 9 【6 1 b i e rt ，l a t t i c e sa s s o c i a t e dt ot h er e c t a n g u l a ra s s o c i a t i o ns c h e m e , a mc o m - b i n 1 9 8 7 ，2 3 ( a ) ：4 1 5 0 f 7 l 万哲先，戴宗泽，冯绪宁，阳本傅，有限几何与不完全区组设计的一些研究。 科学出版社，1 9 6 6 ：1 - 1 2 4 【8 】b a n n e de ，c o d e sj 丑b i p a r t i t , ed 汛蜘协r 鲫l l a rg r a p h s , j l o n d o nm a t h ，s o c 1 9 7 7 ，1 6 ( 2 ) ：1 9 7 - 2 0 2 1 9 b a n n a ie ，o np e r e c tc o d e sj nt h eh a m m i n gs c h e m ej 了向，w i t hqa r b i 缸a r y , j c o m b i n t h 1 9 7 7 ，2 3 ( a ) ：5 6 - 5 7 1 0 b i g g sn ，p e r f e c tc o d e si ng r a p h s , j c o m b i n t h 1 9 7 3 1 5 ( b ) ：2 8 9 - 2 9 6 f 1 1 】d e s a r t ep h ，a na l g e b r 硒ea p p r o a c ht ot h ea s s o c i a t i o ns c h e m e so f c o d i n gt h e - o r y , p h i l i p sr e s e a r c hr e p o r t ss u p p l 1 9 7 3 ，1 0 1 6 d 一界距离正则图中强闭包子图的一些性质 【1 2 l 王仰贤，王春森，麻常利，特征为2 的有限域上二次型结合方案，科学通报。 1 9 9 8 ，4 3 ( 1 4 ) ：1 4 8 2 - 1 4 8 4 i r a h e m m e t e rj ，t h el a r g ec l i q u e si nt h eg r a p ho fq u a d r a t i c 向f 如鼠e u r j c o m b i n 1 9 8 8 。9 ：3 5 9 - 4 1 0 【1 4 】h u a n gt ，s o m er e s u l t so i lt h ea s s o c i a t i o n8 c h e m 锵o