（基础数学专业论文）五圈及六圈调和图.pdf

湖南师范大学硕士学位论文 中文摘要 设g 是他阶简单图显然，g 恰有一个主特征值当且仅当g 为 正则图而刻划恰有k ( k22 ) 个主特征值是c v e t o k v i d 提出的一个长 期未解决的问题近来a d r e s s 和g u t m a n 从图中路数目的计算，提 出了调和图的概念：一个图g 称为是调和的，如果存在一个数a ，使 a ( v ) d ( v ) = 州( g ) 其中d ( c ) = ( 酬u 1 ) ，d ( ) ) 为g 的度序列从特 征值上来看，一个非正则图g 是a 一调和图当且仅当g 恰以a 和0 为 主特征值具有较少圈的连通的调和图：如调和树，单圈图，双圈 图，三圈图和四圈图都以完全确定 本论文研究并确定了所有的五圈调和图和六圈调和图：( 1 ) ：连 通的五圈调和图恰有6 2 个其中，连通非正则的五圈3 一调和图恰有 5 6 个；连通正则的五圈3 一调和图恰有5 个；连通五圈4 一调和图恰有 1 个( 2 ) ：连通的六圈调和图恰有7 7 个其中，连通非正则的六圈3 一 调和图恰有5 5 个；连通正则的六圈3 _ 调和图恰有1 9 个；连通菲正 则的六圈4 一调和图恰有2 个；连通正则的六圈4 调和图恰有1 个 关键词：调和图；图谱；主特征值；五圈图；六圈图 湖南师范大学硕士学位论文 i i a b s t r a c t l e tgb eas i m p l eg r a p ho fo r d e rn c l e a r l y , gh a se x a c t l yo n em a i n e i g e n v a l u ei fa n d i fgi sr e g u l a r i ti sal o n g - s t a n d i n g1 ) r o b l e mo fd c v e t k o v i dt o c h a r a c t e r i z eg r a p h sw i t he x a c t l yk ( k 2 ) m a i n e i g e n v a l u e s r e c e n t l y , a ，d r e s s a n dg u t m a ng a v ea nc o n c e p to fh a r m o n i cg r a p h s ：t h eg r a p hgi ss a i dt ob e h a r m o n i ci ft h e r ee x i s t sac o n s t a n ta ，s u c ht h a tt h ee q u a l i t ya ( g ) d ( g ) = a d ( g ) h o l d s o n en o n r e g u l a rg r a p hgi s a h a r m o n i ci fo n l yi fgh a se x a c t l ym a i n e i g e n v a l u e saa n dz e r o e a r l i e ra l lh a r m o n i ct r e e sw e r ed e t e r m i n e da n da l l u n i c y c l i c ，a c y c l i c ，b i c y c l i c ，t r i c y c l i ca n dt e t r a c y c l i ch a r m o n i cg r a p h sw e r e c h a r a c t e r i z e ( 1 i nm y p a p e r w eg oas t e pf u r t h e ra n df i n da l lp e n t a c y c l i ca n dh e x a c y c l i c h a r m o n i cg r a p h s ：( 1 ) ：t h e r ea r ee x a c t l y6 2c o n n e c t e dp e n t a e y c l i ch m m o n i c g r a p h s ，w h e r et h e r ea r ee x a c t l y5 6n o n - r e g u l a ra n d5r e g u l a rc o n n e c t e dp e n t a c y c l i c3 - h a r m o n i cg r a p h sa n dt h e r ee x i s te x a c t l y 1 n o n r e g u l a rc o n n e c t e d p e n t a c y c l i c4 - h a r m o n i cg r a p h s ( 2 ) ：t h e r ea r ee x a c t l y7 7 c o n n e c t e dh e x a c y c l i c h a r m o n i cg r a p h s ，w h e r et h e r ea r ee x a c t l y5 5l i o n r e g u l a ra n d1 9r e g u l a rc o n n e c t e dh e x a c y e l i c3 - h a r m o n i cg r a p h sa n dt h e r ee x i s te x a c t l y2n o n r e g u l a ra n d 1 r e g u l a rc o n n e c t e dh e x a c y c l i c4 - h a r m o n i cg r a p h s k e y w o r d s ：h a r m o n i cg r a p h s ；s p e c t r a o f g r a p h s ；m a i ne i g e n v a l u e s ；p e n t a c y c l i c g r a p h s ；h e x a c y c l i cg r a p h s 湖南师范大学硕士学位论文 第一章绪论 代数图论是目前国际上一个非常活跃的图论分支，已经形成相 当成熟的理论详见专著1 0 ，1 l1 ，其中对图的同构不变量特征值的 研究又是十分重要的课题之一详见专著f 8 ，1 11 自从七十年代初， 由d ，m c v e t o k v i 6 3 1 提出主特征值的概念以来，很多图论学者都投 身于这方面的研究它越来越多地与其它数学分支及其它学科相互 交叉，相互影响，使之成为这方面研究的重要发展趋势目前，关 于这方面研究主要表现在如下几个方面： ( 一) 主特征值 七十年代初，d m c v e t o k v i 提出了主特征值的概念 3 ，4 ：g 的 一个特征值a 称为是主特征值，如果g 有一个相应于a 的特征向量 其分量之和不为0 关于这方面的结果以及它在化学之中的应用可 以参考文献 2 5 ，2 6 】和 5 】另外，刻划恰有k ( k 2 ) 个主特征值图是 c v e t o k v i d 提出的一个长期未解决的问题【6 】目前，只有文献 2 8 m 9 】 刻划了恰有两个主特征值的树和单圈图，故在探求图的主特征值的 结构特征上，仍有广阔的研究前景 ( 二) 调和图 近来，a d r e s s 和g u t m a n 从图中路数目的计算，提出了调和图 的概念 1 2 l ： 设是长为k 的路数目，a ：= w k 十1 w k l 一孵，若x 1 0 且。= 0 ，k = 2 ，3 ，成立，则g 称为调和图另一种概念是：图 g 称为是调和图的，如果存在一个数a ，使a ( g ) d ( g ) = a d ( g ) ，其中 d ( c ) = ( d ( v 。) ，d 池) ，d ) ) t 为度序列从特征值上来看，一个非正 则图g 是a 一调和图当且仅当g 恰以 和0 为主特征值，或者说，g 是调和图，如果度序列( d ( v 。) ，d ( v 。) ，d ( ) ) t 是g 的邻接矩阵a 的 特征向量因而确定调和图的个数，结构以及性质是很有意义的 ( 三) 调和图的推广 近来，在调和图的基础上，a d r e s s ，s g r i i n e w a l d 等人提出了半 湖南师范大学硕士学位论文 2 调和图，几乎半调和图，超调和图和低调和图等一系列的概念f 1 4 1 - 目前，已经证明并确定了半调和树；单圈图的半调和图；二圈图的半 调和图以及半调和图的个数是无限的等一系列的结论1 6 ，2 4 1 因此， 在这方面仍有研究的价值 本文受到文献【1 2 9 的启发，运用了其中某些方法，进一步推广 了目前有关调和图的结果( 一一四圈是已有结果) ( 见下表) 我们用c 表示圈数，用r ( c ) 表示c 圈正则图，用n r ( c ) 表示c 圈非正则图 c r ( c )n r ( c ) a 0l o 。 a 1 1 o 。 0n 3 ：a = 2 200 314a = 3 421 8a = 3 55 6a = 3 5 01a = 4 1 95 5a = 3 6 12 = 4 湖南师范大学硕士学位论文 3 第二章基本引理 设g = ( ue ) ，其中l y ( g ) i = 礼，i e ( g ) i = m 如果图g 有p 个连通 分支，则c = m 一扎+ p 称为图g 的圈数若g 是连通图，当p = l ， c = 0 时，称g 是树另外，若一个顶点的度数为，则称为一个k 顶 点；一顶点的数目通常用礼t 表示；顶点z 的度通常用d ( x ) 表示；用 表示一个图的最大度；若树中有一个顶点”，其中”顶点的度数为 入2 一a + i 且其邻点的度数都为 ，其余顶点的度为1 ，则称为g r i i n e w a l d 树，通常用乃表示 g 称为a 调和图【2 3 ，若存在一个常数a 使得等式 a d ( v 1 ) = ：d ( 吩) ( 1 ) v j _ v ( ) 成立，i = 1 ，2 ，3 ，t 这里，( q ) 表示与顶点所相邻的顶点 另外，在 2 3 】中证明了a 是一个非负整数；在g r i i n e w a l d 2 3 中确定 了调和树的结构且个数有无限多个；在 1 】和 2 】中解决了一四圈 调和图的数目及结构：连通非正则的一圈调和图和二圈调和图不存 在；2 调和图只有树正及圈g ；连通非正则的三圈调和图恰有4 个；连通非正则的四圈调和图恰有1 8 个连通非正则的四圈调和图恰 有2 个本文，我们找到了所有的五圈及六圈调和图的数目及结构 为了证明本文定理，我们需要下面的引理： 引理2 1 【1 设g 是连通的卜调和图，则 ( a ) a 是最大特征值且重数为1 ( b ) 若m 0 ，则 1 ( c ) a = 1 当且仅当n = 2 ，m = 1 引理2 2 i t g r i i n e w a l d 树疋是唯一的连通2 一调和图 我们假设a 3 则有： 引理2 3 1 1 ( a ) 在a 一调和图中，每一个l 一顶点必须邻接度为a 的顶点 湖南师范大学硕士学位论文4 ( b ) 若一个k 调和图是非正则的，则它有一个顶点的度大于a 引理2 4 1 1 1 设x 是 一调和图的一个顶点，则d ( x ) t j 洙一a ) n k = 0 ( 3 ) 七 0 引理2 7 1 1 2 设z 是a 一调和图的一个顶点，若d ( z ) 入2 3 a + 4 且n 是z 的邻点则d ( u ) = a 引理2 8 1 1 2 1 对予任意的c 3 ，连通的非正则c 一圈调和图的个数 是有限的 湖南师范大学硕士学位论文 t 5 第三章主要结论 3 1a = 2 c 的调和图 由于2 调和图只有树b 及圈g ，下面总设a 3 称g 中一个顶点”为k n o b ( 柄) ，如果d ( v ) = 2 或它恰有两个邻点 不是悬挂点 定理3 1 设g = ( u e ) 是a 一调和图( a 2 ) ， o ， 1 ， 2 ， 3 ，v 4 是g 中一条路或一个圈( v 0 = 4 时) ，且札v 2 ，u 。都是柄点令p ：= d ( v i ) 一2 ， 贝0d ( v 2 ) = 2 ，d ( v 1 ) = d ( v 3 ) = a ，且d ( v o ) = d ( v 4 ) = a 2 一a 证明：若p 2 0 ，则d ( v 2 ) = a ，这样 d ( v a ) + d ( v 1 ) = a d ( v 2 ) 一p 2 = a 。一a + 2 因为d ( v ，) = a 或2 ，及d ( v 。) = a 或2 ，容易验证，不管何种情况 d ( v 3 ) + d ( v 1 ) a 2 一 + 2 从而p 2 = 0 这样d ( v 1 ) + d ( v 3 ) = 2 3 , ，所以d ( 1 ) = d ( v 3 ) = a ，d ( v o ) = d ( v 4 ) = a 2 一a 】 由定理3 1 可知，在调和非圈图中，至多有三个柄点相继相邻 在 1 l 中，证明了连通调和图中的最大度a 2 c ，及c i 1 ( a 2 2 a + 2 ) 下面的结论刻划等号= 2 c 成立的图 定理3 2 满足= 2 c 的调和图必为 镑掺 隆辫 y ( 。 湖南师范大学硕士学位论文6 证明：由 2 】中引理9 的证明知：2 c ，且等式成立当且仅当 最大度点u 连接g 的每一个独立圈的两条边，这样g 只有一个最大 度点 如果g 只有一个最大度点，则g 的固架图为u ( 见图u ) 由定理 3l 知，每个圈长不超过4 ，若g 的每个长度均为3 ，则g 是g 。若g 的图中有一个圈长为4 由定理3 1 知：最大度点为a 。一a ，从而每个 圈长均为4 故g 为h 。n 图u 定理3 3 设a 一调和图满足2 c = a 2 2 + 2 ，则a 为偶数且g 为 g 证明：若= 2 c ：a 2 2 a + 2 则由定理3 2 知：g 必为g 设g 满足2 c = a 2 2 ) t + 2 若 ( a 一1 ) 设顶点乱满足d ( u ) = a ，b = m a x n l ( ) 情况1 ：若b 之a a 设礼，( ”) = b ，因为v 至少邻接a o 三1 个悬挂点，所以d ( v ) = a 湖南师范大学硕士学位论文 7 设y 1 ，y 2 ，y 是u 的邻域且d ( 姚+ 。) = 1 1si a a 从而 a 2 = a 若d ( y ，) ，d ( y 。) ，中有一个为a ，则 a 2 一a + n = d ( y i ) s a + ( n 1 ) 2 = 1 2 + r a + n 一2 a ) a 2 一a + 2 一n 1 a 2 2 a + 3 1 2 2 a + 2 1 故情况1 不会出现 情况2 ：若b s a 一日一1 记( 钆) 为u 的邻域集，w 。，w t ，w 是“的邻点，且d ( w ；) a 2 ，) k l 因为n 一1 a 一2 ，d ( 铷 ) = k a ，a 一2 一n l ( v ) n l n t ( v ) 三。一1 i = 1 d 。 +n w 口 。僦 + n一2一，( 矗 洲 蚝 +2一+ 则，、 自 1 2 2 且“a ( i i ) 与 相邻的点的度均为a ，且邻接a 一1 一。个悬挂点 ( i i i ) ( a n 一1 ) = 0 ( i v ) a a = 一2 a + 2 由= 0 ，知：钍不邻接度为2 的顶点 若d ( ) = a ，u 一 子情况1 ：若d ( ”) = 入的顶点不邻接2 一度顶点，则d ( ”) = 入的顶 点只邻接a 一度顶点和悬挂点及点钍悬挂点为 一1 一n = b 这样， 一l 一+ = x ( x n ) ，0 邻接n 个k 度顶点) 所以 = 2 一+ 1 ) a + n + i ：! 二坠型， 所以 。一( 。+ 1 1 入+ n + l ：查! 二! 苎兰 2 一( 。+ 1 ) 入+ n + l = 二- 所以 ( n 1 ) 2 一( 舻+ o 一2 ) 入- 4 - ( 0 24 - a 一2 ) = 0 湖南师范大学硕士学位论文 9 因为a 2 ，故 a 2 一( a + 2 ) a + ( a + 2 ) a = 0 而 a 2 一( g + 1 ) a + ( d + 1 ) = a 一1 ， 所以x = a 一1 矛盾 子情况2 ：若”邻接了s 个2 一度顶点，则 + a 1 一a + 2 s + ( a s ) a = a 2 ， 所以 = a 2 一a a ( 一s ) + 1 + n 一2 s = a 2 一( g 一8 + 1 ) a + n 十1 2 s 而= a 2 - 。2 1 + 2 ，所以 ( a 一1 ) a 2 一( n 2 一a s + 一2 ) a + ( a 2 + a 一2 a s 一2 ) = 0 又 ( a 一1 ) a 2 一( a s + 1 ) a + ( a + l 一2 s ) 】= ( n 一1 ) ， 上两式相减可得： ( 一1 ) = ( a 一8 1 ) a + 2 s a + 1 = ( a 一1 ) a s + 2 s 一( n 一1 ) 所以 = a 一高a - lq 一鲁 茎a 一1 矛盾故情况2 不会出现 故当2 c = a 2 2 a + 2 时，必有 = 2 c = a 2 2 a + 2 由定理3 2 知：g 必为g 湖南师范大学硕士学位论文 1 0 3 2五圈调和图 由于2 c a 2 2 a + 2 ，故当c = 5 时，a = 3 或4 ， 当a = 4 时，；( a 2 2 a + 2 ) = 5 此时5 一圈图的4 调和图只有一个 ( 见图g s z ) 定理3 4 连通的五圈调和图共有6 2 个( 见图1 ) 其中，连通非正 则的五圈3 调和图5 6 个；连通正则的五圈3 一调和图5 个；连通的 五圈4 一调和图只有1 个 证明：只须证明3 调和图和5 一圈图只有6 1 个当a = 3 ，c = 5 时，由引理4 可知：6 又由引理3 可知有如下三种情况： 情况l ：a = 3 ，x = 6 ；情况2 ：a = 3 ，x = 5 ；情况3 ：a = 3 ，= 4 情况l ：从引理6 得：n 。一n 。0 ，又由等式( 2 ) 和( 3 ) 可得： 根据( 4 ) 又可分为两种情况：礼e = l 或竹。= 2 情况1 1 ：n 。= 1 时又可分如下四种情况： ( 5 ) 【o ) ：7 1 5 = 0 ，n 4 = 0 ，? 2 3 一? 2 1 = 4 ，m + n 2 = 9 ( b ) ：n 5 = 0 ，n 4 = l ，”3 7 1 1 = 2 ，n l + 礼2 = 1 1 ( c ) ：n 5 = 0 ，n 4 = 2 ，7 3 7 1 1 = 0 ，l 1 + ? 1 2 = 1 3 ( d ) ：n 5 = 1 ，n 4 = 0 ，札3 一n l = 1 ，n l + n 2 = 1 4 如果3 调和图满足上面的条件，则它的顶点满足下列的性质： ( i ) ：6 - 顶点和5 一顶点的邻点必须是3 顶点 ( i i ) ：1 一顶点必须邻接墨顶点 ( i i i ) ：每个邻接6 _ 顶点的3 - 顶点必须邻接1 一顶点和2 一顶点 ( i ”) ：垂顶点邻接的顶点也必须是3 顶点，而其墨顶点必须邻接3 顶点和2 _ 顶点( 札4 = 1 1 讨论( n ) ：由性质( i ) 和( i 扰) 可知：n 3 6 ，n 2 3 ，札1 之6 因此，满 足条件的只有n 6 = 0 ，佻= 0 ，n 4 = 0 ，礼3 = 1 0 ，n 2 = 3 ，n l = 6 但是，每个 湖南师范大学硕士学位论文 1 1 2 一顶点至多邻接两个3 _ 顶点，还剩下四个3 一顶点，矛盾故不存在 图 讨论( b ) ：由( i ) 一( i v ) 可知：n 3 1 0 ，n 225 ，又由札3 n 1 = 2 可 知：n ，8 故有现+ 孔。21 3 与( b ) 的条件矛盾，故不存在图。 讨论( c ) ：由性质( i ) 一( 伽) 可得：n s l o m 2 3 n 。l o 易知：只有 当n 1 = 1 0 礼2 = 3 ，礼3 = 1 0 ，n 4 = 2 ，佻= o n 6 = l 时才成立此时，6 一顶 点要邻接六个3 一顶点，还剩下四个3 一顶点而4 一顶点必须邻按3 一 顶点，所以当m = 2 时，这两个4 顶点必须共剩下的四个3 一顶点 但是，对于连通图，在与6 一顶点连接时必须是连接一个2 一顶点，而 与之相连的必须是3 一顶点，矛盾故不存在图 讨论d ：由性质( i ) 一( i v ) 易推出：只有当n 。= 1 0 ，礼。= 4 ，7 t 3 = 儿，n 。= 0 ，n 。= 1 ，礼6 = l 时才满足条件此时恰有图g ， 情况1 , 2 ：n 6 = 2 ，n 5 = 0 ，n 4 = 0 ，n 3 一礼l = 0 ，n 1 + 礼2 = 1 8 时，易推出 只有n 6 = 2 ，n 5 = 0 ，n 4 = 0 ，n 3 = 1 2 ，n 2 = 6 ，n l = 1 2 时才成立这时恰有 图g 2 ，g 3 ，g 4 情况2 ：由等式( 2 ) 和( 3 ) 可得： 一铂+ 扎3 + 2 n 4 + 3 n 5 = 8 ；一孰l 一2 札2 + 4 钍4 十l o n 5 = 8 根据上式又可分为两种情况：n s = 1 和礼5 _ 2 情况2 1 ：礼。= 1 时可分为如下三种情况： ( a ) ：扎4 = 0 ，n 3 一礼l = 5 ，珏1 + 钍2 = 5 ( b ) ：2 4 = 1 ，n 3 一n l = 3 ，n l 十礼2 = 7 ( c ) ：7 1 4 = 2 ，n a 一7 2 121 ，礼l + n 2 = 9 讨论( ：此时参数札扎3 ，n s 满足下面的值： ( 1 ) ：n 1 = 0 ，7 1 2 = 5 ，n 3 = 5 ，n 4 = 0 ，n 5 = 1 ( 2 ) ：n l = 1 ，n 2 = 4 ，n 3 = 6 ，7 1 4 = 0 ，2 5 = 1 ( 3 ) ：7 1 1 = 2 ，2 2 = 3 ，n 3 = 7 ，7 1 4 = 0 ，n 5 = 1 ( 4 ) ：礼1 = 3 ：几2 = 2 ，n 3 = 8 ，7 1 4 = 0 ，n 5 = 1 湖南师范大学硕士学位论文 1 2 ( 5 ) ：扎1 = 4 ，n 2 = 1 ，1 3 = 9 ，r 0 4 = 0 ，n 5 = 1 ( 6 ) ：礼1 = 5 ，札2 = 0 ，n 3 = 1 0 ，c 4 = 0 ，1 1 5 = 1 讨论( 1 ) ：满足( 1 ) 条件的图恰有g s 讨论( 2 ) ：因为5 - 顶点邻接的3 - 顶点可能是邻接两个2 一顶点或 一个3 一顶点和一个1 一顶点若5 一顶点邻接的3 一顶点互相连接，则 m 2 ，矛盾；若5 顶点邻接的3 一顶点与另外一个3 一顶点z 相连( 除 与5 顶点邻接的3 - 顶点) ，则由定义和上面的等式可知：z 必须要 与大于或等于三度的顶点相连，矛盾；若邻接的是两个2 一顶点，它 必须要邻接一个3 - 顶点y ，则必须要邻接一个大于或等于四度的 顶点，矛盾故不存在图我们可以类似的讨论( 3 ) ，( 5 ) 也不存在满 足条件的图满足( 4 ) 条件的图恰有g 6 ；满足( 6 ) 条件的图恰有g 。 讨论( 6 ) ：因为5 一顶点和4 一顶点必须连接3 一顶点，并且5 顶点 不与4 顶点共3 顶点，所以有n 3 9 又由n 。一m = 3 可知：n 1 6 另外，邻接4 一顶点的每个3 一顶点必须邻接两个2 顶点和一个3 _ 顶 点，故礼。2 则有礼1 + 礼2 8 ，而与n 1 + n 2 = 7 矛盾，故不存在图 讨论( c ) ：因为5 一顶点和4 一顶点必须连接3 一顶点，并且5 一顶点 不与4 i 顶点共3 一顶点，所以有n 。9 又由n 3 一竹t = 1 可知：n ，三8 另外，5 顶点邻接的3 一顶点必须连接一个3 一顶点和一个1 一顶点或 者连接两个2 一顶点若5 一顶点连接的点全是一个3 - 顶点和一个1 一 顶点，则对于一个连通图来说是不可能的，矛盾所以至少有一个 5 一顶点的邻接点是与与两个2 一顶点相邻，即n 。2 所以礼。+ n 。1 0 ， 而与礼，+ n 。= 9 矛盾故不存在这样的图 情况2 2 ：当咒。= 2 时，有如下两种情况： 若3 一调和图满足上面的条件，则它的顶点有如下性质： ( i ) ：5 顶点邻接的顶点必须是3 - 顶点且5 一顶点与5 一顶点不能共3 一 顶点 ( i i ) ：5 一顶点邻接的3 - 顶点必须是邻接一个3 一顶点和一个1 一顶点或 者两个2 顶点，可知2 一顶点是偶数 湖南师范大学硕士学位论文 1 3 讨论( n ) ：由( i ) 可知：礼3 1 0 又由n 3 一n ，= 2 可得：n l 8 易 知：礼l ，几3 ，n 。，佻满足下面的值： ( 1 ) ：7 5 1 = 8 ，他2 = 2 ，? 2 3 = 1 0 ，n 4 = 0 ，n 5 = 2 ( 2 ) ：n l = 9 ，礼2 = 1 ，t 3 = 1 1 ，n 4 = 0 ，几5 = 2 ( 3 ) ：n l = 1 0 ，n 2 = 0 ，n 3 = 1 2 ，n 4 = 0 ，n 5 = 2 又由( i i ) 可排除( 2 ) 考虑( 1 ) ，( 3 ) 两种情况：满足( 1 ) 条件的图恰 有：g 8 ，g 9 ，g l o ，g g 1 2 ；而满足( 3 ) 条件的图恰有：g 1 3 ，g 1 4 jg 1 5 ，g 1 6 ， g 1 7 ，g 1 8 ，g 1 9 ，g 2 0 ，g 2 1 ，g 2 2 ，g 2 3 讨论( 6 ) ：由性质( i ) 和( i i ) 易知：礼。1 4 又由n 3 一n 1 = 0 可得 而n - + n z = 1 2 ，矛盾故不存在图 情况3 ：由等式( 2 ) 和( 3 ) 可得如下情况： ( 8 ) ：扎4 = 1 ，? 3 一托l = 6 ，挖i + n 2 = 2 ( ：n 4 = 2 ，扎3 一咒i = 4 ，咒1 + 九2 = 4 ( c ) ：n 4 = 3 ，n 3 一n l = 2 ，n l + n 2 = 6 ( d ) ：n 4 = 4 ，n 3 - n 1 = 0 ，7 1 1 + n 2 = 8 讨论( a ) ：由调和图的定义和( a ) 中的顶点满足的条件易知：只有 当凡1 = 0 ，n 2 = 2 ，n 3 = 6 ，n 4 _ 1 时才有可能，此时恰有图g 2 4 ，g 2 5 讨论( b ) ：由( b ) 中满足的条件可知：n 1 7 礼a 满足下面的值： ( 1 ) ：n l = 0 ，n 2 = 4 ，n 3 = 4 ，佗4 = 2 ( 2 ) ：n l = 1 ，n 2 = 3 ，n 3 = 5 ，n 4 = 2 ( 3 ) ：几l = 2 ，n 2 = 2 ，竹3 = 6 ，n 4 = 2 ( 4 ) ：n l = 3 ，n 2 = 1 ，n 3 = 7 ，n 4 = 2 ( 5 ) ：n 1 = 4 ，n 2 = 0 ，t $ 3 = 8 ，n 4 = 2 讨论( 1 ) ：由调和图定义和( b ) 中顶点满足的条件可知：缸顶点 的邻接点必须邻接一个3 顶点和一个2 顶点，且4 顶点不能与4 一 顶点邻接，否则礼。1 ，矛盾故只可能是与2 一顶点相邻，但这时由 定义可知( 4 一顶点必须要与一个大于四度的顶点相邻) 矛盾，故( 1 ) 不存在图 对于( 2 ) ，( 4 ) ，( 5 ) 可类似的讨论，它们都不存在图只有情况( 3 ) 有满足条件的图，且其图恰有g 。6 ，g 。r ，g 2 s 讨论( c ) ：由条件可知札n 2 ，乱t 满足如下的值： 湖南师范大学硕士学位论文 1 4 【i ) ：n l = 0 ，7 1 2 = 6 ，n 3 = 2 ，n 4 = 3 ( 2 ) ：t l i = l ，礼2 = 5 ，n 3 = 3 ，“4 = 3 ( 3 ) ：礼1 = 2 ，? 2 2 = 4 ，7 1 3 = 4 ，7 2 4 = 3 ( 4 ) ：n 1 = 3 ，n 2 = 3 ，n 3 = 5 ，n 4 = 3 ( 5 ) ：礼1 = 4 ，n 2 = 2 ，n 3 = 6 ， 4 = 3 ( 6 ) ：n 1 = 5 ，扎2 = l ，礼3 = 7 ，n 4 = 3 ( 7 ) ：7 1 1 = 6 ，n 2 = 0 ，礼3 = 8 ，札4 = 3 此时，满足( 1 ) ，( 3 ) ，( 5 ) ，( 7 ) 条件的图不存在它们的证明方法类 似不妨证明( 3 ) ：显然可知：1 一顶点要与3 - 顶点相邻且1 一顶点邻 接的3 顶点必须接两个4 一顶点，否则由定义可知矛盾同样另一个 l 一顶点也有同样的结构不妨设其中的一个1 一顶点为z ，与其相邻的 3 一顶点为y ，与y 相邻的两个4 一顶点为n 又不妨设另一个1 一顶点 为z ，与它相邻的3 一顶点为，与，相邻的两个4 一顶点为m ，e 而4 ，顶 点m 只可能接两个3 一顶点或接一个4 顶点和一个2 顶点若m 接 一个4 一顶点和一个2 一顶点，这时与n 。= 3 矛盾；若4 一顶点m 接两 个3 一顶点，不妨设为c ，d 对于这两个3 一顶点，若接一个4 一顶点，则 必然有一个1 一顶点，而与m = 2 矛盾故它只能与一个3 _ 顶点和一 个2 一顶点连接，故可知n 。5 与已知7 s = 4 矛盾，所以不存在满足 条件的图 满足条件( 2 ) 的图恰有g 。；满足条件( 4 ) 的图恰有g 。o ，g 。- ；满足 条件( 6 ) 的图恰有g 3 2 ，g 3 。 讨论( d ) d ：若3 一调和图满足( d ) 的条件，则它的顶点满足下列性 质： ( i ) ：1 一顶点邻接3 顶点 ( i i ) ：每个二顶点邻接的必是两个3 一顶点或一个4 一顶点和一个2 一顶 点，故2 顶点是偶数 由上式性质( ) ，( 乱) 和( d ) 的条件可知满足条件的有： ( 1 ) ：n l = 0 ，n 2 = 8 ，札3 = 0 ，n 4 = 4 ( 2 ) ：n l = 2 ，n 2 = 6 ，n 3 = 2 ，n 4 = 4 ( 3 ) ：礼1 = 4 ，n 2 = 4 ，姚= 4 ，n 4 = 4 ( 4 ) ：n 1 = 6 ，n 2 = 2 ，n 3 = 6 ，n 4 = 4 ( 5 ) ：礼1 = 8 ，n 2 = 0 ，n 3 = 8 ，n 4 = 4 满足它们条件的图分别恰有如下： ( 1 ) ：g 3 4 ，g 3 5 ，g 3 6 ，g 3 7 ，g 3 8 ，g 3 9 ，g 4 0 ( 2 ) ：g 4 1 ，g 4 2 ，g 4 3 ，g 4 4 湖南师范大学硕士学位论文1 5 ( 3 ) ：g 4 5 ，g 4 6 ，g 4 7 ，g 4 8 ，g 4 9 ，g s o ，g 5 1 ，g 5 2 ( 4 ) ：g 5 3 ，g 5 4 ( 5 ) ：g 5 5 ，g 5 6 另外，一个r 一正则图有扣r 条边若它是连通的且r ：= 5 时，则 有；礼r n + 1 = 5 可知：礼= 南易知只有r = 3 ，佗= 8 时成立易由 6 1 知恰有图：g 5 7 ，g 5 8 ，g 5 9 g 6 0 ，g 6 1 删粹洒 g 1 g 4 g 2 g 5g 6 够冰罨魁 g 7g 8 g l o g 9 g 3 辞季纵 图1 所有的5 ，圈调和图 g 1 2 姐 湖南师范大学硕士学位论文 1 6 佟参翎垮 螺$ 爷魏 g 1 9g 2 0 暨磷参 黝酝蝴器 ! 二窆p 卜卜1 g 2 2g 2 3 图1 所有的5 一圈调和图( 续) 玲 湖南师范大学硕士学位论文1 7 g 3 4 g 3 2 g 2 7 舻 g 3 0 键 甘 图1 所有的5 _ 圈调和图( 续) 窖埝 令芗 湖南师范大学硕士学位论文 1 8 g 4 3 g 4 6 图1 所有的5 圈调和图( 续) g 4 8 湖南师范大学硕士学位论文 - 1 9 g 5 8g 5 9 熊 g 6 1 g 6 2 图1 所有的5 一圈调和图( 续) g 6 0 湖南师范大学硕士学位论文 3 3六圈调和图 由于2 c a 2 2 a + 2 ，故当c = 6 时，a = 3 或4 定理3 5 连通的六圈3 一调和图恰有7 4 个( 见图2 ) 其中，连通非 正则的六圈3 一调和图恰有5 5 个；连通正则的六圈3 一调和图恰有1 9 个 证明：先考虑非正则的情况当入= 3 时，由弓l 理可知：d ( z ) 2 一a + 1 ，则有 7 ，即6 由此可分为三种情况：情况1 ：a = 3 ，= 6 ；情况2 ：a = 3 ，：5 ： 情况3 ：a = 3 ，= 4 情况1 ：从引理6 得：n 。一7 ，0 又由等式( 2 ) 和( 3 ) 可得： 一2 ”1 2 n 2 + 4 n 4 + 1 0 n 5 + 1 8 n 6 = 0 根据上两式又可分为两种情况：t t 。一l 或n 。= 2 情况1 1 ：n 。= l 时又可分如下七种情况： ( a ) ：礼5 = 2 ，n 4 = 0 ，n 3 7 2 1 = 0 ，n l + n 2 = 1 9 ( b ) ：7 2 5 = 1 ，n 4 。1 ，1 3 一t t l = 1 ，n 1 + ? 2 2 = 1 6 ( c ) ：2 5 = 1 ，2 450 ，i t 3 一2 l = 3 ，t t l + 7 。2 = 1 4 ( d ) ： 2 5 = 0 ，n 4 = 3 ， 1 3 t t l = 0 ，t t i + n 2 = 1 5 ( e ) ：? t 5 = 0 ，n 4 。2 ，i t 3 一n 1 = 2 ，t t l + t 2 = 1 3 ( f ) ：r t 5 = 0 ，t t 4 ；1 ，n 3 一亿1 = 4 ，t i + n 2 = 1 1 ( g ) ：n 5 = 0 ，1 1 4 = 0 ，n 3 一t t l = 6 ，n l + n 2 = 9 如果3 一调和图满足上面条件，则它的顶点满足下列性质： ( i ) 1 一顶点必须邻接3 - 顶点 ( i i ) 6 一顶点和5 一顶点的邻点必须是3 一顶点 ( 每个邻接6 一顶点的3 一顶点必须邻接1 一顶点和 顶点 ( i v ) 6 一顶点，5 顶点和4 顶点都不能相邻，且不能共3 - 顶点 讨论( a ) ：由性质( i i ) 和( i i i ) 可知：n 3 1 6 ，n 2 芝4 又由他一佗1 = 0 可知：n 。1 6 ，故有礼- + n 。2 0 与( a ) 的条件矛盾，故不存在图 湖南师范大学硕士学位论文 2 1 讨论( b ) ：由性质( i i ) ( i i i ) 和( i v ) 可知：n 3 1 5 ，佗2 4 ，又由 n 。一n = l 可知：n t 1 4 ，故有n l + n 2 1 8 与( b ) 的条件矛盾，故不 存在图 讨论( c ) ：由性质( i i ) 和( i i i ) 可知：礼3 儿礼2 6 ，又由咒3 一n ，= 3 可知：n 1 8 只有当m = 8 ，n 2 = 6 ，n 3 = 1 1 ，n 5 = l ，n 6 = 1 时才有可 能，此时恰存在图g ，c 。 讨论( d ) ：此时分四种情况讨论：( 1 ) 若4 一顶点两两互相邻接 此时，由调和图定义知：它们都必须邻接2 一顶点这时，若配对连 接，则它不连通，矛盾若不配对连接，则n 。4 与n 。= 3 矛盾 故不存在图 ( 2 ) 若4 一顶点互相不连接则由性质( i i ) ( i v ) 可知：n 。21 4 ，礼2 4 又由n 3 一让1 = 0 可得：饥- 1 4 ，故n - - i - 礼。1 8 与( d ) 的条件矛盾 故不存在图 ( 3 ) 若3 个4 一顶点中的两个与另一个相邻此时，由性质( i i ) 和 ( i i i ) 知：n 3 1 0 ，n 2 6 ，又由n 3 一n 2 = 0 可得：n l 1 0 故礼l + n 22 1 6 与( d ) 的条件矛盾故不存在图 ( 4 ) 若3 个4 一顶点之中，只有两个是互相邻接的由性质( i i ) 和 ( i i i ) 可得：n 3 1 3 ，且n 226 ，又由竹3 一n l = 0 可得：礼1 1 3 ，故有 n 。+ n 。1 9 与( d ) 的条件矛盾故不存在图 综上所述，此时满足条件( d ) 的图不存在 讨论( e ) ：此时分二种情况讨论；( 1 ) 若4 一顶点不与4 一顶点相 邻则由性质( i i ) 和( i i i ) 可知：忆3 1 3 ，n 2 4 ，又由n 。一几1 = 2 可 得：n 。1 1 ，故有n ，+ n 。21 5 与( e ) 的条件矛盾故不存在图 ( 2 ) 若4 一顶点与垂顶点相邻时，由性质( i i ) 和( i i i ) 可得：礼3 1 0 且n 2 6 ，又由礼3 佗l = 2 得：m 8 ，故有7 , 1 + n 2 1 4 与( e ) 的条件 矛盾故不存在图综上所述，此时满足条件( e ) 的图不存在 讨论( f ) ：由性质( i i ) 和( i i i ) 易知：只有当n ，= 6 ，n 2 = 5 ，n 。= 1 0 ， n 4 = 1 ，n 5 _ 0 ，n 6 = 1 时才满足条件，此时恰有图g 3 ，g 4 讨论( g ) ：由性质( i i ) 和( i i i ) 可知：礼l 6 ，n 2 兰3 由礼1 + 扎2 = 9 可得：只有当n ，= 6 ，扎。= 3 才有可能成立，但是由n 。一n 。= 6 得 湖南师范大学硕士学位论文 2 2 n 。= 1 2 ，易知：必有n 。4 与啦= 3 矛盾故不存在图 情况1 2 ：礼e = 2 时可分如下两种情况： ( a ) ：n 5 = 0 ，? 2 4 = 1 ，礼： 一礼1 = 0 ，礼2 + 礼l = 2 0 ( b ) ：? 2 5 = 0 ，几4 = 0 ，礼3 一n l = 2 若3 一调和图满足上面的条件，则它的顶点有如下的性质： ( i ) 1 顶点必须邻接3 一顶点 ( i i ) 6 一顶点的邻点必须是3 一顶点且每个邻接6 顶点的3 一顶点必须邻 接l 一顶点和2 - 顶点 ( i i i ) 4 一顶点邻接的顶点也必须是3 _ 顶点，且4 一顶点不与6 一顶点共 3 一顶点 讨论( a ) ：由性质( i i ) 和( i i i ) 可知：n 3 1 6 且n 2 6 ，又由n 3 - - t 1 = 0 再得：n ，1 6 ，故有n ，+ 他2 2 与( a ) 的条件矛盾故不存在图 讨论( b ) ：由性质( i i ) 可知：九。1 2 ，n 。6 ，易知只有当7 2 1 _ 1 2 ， 札2 = 6 ，n 3 _ 1 4 ，n 4 = 0 ，n 铲0 ，凡6 = 2 时才成立但是，每个2 一顶点至 多邻接两个3 一顶点，还剩下两个3 - 顶点矛盾故不存在图 情况2 ：由等式( 2 ) 和( 3 ) 可得： - - 2 h i 一2 n 2 + 4 n 4 + l o n 5 0 根据上式又可分为三种情况：扎5 _ 1 ，扎。= 2 和= 3 情况2 1 ：礼5 _ 1 时可分为如下四种情况： ( a ) ? 2 4 = 3 ，? 2 3 7 2 1 = l ， n l + n 2 = 1 1 ( b ) ? 2 4 = 2 ，n 3 一m = 3 ，n l + n 2 = 9 ( c ) n 4 = 1 ，? 2 3 1 2 1 = 5 ，n l + ”2 = 7 ( d ) ? 2 4 = 0 ，n 3 一n l = 7 ，凡l + ? 2 2 = 5 若3 一调和图满足上面的条件，则它的顶点有如下性质： ( i ) 1 一顶点邻接的顶点必须是3 一顶点 ( i i ) 5 一顶点邻接的必是3 _ 顶点，且每一个邻接5 一顶点的3 一顶点必须 邻接两个2 一顶点或一个1 一顶点和一个3 一顶点 ( i