（运筹学与控制论专业论文）恰有两个主特征值的双圈图.pdf

摘要 设g = ( v e ) 是简单连通图，其中v = t ，。，忱， n 为项点集合，e 为边 集合。g 的邻接矩阵a = ( 毗，) 。n ，其中啦，为连接点1 3 i ，”f 的边的条数。a ( c ) 的 特征值和特征向量分别称为图g 的特征值和特征向量。图g 的一个特征值称为主 特征值，如果g 有一个相应于该特征值的各分量之和不为零的特征向量。图g 的 最大特征值( 谱根) 总是它的主特征值。图的主特征值在图谱理论及其应用中起着 十分重要的作用。 已知图g 恰有一个主特征值当且仅当它是正则图。在【1 1 】中，h o u 和t i a n 刻 画了恰有两个主特征值的单圈图，本文刻画了所有恰具两个主特征值的双圈图。 关键词：图谱主特征值双圈图度线性图 硕士学位论文 m a s t e r st h e s i s a b s t r a c t l e tgb eac o n n e c t e ds i m p l eg r a p hw i t hv e r t e xs e tv = u l ，也，) a n d e d g es e te a = ( a o ) n ni sc a r e dt h ea d j a c e n c ym a t r i xo fg ，i nw h i c ha oi st h e n u m b e ro fe d g e s j o i n i n g 忱a n d 吻t h ee i g e n v a l u e sa n di t sc o r r e s p o n d e de i g e n v e c t o r s o fa ( g ) i st h ee i g e n v a l u e sa n de i g e n v e c t o r so fg r a p hg a ne i g e n v a l u eo fag r a p hg i sc a l l e dam a i ne i g e n v a l u ei fi th a sa ne i g e n v e c t o rt h es u mo fw h o s ee n t r i e si sn o t e q u a lt oz e r o t h el a r g e s te i g e n v a l u eo fag r a p hgi sa l w a y si t sm a i ne i g e n v a l u e t h e m a i ne i g e n v a l u e so fag r a p hg p l a ya ni m p o r t a n tr o l eo ns p e c t r u mo fag r a p ha n di t s a p p l i c a t i o n i ti sw e l lk n o w nt h a tag r a p hh a se x a c t l yo n em a i ne i g e n v a l u ei fa n do n l yi fi t i s r e g u l a r h o ua n dt i a n 【11 】g i v et h ea l lc o n n e c t e du n i c y c l i cg r a p h sw i t he x a c t l yt w o m a i ne i g e n v a l u e s i nt h i sw o r k ，a l lc o n n e c t e db i c y c l i cg r a p h sw i t he x a c t l yt w om a i n e i g e n v a l u e sa r ed e t e r m i n e d k e yw o r d s ：s p e c t r ao fag r a p h m a i ne i g e n v a l u e s b i c y c l i cg r a p h s 2 - w a l k l i n e a rg r a p h s 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 朱备风 魄如f 岁月弓j 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者豁耘凡 帆扣。 年妨巾 糊叛切 日期：如圻年f 月弓f 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程”中的 规定享受相关权益。回童途塞埕窒蜃遗卮；旦兰生；旦二生；旦三生蕴查! 作者签名：味者风 吼加r 月翻日 导师签名：if i 够量 日期：如口1 年f 月孑日 硕士学位论文 m a s t e r st h e s i s 1 1 符号说明 i y ( g ) i i e ( g ) l g t ( n ) s ( x ) 6 ( g ) v l ( g ) 1引言 图g 的阶数 图g 中的边数 阶数为r 的圈 路或圈r 的长度 图g 中与定点z 相邻的所有点的度和 图g 的最小度 图g 的所有悬挂点组成的点集合 本文没有说明的术语和符号，请参看文献【1 】。 l 2 研究背景及现状 以图的谱来刻划图的结构性质是图的谱理论中重要的研究问题之一。一方面图 谱在量子化学、信息科学等学科中均有一系列的重要应用。另一方面图谱理论发展 的同时也促进和丰富了图论和组合数学本身的研究，谱技巧已经成为图论和组合数 学研究中一个重要的工具。本文首先介绍国内外在这方面具有代表性的发展状况。 设g = ( ke ) 为简单图，其中y 为顶点集合，e 为边集合。设v = v l ，忱，) ，定义g 的邻接矩阵a = ( ) n x n 如下： ， i 1 ，仇e l0 ，仇e 称g 的邻接矩阵a = a ( g ) 的特征值a l ，入2 ，a n 为g 的特征值。图g 的一个特 征值称为主特征值，如果g 有一个相应于该特征值的各分量之和不为零的特征向 量。记m ( a ) 为g 的主特征值的个数。对g 的主特征值进行适当标号，使它的前 m ( a ) 个特征值为主特征值。 硕士学位论文 m a s t e r st h e $ i s 图g 恰有一个主特征值当且仅当它是正则图。c v e t k o v i 6 4 】提出了图谱理论中 的一个未解决的公开问题，即如何刻画恰有k ( k 2 ) 个主特征值的图，h u g o s 9 】 给出了恰有两个主特征值的图的一个充要条件。最近，h o u 和t i a n 1 l 】得出恰有 两个主特征值的单圈连通图为钟。其中钟为由g 的每个点都添加七 0 条悬挂 边所得图。 2 硕士学位论文 m a s t e r st h e s i s 2概述 2 1 关于度线性图的已知结论 图g 中，以u 为起点长为克的途径的条数记为比( 口) 。显然，d o ( v ) = 1 ，d l ( u ) = d ( t ，) ，其中d ( ) 为图g 中u 点的度，并且 以+ 1 ( u ) = d k ( 仳) ，v 七0 t l ( ) n ( v 1 为g 中v 的所有邻点组成的集合 图g 是( n ，6 ) 一度线性图，如果存在唯一确定的有理数n ，b 使得 d 2 ( v ) = a d ( v ) + b( 1 ) 对所有的u v ( c 1 都成立。 由以上的定义可知，( n ，6 ) 一度线性图一定为非正则图，因为若图为r j 下则图， 则d 2 ( v ) = r d ( v ) 十0 且d 2 ( v ) = o d ( v ) + r 2 。 如果b = 0 ，则由文献【5 】知( a ，6 ) 一度线性图为a 一哈密顿非正则图，而且哈密 顿图已经在文献 2 ，5 ，8 中被研究。 在文献 9 】中，h a g o s 证得图g 恰含有两个主特征值当且仅当图g 是( 口：6 ) 一 度线性的。更确切的说，如果图g 是( a ，6 ) 一度线性连通图，则g 的两个主特征值 a 1 ，a 2 满足a 1 2 = 睦娅2 ，即a 1 + a 2 = 凸，a l a 2 = 一6 因此，要想找到所有的恰有 两个主特征值的图，只须找到所有的度线性图。 由文献【1 1 1 可知，对所有的( a ，6 ) 一度线性图，因为 一a 1 ) 一入：) 为整系数 多项式，则a 和b 定为整数。同时，h o u 和t i a n 得出以下结论。 引理2 1 ( 【1 1 】) 若g 为( a ，6 ) 一度线性图，则a 和b 定为整数。更确切的 说，如果g 是连通图，则a 0 。 由( 1 ) 我们有， 引理2 2 若g 为( a ，6 ) 度线性图，u ，u 为g 中度不同的两个顶点，若记 s ( z ) 为g 中与顶点z 相邻的所有点的度和，则 n = 器瑞，6 = 1 d ( u ) s 阿( v ) - d ( v ) s ( u ) 。( 2 ) 3 当n 2 时，在文献【8 】中定义树瓦为一个顶点u 的度为吐2 一a + 1 ，所有与 u 相邻的顶点的度为a ，其余都是悬挂点的树。星图硒n 为共有7 , + 1 个顶点，且 中心点与n 个悬挂点相连的的树；双星图& + 1 n + 。为共有2 n + 2 个顶点，其中中 心点乱，u 相邻i 并且让，口分别与n 个悬挂点相邻的树。则易验证得乃为( a ，0 ) 一度 线性图，k l ，n ( n 2 ) 为( 0 ，n ) 一度线性图，& “n + 为( 1 ，n ) 一度线性图 引理2 3 ( 1 1 1 ) 设g 为( 咄6 ) 度线性连通图，若g 中存在一点仳恰与 n + b l 0 个悬挂点相连，则当a 2 时g 竺咒，且当a = 1 时g 竺踮1 1 。 为方便陈述本文的结论，我们介绍一些图论的符号和术语。其他未定义的符 号参阅b o n d y 和m u r t y 所著文献f 1 】。若x 为一个圈或一条路，记为对x 指 定一个方向后所得的有向圈或有向路。若乱v ( x ) ，则记“妻，u x 分别为义上点 “的后继点与前继点。若札， v ( x ) ，我们记让义u 为x 中子路趾u 专口；u 。若 u = 口，记u x 。 ：= 让) 在上述子路中，若方向与指定方向相反，则记为 x u 。为 方便起见，令x 【让， 】：= u 义u ，x 【u ， ) ：= x 陋，u 一 ) ，即可以把它们看做是路，也 可以看作是点集合。若x 为图g 中的一个圈或一条路，则x 的长度即为x 的边 数，记为z ( x ) 。定义点集合v l ( g ) 为【 ：v y ( g ) ，d ( u ) = 1 ) 2 2 本文解决的主要问题 称g 为双圈图，如果g 为简单连通图并且i e ( g ) l = i y ( g ) l + 1 。本文主要刻 画了所有的恰含两个主特征值的双圈图，即确定度线性双圈图。本文结构如下：在 第二节中，我们重述( n ，6 ) 一度线性图的定义并且列出关于( a ，6 ) 一度线性图的已知结 论；第三节，刻画所有的( a ，6 ) 一度线性图( 即恰有两个主特征值的双圈图) 。 4 3度线性双圈图 在这一节中，我们将刻划所有的( a ，6 ) 一度线性连通双圈图。 3 1 所有最小度至少为2 的( a ，6 ) 度线性连通双圈图 我们先来看关于( a ，6 ) 一度线性连通双圈图的一些性质。 引理3 1 设g 为( 口，6 ) 一度线性双圈图，r = ：t i x 2 既为g 中长至少为2 的路或圈，满足d ( z 1 ) = d ( 觑) 3 且d ( z 2 ) = = d ( x t 1 ) ：2 则 ( i ) e ( r ) 3 ，且 ( i i ) 若t ( r ) = 3 ，则g 中不存在路q = y ，y 2 y 3 满足d ( y a ) = d ( y a ) = d ( x 1 ) 且 d ( y 2 ) = 2 。 证明：( i ) 由反证法，假设e ( r ) 4 。则d ( x 2 ) = d ( x 3 ) = d ( 拙) = 2 。在 ( 1 ) 式中分别令u = z 2 ，石3 ，则有s ( x 2 ) = 2 a + 6 = s ( x 3 ) = 4 ，即可得 d ( x ) = s ( x 2 ) 一d ( x 3 ) = 2 ，矛盾。因此，( i ) 成立。 ( i i ) 由反证法，假设e ( a ) = 3 并且在g 中存在路q = y l y 2 y a 使得d ( y 1 ) = d ( y a ) = d ( x 1 ) 且d ( y 2 ) = 2 ，在( 1 ) 式中分别令u = z 2 ，y 2 ，则s ( x 2 ) = 2 a + b = s ( 可2 ) = d ( y 1 ) + d ( y 3 ) = 2 d ( z 1 ) ，即可得d ( x 3 ) = s ( x 2 ) 一d ( x a ) = d ( x 1 ) 3 ，矛 盾。因此，( i i ) 成立。 定理3 2以下图形( 见图1 ) 即为最小度至少为2 的所有的( a ，6 ) 一度线性连 通双圈图。 冈网删 q g 5g 6g 7 图1 g l ，g 2 ，g 3 ，g 4 ，g 5 ，g 6 ，g 7 证明：设g 为最小度至少为2 的( n ，6 ) 一度线性连通双圈图，则6 ( g ) 2 且 e ( c ) i = i v ( g ) i + 1 。由握手引理可知。y ( g ) d ( ，u ) = 2 ( 1 y ( g ) l + 1 ) ，因此 i d ( t ，) 一2 l = 2 ( 3 ) t y ( g ) 5 硕士学位论文 m a s t e r st h e s i s 设q 和岛为g 中两个不同圈。我们考虑以下两种情形。 情形1 i v ( c , ) ny ( c 2 ) i 1 。 因为图g 连通，则存在连接圈g ，c 2 的路p = ”1 v k ，使得v ( c 1 ) n v ( y ) = u 1 ) 且y ( c 2 ) n v ( p ) = 昧) 。则由( 3 ) 知v ( a ) = y ( a ) u v ( c 2 ) u v ( p ) ，d ( u 1 ) = d ( v k ) 3 且d ( v ) = 2 ，h ( v ( c ) 1 ) ) 仇) 。在引理3 1 ( i ) 中， 分别令r ：= c l ，伤和p ，可得i v ( c 1 ) i = i y ( q ) i = 3 且k 4 。若k = 3 ，则 ( r ，q ) ：= ( q ，p ) 与引理3 1 ( i i ) 相矛盾。所以七( 1 ，2 ，4 ) ，即g 笺g 2 ，0 4 或 g 6 。直接验证可知g 2 为( 1 ，4 ) 一度线性连通双圈图，g 4 为( 2 ，1 ) 。度线性连通双圈 图，g 6 为( 1 ，3 ) 度线性连通双圈图。 情形2 i v ( g ) n y ( 岛) i 2 。 选取z ，y y ( c 1 ) ny ( 岛) 使得 ( a ) q 陋，y 1 为圈q 的子路，且 ( b ) 在条件( a ) 下，i q 【z ，j ! i 达到最大值。 若。= y ，则e ( c 1 ) ne ( 岛) = d ，即e v e v ( o ) n v ( q ) f d ( ) 一2 2 i v ( c , ) n y ( g ) i 4 ，与( 3 ) 矛盾。因此，z y 。由( a ) ，不失一般性，我们可假 设c t x ，y 1 = q k y l ，结合( z ，y ) 的选取我们可知z 云。，正云。和z 去分别为点z 在图g 中的不同邻点，则d ( z ) 3 。同理可得，a ( v ) 3 。由( 3 ) 可知 v ( a ) = y ( c 1 ) uy ( q ) ，矗( z ) = d ( u ) = 3 且a ( v ) = 2 ，坳v ( c ) z ，y 。令 p 1 ：= d 陋，乩p 2 ：= d - ky 】，b ：= 魂k 计，则尸l ，r ，b 为连接z ，y 的内部点 不交的三条不同路，并满足e ( a ) ：e ( i 1 ) ue ( 忍) ue ( b ) 。由对称性，我们可假 设z ( p 1 ) ( p 2 ) s ( b ) 。因为p l 忍，可知( 恳) l 。在引理3 1 中，分别令 r ：= p 3 ，q ：= 只，可知( p 3 ) 3 且 ( p 3 ) = 3 兮z ( 只) 2 ，v i = 1 ，2 结合( p 1 ) 1 和( 岛) 1 可知( z ( r ) ，g ( 尼) ，( b ) ) = ( 1 ，2 ，2 ) ，( 2 ，2 ，2 ) ，( 1 ，3 ，3 ) 或 ( 3 ，3 ，3 ) ，因此g 垡g l ，g 3 ，g 5 或g 7 。直接验证可知，g 1 为( 1 ，4 ) 一度线性连通双 圈图，g 3 为( 0 ，6 ) 一度线性连通双圈图，岛为( 2 ，1 ) 一度线性连通双圈图，岛( 1 ，3 ) 度 线性连通双圈图。定理3 2 得证。 6 3 2 所有最小度为1 的( a ，6 ) 一度线性连通双圈图 以下，我们将刻划所有的最小度为1 的( n ，6 ) 一度线性连通双圈图。为方便起 见，我们定义 9 。6 ：= g ：g 为( o ，6 ) 一度线性连通双圈图且6 ( g ) = 1 ) ， v g 鼠6 ，记g o 为图g 去掉所有的悬挂点后所得的子图。若v v ( c o ) ， 记d g 。( 口) 为图g o 中与点v 相关联的边的条数。对于给定的一个图g 鲵，b ，在本 节中，假设z 为图g 中的一个悬挂点且与z 相连的唯一边记为z ! ，。 引理3 3 设g 瓯，b 且口v ( c o ) 。若d ( u ) d a 。( u ) ，则d ( v ) = a + b 。 证明：假设d ( v ) d c 。( ”) ，则g 中存在一悬挂点札，使得? l v e ( a ) 。对点 札利用式( 1 ) ，可得d 2 ( u ) = a d ( u ) + b 且d ( v ) = d 2 ( u ) 。所以，d ( v ) = a 十b 。 弓l 理3 4 设g 9 。6 。贝 ( i ) 6 ( g o ) 2 ； ( i i ) l e ( c o ) i = i v ( c o ) i4 - 1 证明：( i ) 利用反证法，假设6 ( g o ) 1 。设c 为图g 中的任意圈，则 v ( c ) nv l ( g ) = 毋，因此v ( c ) v ( a o ) 。由于g o 为至少有3 个顶点的连通 图，可知占( g o ) 1 ，因此6 ( g o ) = 1 ，即存在v v ( c o ) 使得如。( u ) = 1 。因为u 茌v l ( o ) ，则d ( 口) 1 ，可推得d ( v ) d a 。( u ) 。由引理3 3 ，可知 d ( t ，) = a + b 2 。因此，恰有d ( v ) 一d a o ( v ) = n + b 1 个悬挂点与点v 相邻。由 引理2 3 可知，g 一定为哈密顿树死或双星图鼽1 十l ，与假设g 至少含有两个 圈相矛盾。 ( i i ) 由于g 为双圈图，则le ( g ) l = l y ( g ) i + 1 ，因此i e ( c o ) l = l e ( g ) i l v l ( c ) i = l v ( a o ) l + 1 。引理3 4 得证。 引理3 5 设g 瓯，b ，则s ( z ) = d ( u ) = a + b 3 且a 2 。 证明：因为z v l ( c ) 且x y e ( c ) ，则y v ( a o ) 且如。( 矽) d ( ! ，) 。由引 理3 3 和引理3 4 可知a + b = d ( 可) d a o ( y ) + 1 c ( g o ) + 1 3 。设z n a 。( ) 7 硕士学位论文 m a s t e r st t t e s i s ，则 s ( z ) = ( d ( z ) 一d o o ( z ) ) + d ( ) + d ( t d ) 删n 。o ( ：) 佃) ( d ( z ) 一d g 。( z ) ) + ( a + b ) + 2 ( d a 。( z ) 一1 ) d ( z ) + ( a + 6 ) 在式( 2 ) 中令( u ，u ) = ( z ，z ) ，可得 凸= 器器型等等幽 上式结合引理2 1 可得a 2 。故引理3 5 得正。 引理3 6 设c 瓯6 ，若r = 札l 让2 缸t 为g o 中长至少为3 的路或圈，且 满足d a o ( u 1 ) = d c 。( u 七) = 3 且d g 。u t ) = 2 ，v 2 i 尼一1 。则 ( i ) d ( u 2 ) = d ( t t 3 ) = = d ( u k 一1 ) 2 ，a + b ，且 ( i i ) 若d ( u 2 ) = 2 ，则l ( r ) = 3 且d ( u a ) = d ( u 2 ) = 2 。 证明：( i ) 由引理3 3 ，可知 d ( u i ) d c 。( ) ，a + 6 = 2 ，a + 6 ，v i = 2 ，3 ，k 一1 ( q 若( i ) 不真，则存在整数i 2 ，3 ，七一2 ) 使得d ( u t ) d ( u 件1 ) 。由( 4 ) ， 不失一般性，可假定d ( u i ) = 2 且d ( u 州) = o + b 。在( 2 ) 中取( t 厶乱) = ( u f + l ，z ) ， 可得 n ：璺( 丝12 二曼( 三! ：! 垡( 竺1 2 ! 竺! 二1 2 二( 竺鱼2 ：亟兰! 1 2 ”d ( u t + 1 ) 一d ( z ) a + b 一1 a + b 一1 上武结合引理3 5 可知d ( 地+ 2 ) = 口( 口+ b 一1 ) 2 ( a + b 一1 ) 2 口+ b + l m a x 【口+ b ，d a 。( u 件2 ) ，与引理3 3 相矛盾。所以，( i ) 得证。 ( i i ) 利用反证法，假设d ( 地) = 2 且e ( r e ) 4 。则由( i ) 可知d ( u 2 ) = d ( u a ) = d ( u 4 ) = 2 。在( 2 ) 中取( u ，u ) = ( u 3 ，z ) ，可得 口=粼d(ua= 垡垒丝l 堕2 笔掣= 4 一( n + 6 ) ， ” ) 一d ( z ) 一l 1 p 乃 与引理3 5 相矛盾。因此，引理3 6 得证。 8 引理3 7 设g 吼，6 且g = u l l j , 2 “七u l 为g 中满足如。( u 1 ) 3 ，c l a 。( 讹) = 2 的圈。则存在整数i l ，2 ，凫 使得d ( u i ) n + b 。 证明：利用反证法，假设d ( u 1 ) = c t ( u 2 ) = = d ( 仳七) = 口+ 6 。在式( 2 ) 中 分别令 = l ，忱，可得。 s ( u 1 ) = a ( n + 6 ) + b = s ( u 2 ) = d ( u 1 ) + d ( u 3 ) + ( d ( 锄) 一2 ) = 3 ( a + b ) 一2 另外，由引理3 4 知占( g o ) 2 ，因此 s ( 札- ) = ( d ( 乱，) 一d g 。( u ) ) + d ( 乱。) + d ( u t ) + d ( 伽) u j e n g o ( t 1 ) t 2 ，“ ( 凸+ b 一如。( u 1 ) ) + ( 凸+ b ) + ( n + b ) + 2 ( d a o ( u 1 ) 一2 ) = 3 ( a + b ) 十d c 。( 让1 ) 一4 3 ( n + b ) 一1 ； 矛盾。则引理3 7 得证。 引理3 8 设g 9 n 6 ，若c = 礼1 乱2 札七他1 为g 中满足3 d a o ( u 1 ) 4 且 d g 。( u 2 ) = d a o ( 札3 ) = = d c 。( 札七) = 2 的圈。则不存在整数j l ，2 ，七) 使得 矗( 1 0 ) = d ( i l j + 1 ) = n + b ，其中孔+ 1 ：= u 1 。 证明：利用反证法，假设存在j 1 ，2 ，七) 使得d ( 哟) = d ( u j + 1 ) = n + 6 。 选取a ，p 1 ，2 ，七) 使得 ( i ) c l 【仳口，邯】2 _ ，f 句+ l ； ( i i ) d ( v ) = 口+ 6 ，( 2 1 u 。，仳卢】； ( i i i ) 在( i ) ，( i i ) 的前提下，f c x u a ，“卢】i 达到最大值。 若口= 理一l ，则c 上每一点的度都为q + 6 ，与引理3 7 相矛盾，因此 p 理1 。结合a ，p 的选取可知d ( 札口一1 ) a + b d ( 札斛- ) 。显然 “口，u p 缸1 ) 咖。由对称性，可假设口l ，则有c l a o ( u 。) = 2 且s ( u 。) = d ( u n 一1 ) + d ( + 1 ) + ( d ( “q ) 一2 ) = d ( 一1 ) + 2 ( o 十b 一1 ) 在( 2 ) 中取( t ，乱) = ( 让a ，z ) ，可得 s ( u q ) 一s ( z )d ( 让n 一1 ) + ( n + b 一2 ) ，d ( 札口一1 ) 一1 口2 丽萧丽2 i i bj 一一1 十i 辅b = 丁 ” d ( u q ) 一d ( z ) o +一1 。 n +一l 由引理2 1 可知，( n + b 一1 ) l ( d ( u n 一1 ) 一1 ) 。结合d ( 孔n 一1 ) d + b 可知 ， d ( t 上q 1 ) 一1 2 ( n + b 一1 ) 之a + 6 + l ， 项士学位论文 m a s t e r st i t e s i s 因此d ( t a 一1 ) a + b + 2 m a x a + b ，d c 。( 让旷1 ) ) ，与引理3 3 矛盾。引理3 8 得 证。 定理3 9 设g 为最小度为l 的度线性连通双圈图，则g 同构于g 8 或g 9 ( 见图2 ) 沙一山吲 图2 g 8a n dg 9 证明：设g 为最小度为1 的的( a ，6 ) 一度线性连通双圈图，设g 0 为g 删除所有 的悬挂点后所得的子图。由引理3 4 可知6 ( g o ) 2 且l e ( g o ) l = l v ( e o ) l + 1 。结 合握手引理可知 i 如。( 可) 一2 1 = d c o ( u ) 一2 1 v ( g 。) l = 2 1 e ( g 。) f - 2 1 v ( e 。) i = 2 ( 5 ) u v ( c o )v e v ( g o ) 设c l ，岛为g o 中两个不同圈。我们考虑以下两种情形。 情形1 i y ( q ) ny ( 岛) l 冬1 因为g o 连通，则存在连接圈a ，岛的路p = u 1 仇使得y ( g ) nv ( p ) = t j l ) 且y ( q ) nv ( p ) = 讥) 。由式( 5 ) 可知v ( c o ) = y ( g ) uy ( 岛) uy ( 尸) ， d g o ( ”) = d a 。( 仇) 3 且d v 。( u ) = 2 ，咖( v ( c , o ) 1 】) d a 。( 扎1 ) = 3 。在式( 2 ) 中令( 。，锃) = 硕士学位论文 m a s t e r st h e s i s ( u l ，o ) ，可得 n ：坠! ) 二墅! ：堡丝生堡! 塾址垫望生终兰! l ! l ! 兰坠：堡幽! ，i = = 一= = 一 ”d ( u 1 ) 一d ( z ) d ( u 1 ) 一l q + b 一1 结合引理3 5 可知d ( t j 2 ) = a ( a + b 1 ) 一1 2 ( a + b 1 ) 一l 之a + b + 1 m & x 口+ 舀，( 忱) ) ，与引理3 3 矛盾。因此， ( 9 ) 式成立。 由式( 7 ) 一( 9 ) 可知，d ( v ) = d a 。( u ) ，v v y ( c 1 ) uy ( q ) 。因此，y = v i 对 某些满足2 i 七一1 的i 成立。在引理3 6 中令r ：= p ，则有 d ( 吨) = = d ( v k 一1 ) = d ( y ) = a + b ( 1 0 ) 在式( 2 ) 中令( 口，让) = ( 抛，z ) ，可得 s ( 啦) 一s ( x ) d ( u 1 ) + d ( u 3 ) 一( a + b ) d ( t 也) 一d ( x ) 2 1 = 5 一( a + 6 ) 结合引理3 5 可知2 5 一( a + b ) 5 3 ，因此a + b = 3 。由式( 7 ) 一( 1 0 ) ，可 知g 竺g s 。直接验证可得，g 8 为( 2 ，1 ) 一度线性连通双圈图。 情形2 1 v ( c ，) ny ( q ) i 2 选取z ，w v ( c i ) nv ( q ) ，使得 ( a ) c tz ，叫】为伤的子路，且 ( b ) 在( a ) 的前提下，i c 。z ，叫】| 达到最大值。 与定理3 2 的证明相类似，可知z 且e ( c o ) = e ( r ) ue ( p 2 ) ue ( 岛) ， 其中只，b ：b 为连接z ，1 3 的三条内部点不交的不同路，为方便起见，我们令 p l ：= u l u 2 趾m ，b = 0 1 忱仇且b = w 1 w 2 ，其中u 1 ：= u 1 ：= w l ：= z 且：= o k ：= w n ：= w 。我们首先证明以下几个命题。 命题1 d ( u 1 ) = d ( ) 证明：由对称性，可假设m 七n ，结合岛b 可知七3 。由引理3 6 可知d ( 仳2 ) = d ( t 一1 ) 且d ( v 2 ) = d ( v k 1 ) 。则 s ( u 1 ) 一s ( u m ) = ( d ( u 1 ) 一3 ) + d ( u 2 ) + d ( 耽) + d ( w 2 ) 一【( d ( 让m ) 一3 ) + d ( u m 一1 ) + d ( v k 一1 ) + d ( 1 一1 ) 】 = d ( u 1 ) + 矗( 地) 一d ( 筐m ) 一d ( 一1 ) ， id ( u 1 ) 一d ( ) ，n 3 2 10 ， n = 2 12 若d ( u 1 ) d ( ) ，则由式( 2 ) 可知 口= 渊“口2 面万丽纠 与引理3 5 相矛盾，则命题1 得证。 以下，我们假设x ：= ： u 2 ，v 2 ，忱) 且d ( v ) = n + 6 ) 。 命题2 假设d ( 廿) = d ( ) = a + b ，则 ( i ) l x l 1 ，且 ( i i ) d ( ”) = 2 ，v v ( u 2 ，忱，她) x 。 证明：( i ) 利用反证法，假设l x i22 ，则u 2 ，v 2 x 。在引理3 6 中分别令 r ：= p 1 ，吃可得 d ( u ) = a + b ，v 口( v ( 尸1 ) uy ( 岛) ) 札l ，让。) 显然p l p 2 ，不失一般性，假设( p 1 ) 2 ，则c ：= ? 2 1 f l u 。p 2 u l 为圈，与引理 3 7 相矛盾。 ( i i ) 不失一般性，可假设t ，= 让2 譬x ，则d ( u 2 ) a + b 。结合d ( u 。) = 口- - 6 可 得m 2 ，因此d g 。( 让2 ) = 2 。由引理3 3 ，可知d ( u 2 ) = d a 。( 札2 ) = 2 。 命题3 d ( 乱1 ) = 3 。 证明：利用反正法，假设d ( 仳1 ) 3 ，则d ( u 1 ) d v 。( 让1 ) 。由命题l 和引理3 3 可知d ( 仳。) = d ( 乱1 ) = a + b d g 。( 仳1 ) = 3 。结合命题2 可知d ( u 2 ) + d ( 忱) 十d ( 此) 口+ b + 4 ，因此s ( u 1 ) = d ( 坳) + d ( v 2 ) + d ( w 2 ) + ( d ( u 1 ) 一3 ) 2 ( a + b ) + 1 。在 ( 2 ) 中取( u ；乱) = ( l t l ，z ) ，可知 。= 粼堕群 2 ， 与引理3 5 相矛盾。 由命题1 和命题3 可知，u 1 ，牡。都不与g 中的悬挂点相连，因此，y ( y ( p 1 ) uy ( 岛) uy ( p 3 ) ) u l ，l t m ) ，即耖y ( r ) 一 u l ，) 。因为d ( ! ，) = a 十b ， 在引理3 6 中令r ：= 只，则有 d ( v ) = a + b ，vt ，y ( p 1 ) 乱l ，) ( 1 1 ) 1 3 在式( 2 ) 中取( 口，u ) = ( 仳2 ，z ) ，则有 s ( u 2 ) 一s ( z ) 归币于习衙2 结合引理3 , 5 可知 蚴地警趔=黜02)1 ab1 d ( 啦) 一 十一 d ( u 3 ) = a ( a + b 1 ) 一1 2 ( a 十b 一1 ) 一1 = ( a + 6 ) + ( n + b 一3 ) n + b ( 1 3 ) 另一方面，由引理3 3 可知d ( u 3 ) m a x 始。( 乱3 ) ，n + b ) = 口+ b 。结合式( 1 2 ) 、 ( 1 3 ) 可知 d ( u 3 ) = a + b = 3 ( 1 4 ) 且a = 2 。由式( 1 4 ) 和命题1 3 可知d ( u 1 ) = d ( ) = a + b ，因此i x l 1 。结 合式( 1 1 ) 可知，x = u 2 ) 。由命题( 2 ) ( i i ) 可知，d ( 砚) = d ( 叫2 ) = 2 。因为 d ( v k ) = d ( 叫。) = d ( u 1 ) = 3 ，可得 m i n 七，n ) 3 在引理3 6 中分别令r ：= p 2 ，e 3 ，可知 d ( v ) = 2 ，v u ( y ( p 2 ) uy ( p 3 ) ) 仳1 ，u m ) ， 且m a x 孽( 岛) ，( p 3 ) ) 3 ，即 m a r x 七，n ) 4 若k = 3 ，贝u 在( 2 ) 中取( ，u ) = ( 抛，z ) ，则 a2s ( v 2 ) 一s ( z ) 6 一( n + b )。 d ( 吨) 一d ( z ) 一一 2 1 一吨 ( 1 5 ) ( 1 7 ) 与a = 2 矛盾，因此七3 。结合式( 1 5 ) 和式( 1 7 ) 可知k = 4 。同理可知 礼= 4 。由式( 1 1 ) 、 ( 1 4 ) 、 ( 1 6 ) 和命题1 - 3 可知g 筌g 9 。容易验证得g 9 为 ( 2 ，1 ) 一度线性连通双圈图。定理3 9 得证。 推论3 1 0g 1 ，g 2 ，g 3 ，g 4 ，g 5 ，g 6 ，g 7 ，g 8 ，g 9 ( 见图1 和图2 ) 为所有的连通 的恰含有两个主特征值的双圈图。 硕士学位论文 m a s t e r st h e s i s 参考文献 f 1 】j a b o n d y , u s rm u r t y , g r a p ht h e o r yw i t ha p p l i c a t i o n s ，m a c m i l l a n ，n e w y o r k ，1 9 7 6 f 2 】2 b b o r o v i d a n i n ，s g r f i n e w a l d ，i g u t r n a n ，m p e t r o v i d ，h a r m o n i cg r a p h sw i t h s m a l ln u m b e ro fc y c l e s ，d i s c r e t em a t h 2 6 5 ( 2 0 0 3 ) 3 1 4 4 【3 】d c v e t k o v i 6 ，p r o w l i n s o n ，s s i m i 6 ，e i g e n s p a z e so fg r a p h s ，c a m b r i d g eu n i v e r s i t y