（基础数学专业论文）关于两类二部图能量的探究.pdf

。 1 吣i i ih l 舢叭删叭帆帅 l 。y 17 6 018 7 青海师范大学学位论文使用授权声明 青海师范大学、中国科学技术信息研究所、国家图书馆 有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部 或部分内容。论文的公布( 包括刊登) 授权由青海师范大学 研究生部办理。 研究生签名：才弓孔导师签名：棚细日期 即，口多 关于两类二部图能量的探究 摘要 一个图g = ( ve ) 的能量指的是其特征多项式的特征值的绝对值之和即； e ( c ) = 翟1i 九i 本论文是在前人的基础上，更进一步的对两类特殊二部图能量 进行了研究主要内容包括： 第一章介绍了涉及的一些基本概念和术语，图的能量的研究现状以及本论文中 所得到的主要结果 论文第二章讨论了特殊( 佗，仇) 一二部图的第二小到第四小能量图及排序 毛毛虫指删掉所有的悬挂边之后仅剩下条路的图，记为t ( n ，d ；r l l ，竹2 ，n d 1 ) 死。d ，毛毛虫中有n 个顶点，直径为d ，其中的条直径上的点由v o ，v d 构成，再 分别粘结n i ( n i 0 ) 个悬挂边到仇，( i = 1 ，2 ，d 一1 ) 上，n = d + 1 + 江d - 1 1h i ； 论文的第三部分主要得出当直径在3 d 5 时树的第二，三，四小能量图分别 为：当d = 3 时，t ( n ，3 ；1 ，佗一5 ) 为唯一的第二小能量图；t ( n ，3 ；2 ，佗一6 ) 为唯一的第 三小能量图；t ( n ，3 ；3 ，n 一7 ) 为唯一的第四小能量图；当d = 4 时，t ( n ，4 ；1 ，0 ，n 一6 ) 为唯一的第二小能量图；t ( n ，4 ；0 ，佗一5 ，0 ) 为唯一的第三小能量图；t ( n ，4 ；2 ，o ，n 一7 ) 为唯一的第四小能量图；当d = 5 时，t ( n ，5 ；0 ，r t 一6 ，0 ，0 ) 为唯一的第- d , 能量图； t ( n ，5 ；1 ，0 ，0 ，几一7 ) 为唯一的第三小能量图；t ( 5 ；2 ，0 ，0 ，佗一8 ) 为唯一的第四小能 量图；论文的第四章中，我们讨论了一些进一步研究的问题 t 关键词；二部图；树；直径；能量 r e s e a r c ho ns o m eb i p a r t i t eg r a p h s e n e r g y a b s t r a c t t h ee n e r g yo fag r a p hg = ( v e ) i sd e f i n e d 懿t h es u mo ft h ea b s o l u t ev a l u e si t s a l le i g e n v a l u e s t h a ti s ：e ( g ) = 磐li 九i t h i sp a p e rw h i c hs t a n d so nt h eb a s i so f p r e v i o u sr e s u l t s ，a n dw h i c hf u r t h e rr e s e a r c ho nt h ei s s u eo ft h ee n e r g yo fs o m eb i p a r t i t e g r a p h ，m a i n l yi n c l u d e s ： i nc h a p t e r1 , w ei n t r o d u c es o m eb a s i ct e r m i n o l o g ya n dn o t a f i o n s ，t h er e s e a r c hb a c k - g r o u n da n dp r o f o u n dd i s c u s s i o no nt h es t a t u sq u o o fg r a p hn e n r g y ，a n ds h o w st h em a i n r e s u l t so ft h i sp a p e r i i lc h a p t e r2 , w em a i nt a l ka b o u t ( n ，m ) - b i p a r t i t eg r a p ha n dw eo b t a i nt h es e c o n dt o f o u r t hs m a l lg r a p h a c a t e r p i l l a ri sat r e ei nw h i c har e m o v a lo fa l lp e n d a n tv e r t i c e sm a k e sap a t h 1 e t t ( n ，d ；n l ，仡2 ，n d 一1 ) 死，db eac a t e r p i l l a ro b t a i n e df r o map a t hv o ，v l ，v db ya t t a c h i n g m ( m 0 ) p e n d a n te d g e st o 耽，( i = 1 ，2 ，d 一1 ) c l e a r l y , n = d + 1 + 扭d - 1 i 啦； i nc h a p t e r3 , w em a i nt a l ka b o u tt h et r e e sw i t hag i v e nd i a m e t e rb e t w e e n3 a n d 5a n d o b t a i nt h es e c o n dt of o u r t hs m a l lg r 印h w h e nd = 3 , t ( n ，3 ；l ，n - 5 ) i st h eo n l ys e c o n ds m a l l g r a p h ；t ( n ，3 ；3 ，n 一6 ) i st h eo n l yt h i r ds m a l lg r a p h ；t ( n ，3 ；3 ，n 一7 ) i st h eo n l yf o u r t hs m a l l g r a p h ；w h e nd = 4 , t ( n ，4 ；1 ，0 ，佗一6 ) i st h eo n l ys e c o n ds m a l lg r a p h ；t ( n ，4 ；0 ，佗一5 ，0 ) i st h eo n l yt h i r ds m a l lg r a p h ；t ( n ，4 ；2 ，0 ，亿一7 ) i st h e o n l yf o u r t hs m a l lg r a p h ；w h e n d = 5 , t ( n ，5 ；0 ，n 一6 ，0 ，0 ) i st h eo n l ys e c o n ds m a l lg r a p h ；t ( n ，5 ；1 ，0 ，0 ，佗一7 ) i st h eo n l y t h i r ds m a l lg r a p h ；t ( n ，5 ；2 ，0 ，0 ，n - 8 ) i st h eo n l yf o u r t hs m a l lg r a p h ；i nc h a p t e r4 , w ep r o p s e s o m ep r o b l e m sf o rf a r t h e rr e a s u r eb i p a r t i t eg r a p h k e y w o r d s ：b i p a r t i t eg r a p h ；t r e e ；d i a m e t e r ；e n e r g y 2 目录 第一章绪论 1 1 本文中用到的两种拓扑指标：4 ，1 2 基本概念与术语5 1 3 二部图能量的研究进展5 1 4 本文的研究简介8 第二章关于( 扎，m ) 一二部图的第二小到第四小能量的图及排序 2 1 预备知识主要引理9 ：2 2 毒要结果及证明：1 2 第三章给定直径的树的极小能量图 3 1 预备知识及引理1 7 3 2 主要结果及证明1 9 第四章结束语 4 1 可进一步研究的问题2 5 参考文献 致谢 附录一作者攻读硕士学位期间完成和发表的论文 3 第一章绪论 1 1 本文中用到的两种拓扑指标 个图g 指的( g ) ，e ( g ) ) ，其中v c g ) 是非空的顶点集，e c g ) 是边集，若e 是条边，乱和口是边e = u 口的顶点，称e 边连接顶点u 和t ，顶点缸和勘称为e 的端点i v c c ) l 表示g 中的顶点数，l e ( g ) i 表示g 中边数 1 h o s o y a 拓扑指标 h o s o y a 指标是由日本化学家h o s o y a 于1 9 7 1 年提出的f 2 】，定义为； z ( g ) ；m ( g ，七) k = o 其中m ( c ，k ) 为在图g 中选取k 条边，使得两两都不相邻的选取方法的数目，称为 k 匹配数，k = 0 ，1 ，【量j 定义m ( g ，0 ) = 1 2 图的能量拓扑指标 令g 是n 个顶点的图，其邻接矩阵的佗个特征值分别为a 1 ，a 2 ，a 几，图g 的 能量e ( g ) 指的是特征多项式的特征值的绝对值之和： 几 e ( g ) = h i i = l 这一概念由g u t m a n 引进 2 2 】，由于它具有可以用来粗略估计一个分子的7 r 一电 子能量的性质而在化学中被广泛研究对于图g ，令m ( c ，) 为图g 中一匹配数j 目，这里k 1 ，定义m ( g ，0 ) = 1 若图g 为二部图，图的特征多项式为【6 】 庐( g ) = ( 一1 ) 七m ( t ，忌) z 舾2 七 那么二部图g 的能量由c o u l s o n 公式可表示如下， 即，= 玎z 1 州墨m c 蒜2 恤 由c o u l s o n 公式可知，e ( g ) 是个关于m ( g ，k ) 的严格单调递增函数， 1 ，【鸶j ，基于该事实，g u t m a n 定义了一个偏序；对于g 1 和g 2 ， g 1 三g 2 营m ( g 1 ，k ) m ( g 2 ，k ) 4 对于所有的k 1 均成立 ： 若g l g 2 ，而且存在某个j 使得m ( c 1 ，j ) m ( g 2 ，歹) ，那么我们记为g 1 - 岛， 因此， g 1 卜g 2 兮e ( g 1 ) e ( g 2 ) 1 2 基本概念与术语 一 本文只研究无向有限图，文中未加说明的图论术语见文献【1 】 一个图的直径指的是g 中的两个顶点之间的最大距离； ： 二部图( 或偶图) 是指个图，它的顶点集可以分解成两个非空子集x 和y ，使 得每一条边都有个端点在x 中，另一个端点在y 中，这样的一种分类伍，y ) 称 为图的个二分类 记u y ( g ) ，e e ( g ) ，g 一口表示从g 中删去口及和这个顶点相关联的边所得 的图，g e 表示从g 中删去边e 所得到的图 下面是本文要用到的一些记号和图的定义z r 表示阶为竹的路； 瓯表示n 个顶点的的圈； ( n ，m ) - 表示具有n 个点m 条边的所有二部图类； 代表具有n 个顶点的树类； t 死d 代表具有扎个顶点，直径为d 的树类； 毛毛虫指的是删掉所有的悬挂边之后仅剩下一条路的图，记为t ( n ，d ；? t l ，n 2 ，粕一1 ) 死d ，毛毛虫中有礼个顶点，直径为d ，其中的条直径上的点由v o ，口1 ，v d 构成，再 分别粘结r l i ( 7 i 之0 ) 个悬挂边到地，( t = 1 ，2 ，d 一1 ) 上，n = d + 1 + 蟹h i ； 1 3 二部图能量的研究进展 在文献【9 】中g c a p o r o s s i ，d ，c v e t k o v i ，g u t m a n ，p ，h a n s e n 提出猜想：顶点 数佗6 ，边数m 满足他一1 m 2 ( n 一2 ) 连通图g ，若( m 竹+ 【( 丁- 7 ) j ) ，最，j 、能 量图即为星图添加m n + l 条边至同一顶点形成的图；否则，为二部图，其中一 个分部有两个顶点，并且其中的一个点与另个分部的所有点关联 该猜想已被几个人分情况证明成立：其中g c a p o r o s s i ，e t a l 证明了当m = 佗一 l ，2 一2 ) 时结论成立【4 9 ；h o u 在2 0 0 1 年证明了m = n 时结论成立 5 0 】，x ，l i ，e t a l 5 在2 0 0 8 年【2 2 】证明了当佗m 2 n 一5 时最小能量图为b ( n ，m ) 见( 图1 ) ；它是一 个二部图，个顶点集h 有两个顶点，另个顶点集屹有n 一2 个顶点构成的 中的个顶点和的所有点关联，的另个点和k 的m n + 2 关联本文 在前人基础上给出了当n m 2 n 一5 时( n ，m ) 一二部图的第二，第三，第四小能 量图分别为b 2 ( n ，m ) ，( 图2 ) ，b 3 ( n ，m ) ，( 图3 ) ，风( n ，仇) ，( 图4 ) ，并且给出( 扎，m ) 的 排序 1 图1 l 2 2 n 一”l 一4 岛( 佗，m ) 见( 图2 ) ，是由b ( n ，m ) 原有的个悬挂点移到第二大度点上构成的 1 2 礼一仇+ 2 2 n m 一5 图2 b 3 ( n ，m ) 见( 图3 ) ，是由b ( n ，m ) 原有的两个悬挂点移到第二大度点上构成的 6 l 。2 l 佗一m + 2 图3 1 2 2 n m 一6 b 4 ( n ，m ) 见( 图4 ) ，是由b ( 凡，m ) 原有的三个悬挂点移到第二大度点上构成的 他一m + 2 图4 1 2 2 n m 一7 令t 死，d ( 2 d n 一1 ) ，文献【4 4 】刻画了磊d 中唯极小的能量树，文献 【4 6 】给出了死。d 中的第二小能量树，但在小直径时遗留了一个问题，本部分就这一 课题提出了猜想，并刻画了当直径3 d 5 时树的第二，第三，第四小能量图 7 1 4 本文研究简介 本文的第二章讨论了特殊( n ，m ) 一二部图能量的第二小到第四小能量及排序 其中第二小图为b 2 ( n ，m ) ，第三小图b 3 ，m ) ，第四小图芒h ，m ) 。以及对b ，m ) 图的排序； !论文的第三部分主要得出当直径在3sds5 时树的第二，三，四小能量图分别 为；当d = 3 时，t ( n ，3 ；1 ，佗一5 ) 为唯一的第- d , 能量图；t ( n ，3 ；2 ，n 一6 ) 为唯一的第 到、能量图；t ( n ，3 ；3 ，n 一7 ) 为唯一的第四小能量图；当d = 4 时，t ( n ，4 ；1 ，o ，n 一6 ) 为唯一的第- - z j 、能量图；t ( n ，4 ；0 ，n 一5 ，0 ) 为唯一的第三小能量图；t ( n ，4 ；2 ，0 ，n 一7 ) 为唯一的第四小能量图；当d = 5 时，t ( n ，5 ；0 ，n 一6 ，0 ，0 ) 为唯一的第二小能量图； z ( n ，5 ；1 ，0 ，0 ，佗一7 ) 为唯一的第三小能量图；t ( n ，5 ；2 ，0 ，0 ，佗一8 ) 为唯一的第四小能 量图； 论文的第四章主要讨论了二部图进一步可研究的问题； 8 第二章关于( 他，m ) 一二部图的第二小到第四小能量的图及排序 根据文献【9 】中g c a 删r o s s i ，d ，c v e t k o v i ，i ，g u t m a n ，p ，h a n s e n 的猜想，本部分 研究的( n ，m ) 二部图只需考虑其中的一个分部只有两个顶点 2 1 预备知识及引理 记图g 的特征多项式咖( g ) = 饕。吼入n 一当i 之1 时， a i = ( - 1 f ( 8 ) 2 。( 5 8 c 工h 其中厶记为g 中i 个点的s a c h s 子图；也就是说图s 的分支或者为乜或者为 圈只为s 中的分支数和c ( 8 ) 为s 中包含的圈数，另外规定a o = 1 令b 2 i ( g ) = ( - 1 ) 4 a 2 i ，b 2 , + l ( g ) = ( - 1 ) a 2 i 十1 ，显然，b l ( g ) = 1 , b 2 ( g ) 等于图g 的边数 又由文献 2 2 】二部图g 的能量由c o u l s o n 公式可表示如下， e ( g ) 。新z l n 【l + ( 吾6 2 i x 2 i 由s a c h s 定理可得： 引理2 1 【1 0 】b 4 ( g ) = m ( g ，2 ) 一2 q ( g ) 其中q ( g ) 为g 中四边形个数 引理2 2 【2 2 1 记伽为g 中的割边，e ( g t 一v ) 表示g 中删去点u ，t ，后得到的 图g u 一口的边数，那么就有 b 4 ( g ) = 6 4 ( g u ) + e ( g u u ) 特别的，若u 口为g 中的悬挂边，且u 为悬挂点，则有， b 4 ( a ) = b 4 ( g 一口) + e ( g t 一口) 引理2 3 1 2 2 】b ( n ，m ) sm 2 n 一5 ) 为( 他，m ) 一二部图中唯一的最小能量图 引理2 4 2 2 l ( n ，m ) 二部图，当n ms2 n 一5 有 口c g ，( m 一；+ 2 ) 其中q ( g ) 为g 中四边形个数 9 引理2 5 【2 2 1 在所有的( 礼，m ) 二部图g 中，若g 无悬挂点，那么： 。蒹m ，- 吲z 叩；，艘) 引理2 6 2 2 对于图g ： 邮= ( 习一p 蒜) 引理2 7 对于( 死，m ) 二部图，g 中无悬挂边，当b ( n ，m ) 有最大的。( g ) ( d 拿) 则b 2 ( n ，r a ) 有第二大的。( g ) ( d 9 ) b z ( n ，m ) 有第三大的。( g ) ( d 擘) b 4 ( n ，仇) 有第 四大的。( g ) ( d 妒) 证明记： ( d ) c = ( d l ，d 2 ，也一1 ，也d j ，d j + l ，厶) ( 1 ) ( d ，g = ( d l ，d 2 也一l ，也+ 1 而一1 ，吗+ 1 d r ) ( 2 ) 其中，也而，d l2d 2 一厶之2 ，且d 1 + d 2 + 一磊= 2 m ，将( d ) 0 又可记为： ( d ) 0 = ( 4 ，如，z 一。，弓，弓+ 。，五) 那么我们可以得到： 耋( 雪) 砉( 李) 因为： 翟- ( 鲁) 一罄。( 李) = ( 也1 ) 4 - ( 由f 1 ) 一( 壹) 一( 字) = 丝产+ 垃学盛一垃业2 一工与丝 = 成一嘞一手+ 1 + 孝 = 盔一而+ 1 0 不断的应用以上变换，我们能够得出新的度序列： ( d ) ”= ( ，d s d r 一n + 4 ，和) 并且= n 一2 时，n 一2 ，之如，若有 。 综合上面的比较，( 4 ) 式的度序列对2 取组合数有第二大的值而b 2 m ，m ) 的 度序列为： r g t - - e l + 22 n - - m - 4 ( d ) b 。( n 。m ) = ( n 一3 ，m n + 3 ，和，和) 所以，岛( 仃，仇) 有第二大的v ( g ) ( d ) 同理，当g b ( n ，m ) ，g b 2 ( n ，m ) 时，b s ( n ，m ) 有第三大的。( g j ( d 譬) 其形 式为。 r f t - n + 22 n - - m - - 4 ( d ) 历( n ，州= 仰一4 ，m n + 4 ，和，和 当g b ( n ，仇) ，g b 2 ( n ，m ) ，g b 3 ( n ，m ) 时，b 4 ( n ，仇) 有第四大的e v ( g ) ( d 拿) 其形式为： 。 m - n + 22 n - - m - - 4 ( d ) 风( n ，m ) = ( 他一5 ，m n + 5 ，雨囊，窳 2 2 主要结果及证明 定理1g ( 佗，m ) 一二部图，其中的一个分部只有两个顶点， 玩( 佗，m ) ( 1 7 , s 7 7 l 2 n 一5 ) 为( 礼，m ) - 二部图中唯具有第二小能量图 证明因为b o ( b 2 ( n ，m ) ) = 1 , b 2 ( b 2 ( n ，m ) ) = m ，b 4 ( b 2 ( n ，m ) ) = ( 7 n 一亿+ 3 ) ( 2 n 一 仇一4 ) 一1 ，b i ( b 2 ( n ，m ) ) = 0 ，当l 取其他整数时均成立当g 晶，仇时，因6 0 ( g ) = 1 ，6 2 ( g ) = m ，所以只需证明6 4 ( g ) b 4 ( b 2 ( 孔，m ) ) 我们对佗进行数学归纳从【4 8 】 我们已经知道当佗= 8 时已经成立，故我们假设当佗9 时此结论对所有小于1 7 , 的 数都已成立 情形1 当g 中有悬挂边u 0 时，且t ，为悬挂点，由引理2 2 则； b 4 ( g ) = b 4 ( g 一掣) + e ( g t 一u ) g b n ，m ，( n ，m ) 图中的一个部分只有两个顶点，所以有a ( g ) sn 一3 ，那么 e ( g u v ) m 一( g ) m n + 3 = e ( s ：m - n + 4 ) 1 2 用归纳假设：b 4 ( g 一口) 2b 4 ( b 2 ( n 一1 ，m 一1 ) ) 又因为b 4 ( b 2 ( n ，m ) ) = b d s 2 ( n l ，m 1 ) ) + e ( s - n + 4 ) ， ： 所以b 4 ( g ) b 4 ( b 2 ( n ，m ) ) 情形2 当g 中无悬挂边时由引理2 1 ，2 6 得； 郴，= ( 苫) 一。翕) 柏c a ； 。 ： 淝帆删= ( m ) 一倒。，( d 詈) 咄c 跏， 因口( b 2 ( m ) ) = g ( b ( 佗，m ) ) ，( 写) 的值两式相等再结合引理2 7 ，岛( n ，仇) 有第二 大的。( g ) ( d 拿) 所以b 4 ( g ) b 4 ( h ( n ，m ) ) 综合以上两种情况定理1 证完 又因为b 2 ( n ，m ) 的特征多项式为； 一 咖( b 2 ( 礼，m ) ) = x n - 4 ( 2 7 4 一m z 2 + ( ( m 一佗+ 3 ) ( 2 扎一仇一4 ) 一1 ) ) 因此我们有推论l ： 推论1g 为( n ：m ) 二部图，其中的个分部只有两个顶点，且佗m 2 n 一5 ， 若g b ( n ，m ) ，那么： ：e ( g ) 2 、m + 2 、( m n + 3 ) ( 2 礼一m 一4 ) 一1 等号成立当且仅当g 竺b 2 ( n ，仇) 。 定理2g ( z , ，m ) 一二部图，其中的一个分部只有两个顶点，b s ( n ，m ) m 2 n 一5 ) 为( n ，m ) - 二部图中唯一具有第三小能量图 证明因为b o ( t h ( n ，m ) ) = 1 ，6 2 ( 玩( n ，m ) ) = 仇，b 4 ( b 3 ( n ，m ) ) = ( m 一竹+ 4 ) ( 2 n 二 m 一4 ) 一4 ，b i ( b s ( n ，m ) ) = 0 ，当i 取其他整数时均成立当g b n ，m 且g b 2 ( 小) 时，因b o ( g ) = 1 , b l ( g ) = m ，所以只需证明6 1 4 ( g ) 之b 4 ( b s ( n ，m ) ) 我们对n 进行数学 归纳从【4 8 】我们已经知道当竹= 9 时已经成立，故我们假设当礼1 0 时此结论对 所有小于n 的数都已成立 情形1 当g 中有悬挂边伽时，且t ，为悬挂点，由引理2 2 则： 6 4 ( g ) = b 4 ( g t ，) + e ( g t 一钞) 1 3 g 岛，m ，g 岛( n ，m ) ，( 佗，m ) 图中的个部分只有两个顶点，所以有z x ( a ) 他一4 ，那么， e ( c t 一t ，) 之m a ( v ) 芝仇一他+ 4 = e ( 8 m 一l + 5 ) 用归纳假设：b 4 ( g 一口) b 4 ( b 3 ( n 一1 ，m 1 ) ) 又因为b 4 ( b 3 ( n ，仇) ) = b 4 ( b a ( n - 1 ，m 一1 ) ) + e ( - n + 5 ) ，所以b 4 ( g ) 6 4 ( b 3 m ，m ) ) 情形2 当g 中无悬挂边时由引理2 1 ，2 6 得： 郴，= ( 写) 一。品) 咄c k c 玩，m ，= ( ：) - 。y 。劢e 。n ，m ，( d 詈) 一2 q c b s ，m ， 因q ( b 3 ( n ，m ) ) = q ( b ( n ，m ) ) ，( 孑) 的值两式相等再结合引理2 7 ，s 3 ( n ，m ) 有第三 大的。( g ) ( d 拿) 所以b 4 ( g ) 之b 4 ( b 3 ( n ，m ) ) 综合以上两种情况定理2 证完 又因为b 3 ( n ，m ) 的特征多项式为： 咖( b 3 ( 佗，仇) ) = x n - 4 ( z 4 一m t 2 + ( ( m 一几+ 4 ) ( 2 几一m 一4 ) 一3 ) ) 因此我们有推论2 ： 推论2g 为( 礼，m ) 二部图，其中的一个分部只有两个顶点，n 9 且几sm 2 n 一5 ，若g b ( 他，m ) ，g b 2 ( n ，m ) ，那么： i e ( g ) 22 m + 2 、( m 一亿+ 4 ) ( 2 n m 一4 ) 一3 等号成立当且仅当g 鲁b 3 ( n ，m ) 定理3g 为( 他，m ) 二部图，其中的个分部只有两个顶点，风( n ，仇) 优 2 n 一5 ) 且n 1 0 为( 几，m ) 一二部图中唯具有第四小能量图 证明因为6 0 ( 风m ) ) = 1 , b 2 ( b 4 ( n ，m ) ) = m ，b 4 ( b 4 ( n ，m ) ) = ( m n + 4 ) ( 2 n m 一 4 ) 一9 ，b i ( b 4 ( n ，m ) ) = 0 ，当i 取其他整数时均成立当g 晶m ，g b 2 ( n ，m ) ，g b 3 ( n ，m ) 时，因b o ( a ) = 1 , b z ( g ) = m ，所以只需证明b 4 ( g ) b 4 ( s 4 ( n ，m ) ) 我们对n 进行数学归纳从【4 8 】我们已经知道当佗= 1 0 时已经成立，故我们假设此结论对所 有小于扎的数都已成立 】4 情形1 当g 中有悬挂边删时，且t i 为悬挂点，由引理2 2 则： b 4 ( g ) = b 4 ( g v ) + e ( g 一一t ，) 又g b n 朋g 岛( n ，m ) ，g b 3 ( n ，m ) ，( m ) 图中的个部分只有两个顶点， 所以有( g ) 礼一5 ，那么， e c c u t ，) m 一( g ) m 一竹+ 5 = e ( s m n + 6 ) 用归纳假设；b 4 ( g 一口) 之b 4 ( b 4 ( n 一1 ，m 一1 ) ) 又因为b 4 ( b 4 ( n ，m ) ) = b 4 ( 1 3 4 一 1 ，m 一1 ) ) + e ( s 一作+ 6 ) ，所以6 4 ( g ) b 4 ( b 4 ( n ，m ) ) 情形2 当g 中无悬挂边时由引理2 1 ，2 6 得： 郴，= ( 孑) 一。氦，( d 吩2 邸， k c b 4 c 仉m ，= ( 写) - y 。风e 。n ，m ，( d 詈) 一2 9 c 风，m 因q ( b 4 ( n ，m ) ) = q ( s ( n ，m ) ) ，( 孑) 的值两式相等再结合引理2 7 ，b 4 ( 亿，m ) 有第四 大的。( g ) 、d ( 2 v ) ) 所以b 4 ( c ) b 4 ( b 4 ( n ，m ) ) 综合以上两种情况定理3 证完 又因为b 4 ( 佗，仇) 的特征多项式为： 咖( 昆( n ，仇) ) = x n - - 4 ( z 4 一m x 2 + ( m 一亿+ 4 ) ( 2 n m 一4 ) 一9 ) ) 因此我们有推论3 ： 推论3g 为( 几，m ) 二部图，其中的一个分部只有两个顶点，n 1 0 且佗仇s 2 佗一5 ，若g b ( 佗，m ) ，g b 2 ( n ，仇) ，g b 3 ( n ，m ) ，那么： e ( g ) 2 、m - i - 2 v ( m n + 4 ) ( 2 n 一竹i 一4 ) 一9 等号成立当且仅当g 釜b 4 ( 佗，仇) 类似以上定理，我们可以得到其中一个分部只有两个顶点的( n ，仇) 二部图依能 量的序 ， 1 5 推论4 当n 足够大的的时候，( n ，m ) 二部图，其中的个分部只有两个顶点， 依能量的序为： b t 甲j ( n ，m ) 芝_ l - b 4 ( n ，m ) 三b 3 ( n ，仇) 三b 2 ( n ，m ) 三b ( n ，m ) 1 6 第三章给定直径的树的极小能量图 一 。 个图的直径指的是g 的两个顶点的最大距离文献恸z m a t h l e v t 1 8 ( 2 0 0 5 ) 1 0 4 6 - 1 0 5 2 】和文献 j o u r n a l o f m a t h e m a t i c a l c h e m i s t r y ，3 9 ( 2 0 0 6 ) 4 6 5 4 7 3 运用数学归纳法 分别证明了给定直径的树的最小和第二小能量图，分别为t ( n ，d ；n d 一1 ，0 ，0 ) 和 t ( 佗，d ；0 ，0 ，n d 一1 ，0 ，o ) ，t 死d ，d 6 ，但是当d 取小直径时并没有完全解决 而本部分完全解决了直径3 d 5 时树的第二，三，四小能量图 。 引理3 1 d 3 , n 6 ，t ( n ，d ；儿一d 一1 ，0 ，0 ) 是死d 中唯具有极小能量的 树 引理3 2 f 4 6 1t 死，d ，d 之6 ，t t ( 他，d ；佗一d 一1 ，0 ，o ) ，t t ( n ，d ；o ，0 ，他一d 一 1 ，0 ，o ) 那么t 三t ( n ，d ；0 ，0 ，n d 一1 ，0 ，o ) ，等号成立当且仅当t 兰t ( n ，d ；0 ，0 , ：7 2 一 d 一1 ，0 ，o ) 弓i 理3 3 】t ，4 ，佗7 ，若t t ( 佗，4 ；n 一5 ，0 ，o ) ，t t ( n ，4 ；1 ，0 ，扎一6 ) ，t t ( n ，4 ；0 ，n 一5 ，o ) ，贝0 丁卜t ( 亿，4 ；l ，0 ，7 , 一6 ) 弓i 理3 4 4 6 t 死。5 ，佗8 ，若t t ( n ，5 ；n 一6 ，0 ，0 ，o ) ，t t ( 5 ；1 ，0 ，0 ，n 一7 ) ，t t ( n ，5 ；0 ，佗一6 ，0 ，o ) ，贝47 卜t ( 佗，5 ；1 ，0 ，0 ，佗一7 ) 引理3 5 【5 l ! 若，是由t 经运算1 得到，则e ( ，) e ( r ) 运算中的五为无圈 图 乱 u 运算1 t 考r 移l 仇 u 2 t s 引理3 6 【5 1 】若t 7 是由t 经运算2 得到，则e ( t 7 ) e ( t ) 运算中的噩，t d ，正m 为无圈图 运算2 , t 净， 引理3 7 【5 l 】t 死，d ，3 ds 佗一2 ，若t 不是毛毛虫，则反复运用运算2 ，则我 们最总可得到个毛毛虫，则e ( ，) o ； 引理3 1 2 4 5 】记g 为森林，g 7 为g 的生成子图，则有g 芝g ，；若为真生成子 图则g 卜g ， 3 2 主要结果及证明 定理3 1 对于t ( 3 ；a 6 ) ，0 n b ，依能量排序为； t ( 亿，3 ；a ，6 ) 卜t ( n ，3 ；口一 1 ，6 + 1 ) - t ( n ，3 ；a 一2 ，6 + 2 ) - t ( n ，3 ；2 ，n 一6 ) - t ( n ，3 ；1 ，n - - 5 ) t ( 佗；3 ；0 ，他一4 ) 证明对于直径为3 的树可以直接表示为t t ( n ，3 ；a ，6 ) ，0 口6 ，口+ b = n 一4 ， 首先对t ( 佗，3 ；a ，b ) 与t ( 几，3 ；a 一1 ，b + 1 ) 的能量大小进行讨论由计算知道； m ( t ( n ，3 ；a ，6 ) ，2 ) = ( a + 1 ) ( 6 + 1 ) 仇( 丁( 佗，3 ；a ，6 ) ，后) = 0 ，( k 之3 ) m ( t ( 佗，3 ；a 一1 ，b + 1 ) ，2 ) = a ( b + 2 ) m ( t ( n ，3 ；a 一1 ，b + 1 ) ，k ) = 0 ，( k 3 ) 由作差比较得：( 0 + 1 ) ( 6 + 1 ) n ( 6 + 2 ) ，由引理3 1 1 知t ( n ，3 ；a ，b ) - r ( n ，3 ；a 一 1 ，6 + 1 ) 成立类似于上面过程，我们可以得出t ( m 3 ；口一1 ，6 + 1 ) 卜t ( n ，3 ；a 一2 ，6 + 2 ) ， 递推得定理成立 推论3 1t ( n ，3 ；a ，6 ) ，n s , t ( n ，3 ；n 一4 ，0 ) 为唯一的有第- z j 、能量图；t ( n ，3 ；n 一 5 ，1 ) 为唯一的有第三小能量图；t ( n ，3 ；扎一6 ，2 ) 为唯一的有第四小能量图； 定理3 2 直径d = 4 时，t ( n ，4 ；1 ，q ，礼一6 ) 为唯一的第二小能量图；t ( n ，4 ；0 ，n 一 5 ，0 ) 为唯一的第三小能量图； 1 9 证明由引理3 3 可知：只需比较t ( n ，4 ；1 ，0 ，n 一6 ) 和t ( n ，4 ；0 ，n 一5 ，0 ) 的能量 大小两图如下： 1 n 一6 t ( n ，4 ；l ，0 ，n 一6 ) 1 7 , 5 t ( n ，4 ；0 ，礼一5 ，0 ) 由引理3 9 代入计算得，( r ( 仃，4 ；1 ，0 ，n 一6 ) ) = x o ( t ( n 一1 ，4 ；0 ，0 ，伸一6 ) ) 一 z 西( s n 一3 ) = x 2 ( t ( n 一2 ，3 ；0 ，几一6 ) ) 一z 西( s n 一3 ) 一z ( s n 一3 ) 咖( t ( 仡，4 ；o ，礼一5 ，o ) ) = z 西( t ( 礼一l ，3 ；o ，礼一5 ) ) 一x d p ( t ( n 一2 ，3 ；0 ，n 一6 ) ) = z 2 咖( t ( 礼一 2 ，3 ；0 ，1 7 , 一6 ) ) 一x n - - 4 ( p 2 ) 一x o ( t ( r t 一2 ，3 ；0 ，佗一6 ) ) 则有：( t ( 几，4 ；1 ，0 ，n 一6 ) ) 一d z ( t ( n ，4 ；0 ，r , 一5 ，o ) ) = x n - - 4 ( 化) 一z 妒( s n 一3 ) 一z ( s n 一3 ) + x d p ( t ( n 一2 ，3 ；0 ，佗一6 ) ) = z n - - 4 0 堙) 一z 妒( s r i 一3 ) 一z ( 5 n 一3 ) + z ( 3 n 一3 ) 一咖( 5 n 一4 ) = x n - - 4 ( z 2 1 ) 一( s n 一4 ) 一z r f ( s n 一3 ) ， = z 几一2 一z n 一4 一( s n 一4 ) 一z 西( s n 一3 ) 即有咖( t ( n ，4 ；o ，n 一5 ，o ) ) 一咖( t ( n ，4 ；1 ，0 ，佗一6 ) ) = z ( 5 n 一3 ) - - x n 一2 + z n 一4 + ( s n 一4 ) 由引理3 1 2 ，而图8 n - 3 和一个孤立点为8 n - - 2 的真子图所以有e ( 烈n ，4 ；0 ，n - 5 ，o ) ) 一 e ( t ( n ，4 ；l ，0 ，竹一6 ) ) 0 贝0e ( z ( n ，4 ；0 ，礼一5 ，o ) ) - e ( t ( n ，4 ；1 ，0 ，他一6 ) ) 定理3 3 直径d = 4 时，t t ( n ，4 ；n - 5 ，0 ，o ) ，t ( n ，4 ；1 ，0 ，n - 6 ) ，t ( m 4 ；0 ，n - 5 ，o ) ， t ( n ，4 ；2 ，0 ，n 一7 ) 为唯一的第四小能量图； 证明我们用枚举的思想，直径为d = 4 的树t 竹4 要么为毛毛虫t ( n ，4 ；a ，b ，c ) ， 比如乃，噩，乃，要么在条直径最中间的个顶点上伸出若干个2 长的路，例如码， 但对于n 与死，乃与，根据引理3 5 ，3 6 ，3 7 ，3 8 得，e m ) e m ) e ( 乃) ，所以 我们只需比较，n 两个图的能量大小： 刁了一 1几一6 图死 刁k 1 几一7 12 图噩 图乃 z 杰 1 n 一6 图死 因为r e ( t o ，0 ) = l , m ( t 1 ，0 ) = 1 ；r e ( t o ，1 ) = 礼一l , m ( t l ，1 ) = n 一1 ；r e ( t o ，2 ) = 3 n 一 1 3 ，m ( 乃，2 ) = 4 n 一2 1 ；m ( t o ，3 ) = 扎一5 , r e ( t 1 ，3 ) = o ；若k 4 , r e ( t o ，后) = o , m ( t 1 ，k ) = o ； 又因为； 所以有： 即得： 一：2 z 0 + 。x - 2i n 誊以炉 9 ，+ e ( t o ) 2 妻上z 以1 1 1 【1 + ( n 一1 ) z 2 + ( 3 n 一1 3 ) z 4 + ( n 一5 ) z 6 】出 刀( 丑) = ：2f 0 + 。x _ 2i n 1 + ( n 一1 ) z 2 + ( 4 n - 2 1 ) z 4 】如 珊( n j f 。+ o o x - 2i n 业导害羟篇铲如 因为对一确定的z 0 ，令，( n ) 一1 - i - ( n l - + 1 ( ) n x 2 一- 1 1 - ) ( z s n ：+ - ( 1 4 3 n ) x 一4 2 - 1 l - ) ( 一n - - 5 ) x 6 ，我们有； m ) ，- 而鲁筹赫 。 所以，f ( n ) 为一个关于n 的严格递减函数，因此，对于所有的佗9 我们有 e ( t o ) 一e ( t 1 ) e ( t 9 ) 一e ( 巧) 0 ，令，( n ) = i l + + ( ( n