（基础数学专业论文）几类seidel整谱图.pdf

摘要 图的特征值的集合称为图的谱设图g 是一个简单图，对于g 的s e i d e l 矩阵a 4 ( = j i 一2 a ，如果g 的s e i d e l 谱都是整数，就称g 是s e i d e l 整谱 图根据图的特征值来研究图成为了图谱中相对活跃的课题，而整潜图是 图的特殊一类，目前对整谱图的研究已取得了不少成果，但对于s e i d e l 整谱 图的研究成果还较少，本文主要利用邻接主特征值和s e i d e l 主特征值的关 系以及丢番图方程确定了图类q 心u p 玩，n 虬u p c p ( b ) 和a 玩，。u b c p ( b ) 中的所有的s e i d e l 整谱图，得到了如下结论： 确定了图类a 玩u z k , , ，q 玩u p c p ( b ) 和q 玩，。u , s c p ( b ) 中所有的s e i d e l 整谱图 例如：若a 虬up 风是s e i d e t 整谱图，则它是如下形式： 【等跏+ 了m e2 】甄孚册hu 睾珈+ 竺l n 学+ t z 】，m 其中( i ) 亡，七，z ，m ，e ，h n ，且( m ，n ) = 1 ，( ，e ) = 1 ； ( i i ) 丁= ( ( t 盐f - ) k + l m ，m e ) ，且7 i l 舰； ( i i i ) ( x o ，y o ) 是( ( 譬) 后+ l m ) x 一( m e ) 可= r 的一个特解； ( i v ) z z o ，z o 是满足下列条件的最小整数， ( 等时m 丁e z o ) l ，( 竽蜘+ 学牝1 本文利用邻接主特征值和s e i d e l 主特征值的关系，结合丢番图方程， 得到它们的具体表达式这是本文的主体部分 关键词：s e i d e l 整谱图，主特征值，丢番图方程，完全图，完全二部图，鸡尾 酒会图。 a b s t r a c t t h es e to fa l lt h ee i g e n v a l u e so fag r a p hi sc a l l e di t ss p e c t r u m l e tgb e as i m p l eg r a p ho fo r d e rn i t ss e i d e la d j a c e n c ym a t r i xi sd e n o t e db ya + ( g ) = j i 2 a ag r a p hgi sc a l l e ds e i d e li n t e g r a li fi t ss e i d e ls p e c t r u mc o n s i s t s e n t i r e l yo fi n t e g e r s t h ee s t i m a t i o no ng r a p h sb yi t ss p e c t r u mi sa na c t i v eq u e s t i o n f o rd i s c u s s i o n ，m o r e o v e ri n t e g r a lg r a p hi sas p e c i a lc l a s s t h e r ea r em a n yr e s u l t s a b o u ti n t e g r a lg r a p h s b u tf o rs e i d e li n t e g r a lg r a p h s ，t h e r ea r ef e wa b o u ti t t h i s p a p e rd e t e r m i n e sa l lt h es e i d e li n t e g r a lg r a p h so fq k o u8 k b ，o 【k 4 u 3 c p ( b a n d a 耽。up c p ( b ) m a i n l yb yt h em a i ne i g e n v a l u er e l a t i o nb e t w e e na d j a c e n c ym a t r i x a n ds e i d e la d j a c e n c ym a t r i xa n dd i o p h a n t i n ee q u a t i o n i nt h i sp a p e r ，w eo b t a i n t h a t d e t e r m i n a t i o na b o u ta l lt h es e i d e li n t e g r a lg r a p h so fa k au _ bk ，& k buz c p ( b a n da 玩。uf l c p ( b ) f o re x a m p l e ： l e tq k n u8k bi ss e i d e li n t e g r a l ，t h e ni t sf o r mi sf o l l o w e d ： a m o n g t i o n ， 【等勘+ 7 m e 名】墨半斛。u f 等珈+ ( 警) 七十l m ( i ) t ，k ，l ，n ，m ，f ，e ，h n ，a n d ( m ，礼) = 1 ，( f ，e ) = l ； ( i i ) 丁= ( ( 警) + l m ，m e ) ，a n d 叫地； a k m ( i i i ) ( x o ，y 0 ) i sas p e c i a lr o o to f ( ( 警) 惫+ l m ) x 一( m e ) y = 7 - ； ( i v ) 名z 0 ，z oi sm i n i m a li n t e g r a ln u m b e rw h i c hs a t i s f yt h ef o l l o w i n gc o n d i - ( 竽勋+ m 丁e z o ) _ 1 ，( 竽珈+ ( 警) 七+ l m 为) 之1 f i n a l l yw em a k ea p p l yo ft h em a i ne i g e n v a l u er e l a t i o na n dd i o p h a n t i n ee q u a - t i o n ，a n do b t a i nt h ed e t a i lf o r m s t h a ti st h em a i np a r to ft h i sp a p e r i i i k e y w o r d s ：s e i d e li n t e g r a lg r a p h ，m a i ne i g e n v a l u e ，d i o p h a n t i n ee q u a t i o n ，c o r n - p l e t eg r a p h ，c o m p l e t eb i p a r t i t eg r a p h ，c o c k t a i lp a r t yg r a p h i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识 到本声明的法律后果由本人承担 学位论文作者签名：慝玮色群 川年乡月7 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权属湖南师范大学，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内容编 人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密硒 ( 请在以上相应方框内打“ ”) 作者签名：易亿寄 导师签名镀耀千 4 1 日期：滞占月7 日 日期：冲年石月7 日 几类s e i d e l 整谱图 1 1 引言 1 综述 图论是一门内容非常丰富且应用十分广泛的数学分支，是近年来离散 数学和组合数学领域较为活跃的分支之一而图谱则是图论中的一个新 兴领域，它起源于理论化学家和物理学家为寻求一类偏微分方程的近似 解而建立起的一套离散的方法经过短短几十年的发展，图谱已经成为了 一个系统的、综合的理论分支它的研究与发展有着重要的理论和实际意 义，它不仅促进和丰富了图论和组合学本身的研究，而且在量子化学、物 理、计算机科学、通信网络即信息科学中均有广泛的应用正因为图谱有 着广泛的应用，目前很多学者都在致力于这方面的研究 图的特征值的集合称为图的谱如果一个图的谱都是整数，就称这个 图是整谱图整谱图这个概念是由f h a r a r y 和a j s c h w e n k 在1 9 7 4 年引入 的从此，许多有关的研究成果和文章得以问世但主要足关于无向图和 整谱树的，而对有向图却很少研究自从李学良和林国宁的论文问世之后， 在国内也涌现出一大批开始研究整谱树问题的学者 到目前为止，得到1 3 个连通三阶整谱图证明了一个固定度的连通正 则整谱图的集是有限的相似的，有界点度的连通整谱图集是有限的构造 出完全三部整谱图的无限族确定所有1 3 种最大度为4 的连通非正则非 二部整谱图确定所有2 4 个连通垂正则整谱图，它们的谱中没有3 和一3 发现了1 8 8 8 个垂正则二部整谱图可能的谱也确定了二部缸正则整谱图 潜在的谱研究了3 个不同特征值的一些图和有一些相关图族中的整谱图 的性质在二部半正则图的基础上，得到一些新的整谱图研究了没有特 征值1 和一1 的最大度为4 的非正n - 部整谱图 硕士学位论文 ( 一1 ，1 ，o ) 一邻接矩阵即是s e i d e l 矩阵j j s e i d e l 介绍了关于s e i d e l 矩阵形 成同谱图的过程，也即s e i d e l 转换j j 。s e i d e l 还做出了对s e i d e l 矩阵有特 征值3 的强正则图s e i d e l 整谱图是整谱图研究中的一个领域m l e p o v i d 对整谱图有较多的研究，他已经研究出属于不同图类的整谱图，如图类 o 虬”，口，6 6 ，。6 ， 1 2 基本概念 本文所研究的图均为无环无重边、有限无向的简单图设图g = ( ve ) 的顶点集为v ( a ) = ，) ，i v l = n 称为图g 的顶点数，又称为图g 的阶数；边集e ( g ) = 1 e 2 ，e m 】，l e l = m 称为图g 的边数若e 的两 个端点分别为顶点u 与顶点钐，记为e = ( u ，u ) = u v ，则称为顶点u 与顶点 影相邻接，记为钆一钉n ( v ) 表示与顶点v 相邻的所有顶点构成的顶点集 图g 的邻接矩阵记为a = a ( g ) = ( a 0 ) n n 是一个疗x 佗阶的( 0 ，1 ) 一方 阵，其定义如下：吼，： l 饥“吩 l 0 讧和 显然，a 菇= 0 ，a 嵇= a i ，故而a ( c ) 是一个实对称方阵我们称d e t ( x i a ) 为图g 的特征多项式记为p ( g ) 或p ( g ；p ) 它的特征值记为p - ，p 2 ，卢n ， 不妨将其由大到小排列为p l 之p 2 弘n 称s p e cg = p l ，弘2 ，鳓) 为 图g 的邻接谱g 的邻接矩阵a ( g ) 的特征值和特征向量称为图g 的特征 值和特征向量g ( 或矩阵) 的一个特征值p 称为主特征值，如果g ( 或矩阵) 有一个相应于p 的各分量之和不为零的特征向量，由非负矩阵的理论可 知，图的最大特征值( 谱根) 总是它的主特征值一个图恰有一个主特征值 当且仅当它是正则图如果g 的谱完全由整数组成，则称g 是整谱图 g 的s e i d e l 矩阵a = a ( g ) = j i 一2 a 是一个( 0 ，一1 ，1 ) 方阵我们 称d e t ( x i a ) 为图g 的s e i d e l 特征多项式记为s ( a ) 或s ( g ；旷) 不妨将 2 几类s e i d e l 整谱图 它的特征值由大到小排列为店店成称跏cg = 昧脏，戚) 为图g 的s e i d e l 谱g 的s e i d e i 矩阵a 4 ( g ) 的特征值和特征向量称为图g 的s e i d e l 特征值和s e i d e l 特征向量g ( 或s e i d e l 矩阵) 的一个s e i d e l 特征 值矿称为s e i d e l 主特征值，如果g ( 或s e i d e l 矩阵) 有一个相应于旷的各 分量之和不为零的s e i d e l 特征向量g 的s e i d e l 矩阵的主特征值称为g 的 s e i d e l 主特征值若g 的s e i d e l 谱完全由整数组成，则称g 是s e i d e l 整曾 图本文的工作是研究s e i d e l 整谱图 此外，还有些未给出的专业术语与记号将分别在文中的相关章节里给 出 1 3 一些已有的结论 在参阅了大量的文献后，本人开始了对s e i d e l 整潜图的思考本文仅 对图类。虬u p 玩，n u p c p ( b ) 和q 玩，口u f j c p ( b ) 中的s e i d e l 整谱图进 行了研究本文对于s e i d e l 整谱图的研究，主要是遵循对整谱图的研究方 法和利用s e i d e l 主特征值下面介绍一些整谱图的结论： ( 1 ) 文献【7 】中给出了利用顶点数，佗，和主特征值求补图的主特征值的 定理： 定理1 3 1 设图g 为n 阶简单图，且只有两个主特征值p l 和p 2 ，则 _ 1 。= 坚学士v ( p l - p 2 + 1 n ) 2 - 4 n 一1 ( # 1 - # 2 ) ， 其中万1 和_ 2 是g 的补图百的主特征值，n l = 礼钟，胁和阮是p 1 和p 2 的 主角 进一步，结合文献【4 】中给出了下面定理： 定理1 3 2d i o p h a n t i n e 方程a x + b y = c 至少有一个解当且仅当d ic ，其中 3 硕士学位论文 d = ( a ，6 ) 通解为 z = 三z 。一三z ，= 三珈+ i a y z ， ( z z ) z 2 孑z o 万z ， 2 i 珈+ i z ， 【z z ) 其中( 黝，y o ) 表示方程a x + b y = d 的一个特解 ( 2 ) 文献【9 】中给出了利用顶点数，边数和主特征值求补图的主特征值 的定理； 定理1 3 3 如果佗个顶点m 条边的简单图g 恰有两个主特征值p l ，p 2 m i 是g 的最大特征值) ，g 的其它特征值为p 3 ，则g 的补图召的特征 值为_ l ，一2 ，一1 一p 3 ，一1 一，其中 耻：学士迈v ( # l 互+ # 2 乏+ n ) 2 雯- 4 p i p 2 - 8 m ( 3 ) 文献【5 】中给出了利用顶点数，礼。和主特征值求s e i d e l 主特征值的 定理： 定理1 3 4 设图g 为扎阶简单图，且只有两个主特征值弘1 和弘2 ，则 舻垡学士煎耍五乒觋，( 1 - 0 其中弘：和废是g 的s e i d e l 主特征值，且馆l = 懈，伪和尾是弘1 和p 2 的 主角 4 几类s e i d e l 繁谱图 2 图类及心up 中的s e i d e l 整谱图 a 玩up 托是由a 个玩加上p 个蚝构成的图本章主要利用定理 1 3 2 和定理1 3 4 确定了图类q 虬u p 玩中的s e i d e l 整谱图 2 1 及瓦u 玩中s e i d e l 整谱图的一般形式 由定理1 3 4 可知，若g 是整谱图，那么g 是s e i d e l 整谱图当且仅当g 的s e i d e l 主特征值是整数 对任意o l ，p ，a ，b n + ，a b ，则q 玩u p 心是整谱图，且恰有两个主特征 值弘l = a 一1 和芦2 = b 一1 o 玩u 玩的阶为0 = a 8 + 6 由( 1 1 ) ，得 p 净竺竺兰菩型，成：竺唑主菩型，( 2 - 1 )p l 。i 一，p 2 。i 一， 其中6 = 丽葺酉i 气乒忑弼f 巧磊两显然，a 玩u 卢玩是s e i d e l 整 谱图当且仅当( q ，p ，口，b ，6 ) 是下列d i o p h a n t i n e 方程 ( ( a + 2 ) a + ( p 一2 ) 6 ) 2 8 q a ( a 一6 ) = 铲( 2 - 2 ) 的正整数解 对任意恰有两个主特征值的图g ，有 p ：p ；= 4 p l p 2 2 ( r 沈一i ) 比i 一2 ( n l 1 ) p 2 一( 扎一1 ) ， 其中n z = n 谚对于g = n 玩u p 玩，这个关系变成 ( p ：一1 ) ( 肛；一1 ) = 2 a b ( 2 一a p ) ( 2 - 3 ) 接下来，我们将给出a u 风是s e i d e l 整谱图的刻画证明基于定 理1 3 2 5 硕士学位论文 定理2 1 1 若q 玩u p 甄是s e i d e l 整谱图，则它是如下形式? 【等z 。+ 了m e 名】半) 七+ 。mu 【等珈+ 竺壹萼, k + 一l m 名i l k , m ， 俾一 其中( i ) t ，k ，l ，竹，m ，e ，h n + ，且( m ，礼) = 1 ，( ，e ) = l ； ( i i ) 7 _ = ( ( t l n + t ) 尼+ i m ，m e ) ，且丁l 铀 ( i i i ) ( x o ，y o ) 是( ( 丁l n + t ) 后+ l m ) x 一( m e ) y = 7 - 的一个特解i ( i v ) z z o ，徇是满足下列条件的最小整数， ( k 丁t x o 十m - 丁- 竺e z o ) 1 ，( 了k t 珈+ 学牝1 证明：设p ：n + ，则p ：= 1 + o a ，其中0 = 暑，且( p ，妒) = 1 由( 2 - 1 ) 和 ( 2 3 ) ，得 萨1 + 竿，6 = o a + 华 ( 2 - 2 ) 化为 0 + 2 一6 ) n 一= - - - - - - _ - - - - - - _ 0 o a 一6 ( a - t - p 一2 ) 。 设e 是常数，使( d ( a 一6 ) o = c ( o + 2 ) ，和( 动o a 一6 ( q + 一2 ) = c o 由( d 和( 互) ，得c = 延垒幽2由或( 互) ，得a ( o 一的= 虹旦掣( 移+ 2 ) 所以， 口一b = r ( ( q o ) a + ( 卢一2 ) 6 ) ，0 + 2 = 2 r a ， ( 2 - 5 ) 其中r = ，使( s ，t ) = 1 由( 2 5 ) ，得( 司7 印= ( 2 r 1 ) ( r a ( i 一( a 一6 ) ) ，和r 纰= 丝+ o ，且 2 r 一1 = 孕 0 因为够= ( 2 一) ( r 口n 一 一6 ) ) ，所以r i ( 口一6 ) 设( 互) a b = ，y n ( 习7 = k t ，则( 两化为 p = 字丁a a - k t ( 2 _ 6 ) 6 设( 2 s t ，6 ) = l ，则) 2 s t = i n ，和( _ ) b = l m 其中m ，n ， 显然， ( m ，礼) ：1 由( 2 - 6 ) ，得p = 鲁学设( 厶佗) = h ，则佗= h i ，t = h e ，其中 e ，( e ，) = 1 所以有声= 丢旦字 设( 劭o l a 一胁= 叩( m e ) ， d i o p h a n t i n e 方程 因为( 工m ) = 1 ，所以m e l ( q 8 一k t ) 得p ：7 7 ，其中( 吾) 是以q ，叼为变量的 若( 。，m e ) ：丁，则( s - - ) 至少有一个解当且仅当r ik t 由定理1 3 2 ，得 q ：铷+ 孚z ，叼= 了k t 珈+ 孑a z ， q = 一刀o + z ，叼2 。= 珈十= z ， tt 1 li 其中a x o 一( m e ) y o = 丁由( _ ) 和( _ ) ， 根据( 虿) 和最后的这个关系式，得 口：z m + 竿后，= ( 等珈+ 彳a 彬 因为( s ，) = 1 ，所以h = 1 ，或h = 2 口 定理2 1 2 若q g du # g b 是s e i d e l 整谱图，则定理2 f i 中的参数k , l , m ，佗，h ，e ， 五易r 由该图唯一确定 证明：设t l , 7 i , 七l ，z l ，m l ，佗l ，h l ，e l ， 和t 2 , 吃，1 2 ，m 2 ，礼2 ，h 2 , e 2 , 五确定相 同的s e i d e l 整谱图a 玩u p 凰，则由( 2 4 ) ，得 ( i )z l m l + 芈k l = 2 2 忱+ 警， ( i i ) l l m i = 如m 2 因为r l 口1 0 l = 学+ n l 由和 r 2 a 2 a 2 = 筝+ d 2 ，见( 2 5 )式，所以8 1 = s 2 ，t l = t 2 ( 劢，k i t l ：k 2 t 2 ，( 2 s l t l , b 1 ) = z 1 ，( 2 s 2 一如，6 2 ) = z 2 ，得七l5 ，z l 。z 2 由( i ) 和( 以) ，得m l ：m 2 ，礼l = 砌又( 礼1 ，t 1 ) = h l ，( 礼2 ，t 2 ) = 勉，所以h l2 庇2 又n = h f ，t = 眈，故 = ，2 ，e l = e 2 注记2 1 若口凰up 玩是s e i d e i 唯一的 因为 整谱 7 ，仇e ) = 丁，所以n = r 2 口 图，则定理2 1 1 中的x o ，y o ，z o ，z 是 硕士学位论文 定理2 1 3 ( e - 纠的正整数通解? 与定理2 j j 中有 。= i m + 竿后， b = l m ， k tm e a = 一z 0 + z ， 下r ：( ：k t 蜘+ ， l m + 譬后 丁 z ) ， z ) 学 证明：由定理2 1 1 ，可得该定理中的6 由( 2 1 ) ，得 卢；一，哇= 点 弘；+ p ；= ( q 一2 ) 口+ ( p 一2 ) b + 2 又p ；= 2 r a a 一2 n + l ，所以5 = 4 r a a 一2 ( a b ) 一( a o l + 6 p ) 因为a b = ，y r = k t r = k s ，r a a = r k t + r m e 7 7 = 七s + 旦h 翌，= ，? 7 ，所以占= k i n + ( i n + 亡) 警 又叼= 譬蜘+ 1 m + ，：n - 笙t k 2 ，所以6 = k i n + ( 等珈+ 学2 ) 毕口 2 2 几类特殊情况 本节介绍几类特殊情况下口玩up 中的s e i d e l 整谱图 定理2 2 1 若理圪u 是s e i d e l 整谱图，且p i = 1 + a b ，则。虬u p 风是下 列形式j 舌m 尬。一2u ( s t ) n k m - 2 其中m ，礼n + ，体 m ，s 3 ，t b 时，参数q ，p ，a ，b 唯一确定图a k ouz k b 下面说明参数仇，礼，8 ，t 和p ：= 1 + 口6 的s e i d e l 整谱图a 玩u z k b 之间 存在一一对应的关系 定理2 2 2 若a 玩u , o k 6 是s e i d e l 整谱图，且p ；= 1 + a b ，则定理2 1 1 中的 参数m ，几，8 ，t 可由该图唯一确定 证明：设m l ，他1 ，s l t l 和m 2 ，n a ，8 2 ，t 2 确定相同的s e i d e l 整谱图。玩u 凰， 且p ：= 1 + a b ，则由注记2 2 和( 2 7 ) 得： ( i ) t i m l = t 2 m 2 ， ( i i ) ( 8 1 一h ) n l = ( 8 2 一t 2 ) r 沈， ( i i i ) 8 1 n l 一2 = 8 2 7 2 2 2 ， ( i v ) 8 1 m l 一2 = s 2 m 2 2 由( i ) 和( 锄) ，得鲁= 鲁因为( ，s 1 ) = 1 ，( t 2 ，s 2 ) = l ，有t x = t 2 ，8 1 = 8 2 所以，由( ) 和( 蛾得m l = m 2 ，礼l = n 2 口 定理2 2 3 阶不超过1 0 0 的，且p ：= 1 + 0 6 的s e i d e l 整谱图q uz k b 只 奄8 8 个j 9 硕士学位论文 有 证明：若0 1 耽up 是s e i d e l 整谱图，且瞄= 1 + a b ，o 1 0 0 由( 2 7 ) ， 计算结果如下： ( 8 n 2 ) t i n + ( s m 2 ) ( s 一) n 1 0 0 s - - - - - 3 ，t - - - - 1 ，m = l ，讫= 2 ，3 ，2 0 ；s = 4 ，t = l ，m = 2 ，n - - - - 3 ，4 ； s = 3 ，t = l ，m = 2 ，n = 3 ，4 ，7 ；s = 3 ，t = l ，m = 3 ，n = 4 ； s = 3 ，t = 2 ，m - - - - 1 ，扎= 2 ，3 ，1 4 ； s = 3 ，t = 2 ，m - 3 ，n - - - - 4 ； s = 3 ，t = 2 ，m = 2 ，n - - 3 ，4 ，5 ，6 ；s = 4 ，t = 3 ，m - - - - - 2 ，n - - - - 3 ； s - - 4 ，t = l ，m = l ，佗= 2 ，3 ，1 0 ； s = 6 ，t = 5 ，m = l ，n - - - - 2 ，3 ； s = 4 ，t = 3 ，m = 2 ，珏= 2 ，3 ，7 ；s = 7 ，t = l ，m = l ，n - - - - 2 ； s = 5 ，t = l ，m - - - - 1 ，扎= 2 ，3 ，6 ； s = 7 ，t = 2 ，m - - - - 1 ，n - - - - - 2 ； s = 5 ，t = 2 ，m = l ，n - - 2 ，3 ，4 ，5 ；s = 7 ，t = 3 ，m = l ，n - - - - 2 ； s - - - - - 5 ，t - - - - 3 ，m = l ，n = 2 ，3 ，4 ，5 ； s = 7 ，t = 4 ，m = l ，n - - - - 2 ； s = 5 ，t = 4 ，m - - - - - 1 ，n = 2 ，3 ，4 ；s = 7 ，t = 5 ，m = l ，n = 2 ； s = 6 ，t = l ，m = l ，n = 2 ，3 ； s = 7 ，t = 6 ，m = l ，n - - - - 2 ； s = 8 ，t = l ，m - - - - - 1 ，n = 2 故满足条件的正整数解只有8 8 个口 定理2 2 。4 若q 心u 虬是s e i d e l 整谱图，且弘；= l + 8 ，则它是如下形式 之一： 其中p ，m n + ，且p 2 甄沙2 ) mu p ， ( 2 一l o ) 几类s e i d e l 整谱图 或 其中卢，m ，且p 0 2 k c 3 z _ 2 ) mup ， z - 1 1 ) 证明：由( 2 5 ) ，得r q = 鲁因为r = ； ；，所以o l = 1 ，s = 3 ，t = 2 和 a = 2 ，8 = 3 ，t = 4 当o l = l 时，由( 劢，得2 s t = i n = 4 又亡= h e = 2 ，分情况讨论如下： 情形1 ：h = 1 ，e = 2 ，1 = 1 ，n = 4 因为n = h f ，所以f = 4 又b = i m = m ，卢= 7 7 厂= 4 叩，o l a = a = k t + r i m e ，口= 6 + k t r , 所以k = ( 譬一1 ) m ，a = m 一2 m 也即( 2 一l o ) 同理，可知 情形2 ：h = 1 ，e = 2 ，l - 4 ，n = 1 得k ( 6 0 一8 ) mu z k , m ，也即( 2 - l o ) 情形3 ：h = 1 ，e = 2 ，i = 2 ，几= 2 得甄卵一4 ) mup 鲍也即( 2 1 0 ) 情形4 ：h = 2 ，e = 1 ，1 = 1 ，n = 4 口耽uz k b 具有形式( 2 1 0 ) 情形5 ：h = 2 ，e = l ，k2 ，扎= 2 得k ( 3 z - 4 】。u 侈恐m ，也即( 2 - 1 0 ) 情形6 ：h = 2 ，e = 1 ，1 = 4 ，n = 1 ，= 凳= 互1 ，与i 矛盾 当q = 2 时，由) ，得2 s t = i n = 2 又t = h e = 4 ，分情况讨论如下： 情形1 ：h = 1 ，e = 4 ，l = 1 ，扎= 2 因为他= h y ，所以，= 2 又b = l m = m ，p = 7 7 ，= 2 7 1 ，o l a = 2 a = 眈+ 刀仇e ，a = b + k s ，所以k = 一1 ) m ，a = 2 ( z 1 ) m + z m = 3 z m 一2 m 也 即( 2 1 1 ) 同理，可知 情形2 ：h = 2 ，e = 2 ，k1 ，他= 2 得2 k ( 3 p 一2 ) mu ，也即( z - i x ) 1 1 硕士学位论文 情形3 ：h = 4 ，e = 1 ，l = 1 ，佗= 2 ，= ，与，矛盾 情形4 ：h = 1 ，e = 4 ，i = 2 ，竹= 1 得2 k 一4 卸u p 如m ，也即( 2 1 1 ) 情形5 ：h = 2 ，e = 2 ，l = 2 ，礼= 1 ，= 互1 ，与i 矛盾 情形6 ：h = 4 ，e = 1 ，k2 ，礼= 1 i = 互1 ，与i n 矛盾口 定理2 2 5 阶不超过1 0 0 的，且p ：= 1 十。的s e i d e l 整谱图q k uz z b 只有 1 4 2 个 证明：由( 2 一l o ) ，知( ；卢一2 ) m + z m 1 0 0 ，n + ，且 2 ，满足条件的 正整数解有1 0 9 个计算结果如下： z = 3 ，m = 1 ，2 ，1 8 ；3 = 6 ，m = 1 ，2 ，7 ； f l = 4 ，m = 1 ，2 ，1 2 ； z = 7 ，m = 1 ，2 ，6 ； z = 5 ，m = 1 ，2 ，9 ；p = 8 ，m = 1 ，2 ，5 ； 当p - - - - - 9 ，1 0 时，m = l ，2 ，3 ，4 ； 当声= 1 5 ，2 0 时，m = 1 ，2 ； 当p = 1 1 ，1 4 时，m = l ，2 ，3 ；当= 2 1 ，4 0 时，m = 1 由( 2 一1 1 ) ，知2 ( 3 d 一2 ) m + z m 1 0 0 ，p ，满足条件的正整数解有3 3 个计算结果如下： f l - - - 2 ，m = 1 ，2 ，1 0 ；3 = 4 ，m = l ，2 ，3 ，4 ； z = 3 ，m = 1 ，2 ，5 ；p = 5 ，m = l ，2 ，3 ； 当p = 6 ，7 时，m - - - - - - - 1 ，2 ；当p = 8 ，1 4 时，m = 1 所以共有1 4 2 个口 定理2 2 6g 是n 阶图，则2 弘l + 以礼一1 ，等号成立当且仅当g 是正则 图 几类s e i d e l 謦谱图 证明：设z = - - - 去( 1 ，1 ，1 ) t 则 n 一1 = z t ( j i ) z = z t ( c a + a + 1 z = 2 z ? a z + z t a 4 z 2 删i t l a ；x i x t a x + f f y | l m a ：x l y t a + yf f x h = if f y “= l 。 = 2 # 1 + 瞄 等式成立当且仅当z 是a ，”的特征向量，即g 是正则图口 定理2 2 7 若口心u p 是s e i d e l 整谱图，则 ( i ) p ： b a + 1 ， ( i i ) p 滓b a + 2 当且仅当q 玩u p 玩= k b + lu 凰 证明：若q u 是s e i d e l 整谱图，则2 p l + 店= 2 ( a 一1 ) + 城 o l a + p 6 a + b ，即p ：b a + 2 若a 虬u 是s e i d e l 整潜图，且p ；= b a + 2 ，则a = 1 ，p = 1 因 为”( - ) = - a + ( g ) ，即一a + ( 致u 玩) = a + ( k ou k b ) = a + ( 玩，6 ) ，直接计算 d e t ( a i 一”) 可知玩，b 的s e i d e l 特征值为一1 和a + b 一1 ，其重数分别为 a + b 一1 和1 那么玩u 凰的s e i d e l 特征值为l a b 和1 ，其重数分别为 1 和o + b 一1 所以瞄= 1 所以a = b + 1 ，此时店= 1 口 定理2 2 8 瞄= 1 + a 士b 的s e i d e l 整谱图q u p ，有如下形式之一? 或 2 k s b u 3 k b ， 2 k 3 b u k b ( 2 1 2 ) ( 2 - 1 3 ) 硕士学位论文 - - l l - i _ _ - 一i _ _ _ _ _ i l _ - _ _ l _ _ _ _ _ - - - _ _ - - - i - i - _ - - _ l - - _ _ - - _ - l - _ _ - l l _ _ i _ _ _ _ _ _ 一 证明：由( 2 - 3 ) 和p ：= 1 + n 士6 ，得( 1 + 口士6 1 ) ( p ；一1 ) = 2 a b ( 2 一q p ) 由( 2 1 ) ，得p i + ；= q 口+ p 6 2 a 一2 b + 2 。所以，当弘；= 1 + 8 + b 时，有 ( ，) 肛；一l = 呈型竖斧= ( a 一3 ) 。+ ( 卢一3 ) 6 当卢；= 1 + a b 时，有 ( f f ) 店- 1 = 2 a b ( i 2 - 习q 一- 3 ) = ( o z - 3 ) 。+ 一1 ) 6 ( i ) 和( i i ) 可变成如下以a 为变量的方程： ( ，7 ) ( 口一3 ) a 2 + ( 3 a + 3 p l o ) a b + ( 一3 ) b 2 = 0 ， ( i i ) ( o l 一3 ) 口2 + ( o l + 3 p 一2 ) a b 一( p 一1 ) b 2 = 0 又由( 2 - 5 ) ，得2 r n n = a = l = b + 2 a b ，所以p b ，所以p 0 ，2 r 是整数由( a - ) ，得2 卵= ( 2 r 一1 ) ( n q 一半) ， 所以r j ( o 一2 6 + 1 ) 情况l ：n 一2 b + 1 0 ，即p 1 = a l 2 b 一2 = t 2 令( 勾口一2 b + 1 = 7 r 和( 5 - ) ，y = k t 那么( 吾) 变成( 动2 p = 2 s 6 - m 兰t 丁a o t - k t 情形1 ：8 为奇数，t 为偶数，用s 一2 s 一1 ，t 一2 表示令( 2 ( 2 s 1 ) 一 2 t ，2 t ) = 2 1 ，且c ，d ，有( 1 1 ) 2 ( 2 s 一1 ) 一2 t = 2 1 c 和2 t = 2 1 d ，其中( c ，d ) = 1 那么卢= e 2 6 a 。- 广2 t k 设( c ，2 b ) = e ，且，9 ，有c = e y 和( 1 2 ) 2 b = e g ，其中 ( 只夕) = 1 那么p = 吾丁a o , - 2 t k 因为( c ，d ) = 1 ，c = e f ，( ，9 ) = 1 ，所以( ，d ) = 1 那么9 d i ( o j o l 一2 t k ) 令( 1 3 ) ( 1 0 t 一2 t k = 9 d r l ，得( 1 4 ) p = ，7 7 可知( 1 3 ) 是以 o t 和7 7 为变量的丢番图方程若( 口，9 a ) = 丁，则( 1 3 ) 至少有一个解当且仅当 1 i2 t k 由定理1 3 2 ，得 2 k to d2 k td 乜。f z o + 等名，7 7 。- c y + 7 名，7 -7 其中。铷一9 d y o = r 由 ) ，( 1 1 ) ，( 1 2 ) 和( 1 4 ) ，得口= ( 1 c + ) 七十e 9 1 和 p = ( 擎珈+ 拿2 ) ，也即( 3 6 ) 硕士学位论文 情形2 ：s 为奇数，t 为奇数，用s 一2 s 一1 ，亡一2 t 一1 表示。令 ( 2 ( 2 s 1 ) 一( 2 t 1 ) ，b ) = 2 1 一l ，且m ，他n + ，有( 2 1 ) 2 ( 2 s 1 ) 一( 2 t 1 ) = ( 2 1 1 ) ( 2 n 一1 ) 和( 2 2 ) b = ( 2 1 一1 ) m ，其中( m ，( 2 n 一1 ) ) = 1 因为( 2 ( 2 s 一1 ) 一 ( 2 t 一1 ) ，2 t 一1 ) = 1 ，由( 2 1 ) ，得( 2 扎一1 ，2 t 一1 ) = 1 ，和( 2 1 1 ，2 t 一1 ) = 1 ，由$ ) ，有 3 = 百2 n - 1 - a c , - 2 ( t 2 j t - o k 又( 2 m ( 2 t 一1 ) ，2 n 一1 ) = 1 ，所以2 m ( 2 t - t ) l ( o ，n 一( 2 t - 1 ) ) 故令( 2 3 ) 口a 一( 2 t 一1 ) k = 2 n m ( 2 t 1 ) ，得( 2 4 ) 卢= ( 2 n 1 ) n 解以o l 和刁为 变量的丢番图方程( 2 3 ) ，得 ( 2 t 1 ) 是2 m ( 2 t 1 )( 2 t 一1 ) k a a = 二o z o + 二_ 一z ， 露= 二二y o + - - z ， 其中( a ，2 m ( 2 t 1 ) ) = 7 - ，使a x o 一2 m ( 2 t 一1 ) y o = l 和7 - l ( 2 t 一1 即( 3 - 7 ) 情形3 ：s 为偶数，t 为奇数，用s 一2 s ，t 一2 t 一1 表示令( 4 s 一( 2 一 1 ) ，b ) = 2 1 一l ，且m ，住n ，有( 3 1 ) 4 s 一( 2 t 一1 ) = ( 2 1 1 ) ( 2 n 一1 ) 和( 3 2 ) b = ( 2 1 1 ) m ，其中( m ，( 2 n 一1 ) ) = 1 因为( 4 s 一( 2 t 一1 ) ，2 t 一1 ) = 1 ，由( 3 1 ) ， 得( 2 礼一1 ，2 t 一1 ) = 1 ，和( 2 l l ，2 t 一1 ) = 1 由( 吞) ，有卢= 2 n 2 。- - _ _ _ _ i f ”- 矿( 2 t - i ) k 又 ( 2 m ( 2 t 一1 ) ，2 n 一1 ) = 1 ，所以2 m ( 2 t 一1 ) l