（运筹学与控制论专业论文）关于仙人掌图的点边独立指数的研究.pdf

o nt h ev e r t e x ( e d g e ) i n d e p e n d e n c ei n d e xo fc a c t i at h e s i ss u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：y ey | a l i s u p e r v i s o r ：p r o f l i uh u i q i n g h u b e iu n i v e r s i t y 、h a n c h i n a 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导帅的指导下独立进行研究所取得 的研究成果。除了文l j 特别加以标注引j t j 的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作6 占。对本文的研究做出重要贡献的个人和集 体，均已在文。 l 以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 作者签名： i 叶亚翻 签名日期：卅p 年箩月四日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供f 1 录检索与阅览服务；学 校可以允许采j j 影印、缩印、数字化或其它复制手段保存学位论文：在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 作者签名： 导师签名： 叶亚鞠 鼍冬衲 日期：l 口年岁月堪日 日期：肼乡月必日 罩 巾文摘要 摘要 仙人掌图是每一个块或者是圈或者是边的连通图树和单圈图都是仙人掌 图本文丰要研究仙人掌图的点独立指数和边独立指数，通过介绍。些新的移接 变形使得图的点独立指数和边独立指数严格单调，从而分别得到仙人掌图的点独 立指数和边独立指数的上、下界，并且刻画达到这些界时对应的极图对一些特 殊的仙人掌图，如单圈图，分别对其极大点独立指数和极小边独立指数进行排序； 如树，分别对其极小点独立指数和极大边独立指数进行排序从我们的结果巾可 以看出：在某个给定的图类中。一个图如果具有极大的点独立指数，它往往也具 有极小的边独立指数，反之亦然 全文共分为四章第一章首先介绍了图论的历史背景、基本概念和术语其 次，介绍了本文所要研究的问题第二章刻画了给定割边数的仙人掌图的极大点 独立指数和极小边独立指数及其对应极图第三章对给定同长的单圈图的极大 点独立指数和极小边独立指数进行排序并给出对应极图，本章的丰要结果发表 在m a t c hc o m m u n i c a t i o n si nm a t h e m a t i c a la n di nc o m p u t e rc h e m i s t r y5 9 ( 2 0 0 8 ) 第四章对树的极小点独立指数和极大边独立指数进行刻画并排序 最后，总结了本文研究的问题，并提出可进步研究的问题 关键词：仙人掌图；单圈图；树；点独立指数；边独立指数 湖北大学硕一 ：学位论文 a b s t r a c t ac a c t u si sac o n n e c t e dg r a p hw h o s ea l lo fb l o c k sa r ee i t h e re d g e so rc y c l e s t r e e s a n du n i c y c l eg r a p h sa r ec a c t i i nt h i st h e s i s ，w es t u d yt h ev e r t e xi n d e p e n d e n c ei n d e xa n d e d g ei n d e p e n d e n c ei n d e xo fc a c t i f i r s t ，w ei n t r o d u c es o m en e wo p e r a t i o n sw h i c hm a k e t h ev e r t e xi n d e p e n d e n c ei n d e xa n de d g ei n d e p e n d e n c ei n d e xo fc a c t is t r i c t l yi n c r e a s e o rd e c r e a s e ，a n dt h e no b t a i nt h eu p p e ra n dl o w e rb o u n da n dc h a r a c t e r i z ec o r r e s p o n d i n ge x t r e m a lg r a p h s a l s o ，w eo r d e rs p e c i a lc a c t iw i t hr e s p e c tt ov e r t e xi n d e p e n d e n c e i n d e xa n de d g ei n d e p e n d e n c ei n d e x ，s u c ha su n i c y c l eg r a p h sa n dt r e e s f r o mo u rr c s u i t s ，w ek n o wt h a tag r a p hw i t hm a x i m a lv e r t e xi n d e p e n d e n c ei n d e xh a sm i n i m a le d g e i n d e p e n d e n c ei n d e x ，a n dv i c ev e r s a t h i st h e s i sc o n s i s t so ff o u rc h a p t e r s c h a p t e r1 w ef i r s ti n t r o d u c eab r i e fb a c k - g r o u n do fg r a p ht h e o r y ，c o n c e p t sa n dn o t a t i o n s ，a n dt h e n ，w ep r e s e n tt h em a i nr e s u l t s o b t a i n e di nt h i st h e s i s c h a p t e r2 ，w ep r e s e n tau n i f i e da p p r o a c ht ot h ee x t r e m a lc a c t u s w i t hrc u t e d g e sf o rd i f f e r e n ti n d i c e sa n dc h a r a c t e r i z ec o r r e s p o n d i n ge x t r e m a lg r a p h s c h a p t e r3 ，w eg i v et h em a x i m a lv e r t e xi n d e p e n d e n c ei n d e xa n dt h em i n i m a le d g ei n d e p e n d e n c ei n d e xo fa l lu n i c y c l eg r a p h ss e ta n dc h a r a c t e r i z ec o r r e s p o n d i n ge x t r e m a l g r a p h s ，w h i c hi sp u b l i s h e di nm a t c h c o m m u n i c a t i o n si nm a t h e m a t i c a la n di nc o r n p u r e rc h e m i s t r y5 9 ( 2 0 0 8 ) c h a p t e r4 ，w eo r d e rt r e e sw i t hr e s p e c tt ov e r t e xi n d e p e n d e n c ei n d e xa n de d g ei n d e p e n d e n c ei n d e xa n dc h a r a c t e r i z ec o r r e s p o n d i n ge x t r e m a l g r a p h s f i n a l l y , c o n c l u s i o n sa n ds o m ep r o b l e m st ob es t u d i e df u r t h e ra l ep r o p o s e d k e yw o r d s ：c a c t u s ；u n i c y c l eg r a p h ；t r e e ；v e r t e xi n d e p e n d e n c ei n d e x ；e d g ei n d e p e n d e n c ei n d e x i i 目录 目录 第一章绪论 1 1 1 研究背景及现状 1 1 2 图的基本概念 2 1 3 本文研究的问题 3 第二章仙人掌图的点( 边) 独立指数 5 2 1 引言 5 2 2 图的移接变形 6 2 3 给定割边数的仙人掌图的极大点( 极小边) 独立指数的排序1 2 第三章单圈图的点( 边) 独立指数1 6 3 1 引言1 6 3 2 给定圃长的单圈图的极大点( 极小边) 独立指数的排序1 9 第四章树的点( 边) 独立指数2 3 4 1 引言2 3 4 2 树的极小点( 极大边) 独立指数的排序3 0 总结与展望3 2 参考文献3 3 附录3 8 致谢3 9 1 1 1 第章绪论 第一章绪论 本章首先简要介绍图论的历史，基本概念和术语，然后介绍本文研究的问题 及主要结果 1 1 研究背景及现状 图论是一门内容丰富且应用广泛的数学分支，它以图为研究对象自- | 八世 纪以米，无论是理论还是应川都得到了空前的发展，也是近年来离散数学和组合 数学领域最活跃的研究方向之一 关于图论的文字记载最早出现在欧拉1 7 3 6 年的论著l f l 图论起源于著名的 哥德斯堡七桥i 、廿j 题十九世纪中叶到二十世纪中叶。出现了一些著名的图论问 题，如四色问题，h a m i l t o n 问题等，同时图的应l j 研究也迅速发展，如川图论米研 究有机化合物的分子结构问题，研究电流网络l 、口j 题等及后来出现的m e n g e r 定理， r a m s e y 定理等这些成果大大推动了图论的发展 二 世纪中叶以后，图论的研究发展很快，形成数学科学| f l 一门独立的分支， 并形成了许多研究方向，如超幽理论、极值图论、算法图论、网络图论、随机图 论等由于牛产管理、军事、交通运输、计算机科学、通讯网络等实际l 廿j 题的需 要，如应川图论米研究最小运输费川i 口j 题等，加上计算机技术的迅猛发展，为图论 研究提供了有力的支持，图论及其应用的研究得以更加迅速的发展 图论巾的图代表很多含义，冈此图论有很多方面的麻川例如，如果。个简 单尢向图g = ( ve ) 的每个顶点代表分子t 的，个原子，每条边代表原子之间 形成的化学键，这种图就叫分子图分子拓扑指数以及分子图的不变量的研究 是现代化学图论巾最活跃的研究领域之一它们能够被川米描述有机化合物的 物理化学特性尤其是药理特性自从1 9 4 7 年h w i e n e r 提出第个分子拓扑指数 即w i e n e 对旨数以来，数百利- 分子拓扑指数，包括r a n d i d 指数以及广义r a n d i d 指数， m e r r i f i e l d s i m m o n s 指数( 即点独立指数) ，h o s o y a 指数( 即边独立指数) ，在数学和化 学文献中被研究 图的点独立指数和边独立指数得到了广泛的研究人们在对给定图类的极大 及极小点独立指数研究中发现，在给定的图类中，边独立指数和点独立指数具有 很好的相关性：当图的边独立指数取极大时，对应的点独立指数取极小将其应 用到化学分子图研究中，其中。个方向是研究给定图类的点独立指数和边独立指 数的极值及大小排序 湖北大学硕十学位论文 在给定的图类中，找出某种指数的上、下界及这些界可达时对应的极图是图 论t ，个重要的研究方向近年，许多人对图的点独立指数和边独立指数进行了 研究和刻画，并得到许多结论在n 个顶点的树巾，点独立指数极大和极小( 或边独 立指数极小和极大) 的图分别是星图& 和路r 李学良等人和潘向峰等分别给出 了给定点数( 或直径) 的树的具有极大点独立指数和极小边独立指数的图( 注意到 这两个极图是同构的) 刘慧清等人在文献【3 l 】r f - 对直径为d 的树的点独立指数和 边独立指数分别按从大到小和从小剑大的顺序进行了排列欧建平【3 3 研究了给 定同长的单圈图的边独立指数的下界余爱梅和吕雪征在【3 7 】r l i 给出了含k 个悬 挂点的n 阶树的边独立指数的下界及点独立指数的上界刘慧清和陆玫在【2 9 】i l ， 刻画了给定幽数的仙人掌图。| i 具有极大点独立指数和极小边独立指数的图 1 2 图的基本概念 本文i f l ，图论的基本概念和术语主要米t ! l b o n d y 和m u r t y l j 勺专著【2 】，其它未说 明的概念，术语可以参考文献【2 】 本文仅考虑有限的简单无向图设图g = ( ke ) 是，个简单无向图， x y ( g ) 点x 的邻点集，记为g ( z ) 或( z ) ，定义为图gr l 一与z 相邻的顶点集合 ， i 、i - ：z 的度，记为d a ( z ) 或( f ( z ) ，定义为图g t l 与z 关联的边的数n 图g 【i l 度为1 的顶 点称为g 的悬挂点，与g 的悬挂点关联的边称为g 的悬挂边图g i l - 两顶点z 和y 之 问的最短路的长度称为x ，可两点问的距离，记为d g ( z ，剪) ，或简记为d ( x ，y ) 设只= u o v l 是图g - i 的。4 条路，其r f l d ( v 1 ) = d ( v 2 ) = = d ( v 。一1 ) = 2 ( 除 非s = 1 ) ，若d ( v o ) ，d ( v 。) 3 ，则只被称为g 的一条内部链；若d ( v o ) = l j 呈d ( v 。) 3 ， 则只被称为丁的条悬挂链图g r t l 最短圈的长称为g 的同长设v 7cv ， 记g y 7 为图g 去掉y 7r f i 的顶点及与y r l 的顶点关联的边后得到的图g i v 可 简记为g v 设e 7ce ，g e 7 表示图g 去掉e 7 中的边后得到的图添加条连 接图g 中不相邻的两点z ，可的边得到的图记为g + z 可 无圈的连通图称为树边数等于顶点数的简单连通幽称为单圈图设丁是一 棵树，如果树t f f 存在唯+ 一的一。点乱y ( 丁) 满足d ( u ) = k 3 ，那么我们称t 是一 棵k 一树 设g 是一个图，v + cv ( c ) h _ l v + i = k ，e + ce ( g ) 且i e + i = z 若y 巾任意两 个顶点均不相邻，则称y + 为g 的k 点独立集：若矿巾任意两条边均不相邻，则 称e + 为g 的k 边独立集 下面定义几个图g 的拓扑指数 2 第章绪论 ( i ) 图g 的点独立指数定义为 i ( g ) = i ( g ；七) ， _ | c o z ( g ；七) 是图g 巾七一独立集的个数且i ( g ；0 ) = 1 ( i i ) 图g 的边独立指数定义为 z ( g ) = z ( g ；七) ， k o 名( g ；克) 是图gl | 尼- 边独立集的个数且名( g ；0 ) = 1 ( i i i ) 图g 的w i e n e r 指数定义为 ( g ) = d a ( u ，钉) ， u 即对图g q 所有顶点对的距离求和 ( i v ) 图g 的谱半径p ( g ) ，是图g 的邻接矩阵a ( g ) 的最大的特征值若g 连通， 贝i j a ( g ) 是不可约的，且i 主t p e r r o n f r o b e n i u s 定理，谱半径有唯+ 的正定特征向量， 称这个向量为图g 的p e r r o n 向量若连接图g r l , 两个不相邻的顶点，则谱半径增加 ( v ) 图g 的第。型z a g r e b 指数【1 3 】，第一型广义z a g r e b 指数 2 4 1 分别定义为 尬( g ) = d a ( u ) 2 ， u e v ( a ) 岬( g ) = d a ( u ) q u e v ( a ) f i b o n a c c i 数r 定义如下：f 0 = f 1 = 1 ，r = r 一1 + r 一2 ，n 2 ，b = r b l + 只一1 b 一扣1 易证z ( r ) = f n + i ，z ( p n ) = r 1 3 本文研究的问题 仙人掌图是每个块或者是圈或者是边的连通图树和单圈图都是仙人掌 图本文主要研究仙人掌图的点独立指数和边独立指数，通过介绍一些新的移接 变形使得图的点独立指数和边独立指数严格单调，从而分别得n l , 1 1 人掌图的点独 立指数和边独立指数的上、下界，并且刻画达到这些界时对戍的极图对一些特 殊的仙人掌图，如单圈图，分别对其极大点独立指数和极小边独立指数进行排序； 3 湖北大学硕十学位论文 如树，分别对其极小点独立指数和极大边独立指数进行排序从我们的结果巾可 以看出：在某个给定的图类中，。个图如果具有极大的点独立指数，它往律也具 有极小的边独立指数，反之亦然 首先，我们在第二章巾刻画了给定割边数的仙人掌图的点( 边) 独立指数，证 明g o ( n ，7 ) 是q ( n ，r ) m 1 1 ) t 1 具有极大的点独立指数，极小的边独立指数，极小 的w i e n e r 指数，极大的谱半径，极大的第一型广义z a g r e b 指数的图第三章刻画了 单圈图的点( 边) 独立指数，给出甲圈图集合4 m ( 6 g 7 , 一8 ) r | i 前igj + 1 个极大 点独立指数和后igi + 2 个极小边独立指数；且当夕= n 一2 时，给出前igj + 2 个极 大点独立指数和后igi + 2 个极小边独立指数第四章刻画了树的点( 边) 独立指数， 给出集合咒( n 8 ) 。i l 后孚 一1 个极小的点独立指数和前孚 个极大的边独 立指数及其) c 寸应的极幽最后，我们总结了本文研究的问题及得到的结果，并提出 可进。步研究的问题 4 第二章仙人掌图的点( 边) 独立指数 第二章仙人掌图的点( 边) 独立指数 仙人掌图是每，个块或者是圈或者是边的连通图令9 ( n ，7 ) 是所有礼个顶 点和7 条割边的仙人掌图的集合本章将给出在g ( n ，r ) ( n 1 1 ) 中，仙人掌图的极 大点独立指数，极小边独立指数，极d x w i e n e r 指数，极大谱半径和极大第一。型广 义z a g r e b 指数，并刻画达到这些界时对应的极图 设图g g ( n ，7 ) 若7 = 亿一1 ，则图g 是一棵树因此我们假设r n 一3 设g ( n ，r ) 是所有有n 个顶点和r 扎一3 条割边的仙人掌图的集合显然，9 ( 扎，n 一 3 ) 是围长为3 的单圈图的集合我们将要证明g o ( 死，r ) 是9 ( 礼，r ) m 1 1 ) q 具有极 大的点独立指数，极小的边独立指数，极小的w i e n e r 指数，极大的谱半径，极大的 第一型广义z a g r e b 指数的图在文献【2 9 1 q - ，刘慧清和陆玫对固定圈数的仙人掌 图做了刻画，给出求具有极大点独立指数，极小边独立指数，极d , w i e n e r 指数，极 大谱半径的极图的统一。的方法 下面定义个特殊的仙人掌图g o ( 竹，r ) 当n r 一1 是偶数时，g o ( 礼，7 ) 是在 星图& 的悬挂点之问连接下n - r - 1 条独立边得到的图( 见图2 1 ( a ) ) 当t , 一7 一l 是奇 数时，g o ( 礼，r ) 是在星图& 一1 的悬挂点之问连接下n - r - 2 条独立边，且细分其t l j 条 独立边得到的图( 见图2 1 ( b ) ) ，i r 一4 2 ，、- 、 畛刘矽 、- - _ 一， r ( a ) n 一7 一1 是偶数 2 1 引言 图2 1 极图g o ( n ，r ) 、一 r ( b ) 佗一r 一1 是奇数 引理2 1 1 ( 见 1 2 1 ) 设图g = ( k e ) ，v y ( g ) 则 ( i ) i ( g ) = i ( c v ) + i ( g 一g p 】) ； ( i i ) z ( c ) = z ( a v ) + z ( c u ， ) ) ； t k ( u ) ( i i i ) 如果图g 1 ，g 2 ，g u 是图g 的分支，贝j l i ( g ) = n 名1i ( g i ) r z ( g ) = 丌嘉。z ( q ) 5 湖北大学硕十学位论文 由引理2 1 1 ，若v 是图g 的顶点，则i ( g ) t ( g 一口) 若图g l j 至少有。条边， n z ( c ) z ( g u ) 引理2 1 2 ( 见【4 1 1 ) 设图g 是一个连通图，i t ，v y ( g ) 若v l ，7 3 2 ，u 。 n ( v ) ( 让) ( 1 s d c ( v ) ) j 呈x = ( x v ) 是a ( g ) 的p e n d n 向量设图g 去掉边伽i ， 添加边u v i ，1 i s ，得到的图记为g + 若z u ，则 p ( c ) i ( g ) 或 i ( g ；) z ( g ) ； ( i i ) ( 见【3 0 )z ( c 1 ) z ( g ) 或 z ( g ；) z ( g ) ； ( i i i ) ( 见【3 0 )( g ：) p ( g ) ； ( v )聊( g ；) 岬( g )或岬( g ；) m f ( g ) 当q 1 证明：( v ) 由定义， m f ( c 1 ) 一聊( g ) = d g ：( ) a 一d a ( u ) 口 t i y ( g ：) v e v ( g ) = d v i ( v ) 口士d g * l ( u ) q d e ( v ) n d a ( u ) a = ( d g ( v ) + t ) 。+ ( d a ( ) 一) 口一d g ( u ) q d g ( u ) n = q ( 管一卯一1 ) ， 其l p d g ( u ) 一t 叩1 d e ( u ) ，d a ( u ) 1 时，m l ( g 1 ) m f ( g ) 若叱u ) d a ( u ) ，同理当a 1 时， 聊( g ；) 聊( g ) 证毕 一 定义西= 善：耋：茎妻 设图g 阶为n 7 ，是由连通图日7 在顶点乱处连接图g q 2 ) 和圈q ( q 5 ) 得 到的( 见图2 3 ) 当f = 2 ，3 时，h 7 p 1 设g = u u l u 2 u q _ 1 u 如果图g 7 是由 图g 去掉一条边u 2 u 3 ，增加两条边u u 2 ，u u 3 得到的，则称图g 7 是图g 经过o p e r a t i o n b + 得到的 o p e r a t i o n b + - 一 g 图2 3 接下来证明o p e r a t i o nb + 使得下列指数严格变大或变小 引理2 2 2 如果图g 是由图g 经过o p e r a t i o nb + 得到的则 ( i )i ( c 7 ) i ( g ) ； 7 湖北大学硕十学位论文 ( i i ) ( i i i ) ( i v ) ( v ) z ( c 7 ) m f ( g ) 当q 1 证明：令h = h ua ，i y ( h ) i = h + 1 ( i ) 由引理2 1 1 ，得 则 i ( g ) z ( g 7 ) e l f q i ( h 7 一u ) + 局一2 日一2 i ( h 7 一n h 似】) ， & f t 日一2 i ( h 7 一u ) + 只一2 日一a i ( h 7 一n h ，【u 】) i ( g ) 一i ( a ) = ( i i ) 由引理2 1 1 ，得 则 z ( a ) z ( a 7 ) 日日一4 i ( h 7 一u ) 一只一2 一a i ( h 7 一n h ，陋】) 只一4 一e l 一2 一3 = f z 一1 疋一4 一e l 一2 局一5 0 z ( g 一饥) + z ( g 一乱一“7 ) u c n a ( u ) ( 日一l + 2 日一2 ) z ( 日一“) + 局一1z ( s 一乱一u ，) t 1 7 n h ( t ) z ( a 7 一u ) + 二z ( a 7 一让一让7 ) t 7 v g ，( u ) = 4 b 一2 z ( 日一u ) + 2 局一3 z ( h u 一乱，) u 7 e n n ( u 、 z ( a 7 ) 一z ( a ) 铀z ( h - u ) - 徊一 一日一4 z ( h 7 一u 一札7 ) 。； 如果q 5 且q 是奇数，则 w ( a ) 一w ( c ) = 2 ( ) + 掣一蛀等幽一2 ( q - 3 + 毕) ：h ( q - 3 ) + 生掣 o ( i v ) 设z = ( ) 是a ( g ) 的p e r r o n量，对应顶点 y ( g ) 设( 乱) = w l ，妣 令 一+ jg u2u3+u2u，兰iz u z 牡3 ， ig u u l 一i t w l 一一叫+ u 3 u l + u 3 w l + + u 3 w t ，当z t z u 3 ； 由引n 2 1 2 ，p ( a + ) p ( g ) 由于g + 兰g 7 一u u 3 ，冈此p ( a 7 ) p ( g + ) p ( g ) ( v ) 由第一型广义z a g r e m 旨数的定义，可得 岬( g ) 一聊( g ) = d a 和) 口一d g ( u ) n = 始如) q d a ( u ) a 口y ( g 7 )v e v ( a ) = ( d a ( u ) + 2 ) o d a ( u ) q 0 证毕 设连通图日，u v ( h ，) 在顶点u 上连接圈西和两个长为4 的n c l ，c 2 得 到的图记为g ，g 的阶为n 9 ( 见图2 4 ) 设c 1 = u u l u 2 i t 3 u ，c 2 = l l b v l v 2 v 3 u 图g 去掉边u 2 u 3 ，v l v 2 ，连接边u u 2 ， u v 2 ，v l u 3 得到的图记为口，则称图驴是图g 经 过o p e r a t i o nc + 得到的 9 湖北大学硕十学位论文 g 一 图2 4 u 2 u 3 y l ? j 2 同理可以证明经过o p e r a t i o nc + ，使得- v n 指数严格变大或变小 引理2 23 设图g 经过o p e r a t i o nc + 得到的图为g + 则 ( i ) ( i i ) ( i i i ) ( i v ) ( v ) i ( g + ) z ( g ) ； z ( c + ) 聊( g ) 当“ 1 证明：令h = h 7ua ，l y ( 日) i = h + 1 ( i ) 由引理2 1 1 ，得 i ( c ) = 2 5 f t i ( h 7 一u ) + 4 f t 一2 i ( h 一日舡】) ， i ( c + ) = 2 7 f t i ( h 7 一u ) + f t 一2 i ( h 7 一n h ，【“】) 贝j j i ( g + ) 一i ( c ) = 2 f t i ( h 7 一u ) 一3 f t 一2 i ( h 7 一0 ，【乱】) 2 e 一3 只一2 0 ( i i ) 由引理2 1 1 ，得 z ( c ) = 3 3 z ( h 一乱) + 9 z ( h u 一钆，) u h ( u ) z ( c + ) = 3 2 z ( h u ) + 8 z ( h 一钆一乱，) u 7 h ( t ) 贝j j z ( c + ) 一z ( g ) = 一z ( g u ) 一u ，妇( u ) z ( h 一让一u 7 ) j 9 ( g ) 同样地，当z u z ”。时，g ”= g 一口1 钝+ 删2 ；当z u z u ，时， g = g ，一u u lu u 2 一札u 3 - - u w l 一一u w t + 1 z 正1 + 口1 乱2 + l u 3 + 口1 w 1 + + u 1 w t 则由6 1 坪2 1 2 ，p ( a ) p ( g 7 ) 又g 笺g 7 一u 3 钉l ，冈此，) ( g ) p ( g 7 7 ) p ( c 7 ) p ( g ) ( v ) 由定义知 朋甲( g ) 一a 矸( g ) = d g ( 牡) 口一d g ( u ) n = ( d au ) + 2 ) a d a ( 钍) n 0 证毕 引理2 2 4 当几一r 一1 是奇数时， ( i ) i ( g on ，r ) ) = 5 2 r 3 竖乒+ 2 ； ( i i ) z ( a on ，r ) ) = ( 3 n + 3 r + 2 ) 2 譬产； ( i i i ) w ( a o ( 礼，r ) ) = 2 n 2 r - 3 n + r - 4 ， 一 ( i v ) p ( c o ( 扎，r ) ) 是方程z 6 一( 扎+ 1 ) z 4 一( 礼一7 一4 ) z 3 + ( 2 n + r 一4 ) x 2 + 2 ( n r 一4 ) x 一2 r = o 的根： ( v ) a 卵( g o ( n ，7 ) ) = ( 佗一2 ) 。+ 2 。( 佗一7 一1 ) + 7 证明：由引理2 1 1 ，可得 i ( g o ( n ，r ) ) =i ( g o ( 佗，r ) 一u ) + i ( a on ，7 ) 一n a o ( n , r ) 心】) = 5 2 7 3 半+ 2 ， z ( c 。n ，r ) ) = z ( c o ( 他，r ) 一) + z ( c o ( 扎，7 ) 一u u 7 ) u “7 e = 3 2 字十3 r 2 字+ 3 ( n r 一4 ) 2 甲一1 + 2 2 字+ 1 = ( 3 佗+ 3 r + 2 ) 2 甲 因此( i ) 和( i i ) 成立 1 1 湖北大学硕十学位论文 已知w ( & ) = ( n 一1 ) 2 ，则 w ( a 。( 几，r ) ) = ( n - - 2 ) 2 一兰二+ 2 + 2 + 3 ( n 一4 ) = 翌至二 从而证明( i i i ) 成立 由引理2 1 3 ，( g on ，r ) ；z ) = x r ( z 2 1 ) 字【x 6 一( 礼+ 1 ) z 4 一( n r 一4 ) x a + ( 2 n + 7 一4 ) x 2 + 2 ( n r 一4 ) x 一2 7 】由于p ( g o ( 仃，r ) ) 1 ，冈此p ( g o ( 佗，r ) ) 是方 程z 6 一( 佗+ 1 ) x 4 一( n r 一4 ) z 3 + ( 2 n + r 4 ) z 2 + 2 ( n 一7 一4 ) z 一2 r = 0 的根 ( i v ) 成立 计算得朋甲( g o ( n ，7 ) ) = ( n 一2 ) 口+ 2 口n r 一1 ) + r 证毕一 引理2 2 5 当n 一7 一1 是偶数时， ( i ) t ( g on ，7 ) ) = 2 7 3 二孚+ 1 ； ( i i ) z ( c o ( n ，7 ) ) = ( n + r + 1 ) 21 宇； ( i i i ) w ( a o ( n ，7 ) ) = 2 n 2 _ - 5 j n _ + r 一+ 3 ， ( i v ) p ( g ) 是方程z 4 一n x 2 一( n 一7 一1 ) x + r = 0 的根； ( v ) 尬( g o ( n ，7 ) ) = ( n 一1 ) 。+ 2 。n r 一1 ) + 7 证明：证明同引理2 2 4 的证明类似，故略 2 3 给定割边数的仙人掌图的极大点( 极小边) 独立指数的排序 设c ( a l ，a k ；7 ) 是将k 个圈g 。( 1 i k ) $ n r 条边均取一个顶点重合在一 起得到的图设c o ( 几，7 ) = c ( a l ，a k ；7 ) ：a i 3 ，1 i k ，仁k1 ( o i 一1 ) + 7 + 1 = n ) 则c o ( n ，r ) 夕( 佗，7 ) ， l c ( 3 ，3 ；r ) ，当n 一7 一l 是偶数， l x g 0 ，r 卜1 i 2 j 3 ；吐当n - r - 1 是奇数 【专n - r ；- - 4 设f ( g ) z ( g ) ，p ( g ) ，- z ( a ) ，一w ( g ) ， 卵( g ) ( n 1 ) ) 引理2 3 1 若几1 1 ，贝j j f ( g ) f ( g o ( n ，o ) ) 证明：励n i ( g ) = z ( g ) = r + r 一2 且g g ( n ，o ) 由引理2 2 4 、2 2 5 ，只 第二章仙人掌图的点( 边) 独立指数 需证明 ( 佗+ 1 ) 2 警 r + r 一2 3 孚+ 1 ， 礼一1 是偶数 ( 3 几+ 2 ) 2 学 r + r 一2 ( 3 n 一4 ) 2 学+ ( 3 n 一1 0 ) 2 学 ( 3 凡一4 ) 2 字+ 2 4 2 鼍产= ( 3 n + 2 ) 2 学 已知w ( g ) =掌n 1 1 彗竺骜，冈此由引理2 2 4 和 当礼1 2 是奇数 引理2 2 5 ，当n 1 1 时，w ( g ) w ( c o ( 凡，o ) ) 当n 1 1 时，p ( a o ( n ，o ) ) 再巧 3 ，因此p ( g ) p ( c o ( n ，o ) ) 当n 1 1 时， 聊c 啦们n 协矧嚣篁嚣黝；：篓慧 证毕 一 弓i 理2 3 2 若n 9 ，贝u ( i ) i ( c ( n l ；1 ) ) w ( c ( n 一 4 ，3 ，3 ；0 ) ) ； ( i v ) p ( c ( n l ；1 ) ) p ( c ( n 一3 ，3 ；1 ) ) ，p ( c ( n 一3 ，3 ；o ) ) p ( c ( n 一4 ，3 ，3 ；o ) ) ； ( v ) a 卵( c ( n 一1 ；1 ) ) 1 u ，钉v c 且图日是图g 的一个分支，包 含顶点让，秒，g ( “) 蜥( u ) g ，g ( ) ( u ) 1 2 i 设g ( 仳) ( u ) = u 1 ，u 2 ，u t ) ，n a ( v ) ( ) = l ，眈，】 则s ，t 1 令g ：= g 一 u u l ，讹t + u u l ，v u t ，g ；= g 一 v v l ，u u 8 ) + u 2 j 1 ，u u 。 则g ；，g ；9 ( n ，r ) 9 k 而由弓i n 2 2 1 得，( g ：) 厂( g ) 或厂( g ；) ，( g ) ，矛盾冈 此假设不成立，i k i = 1 - 由论断l ，设g = c ( a l ，a k ；r ) ，其i i n l n 2 n 七3 ，设u 是g 的唯 一害0 点，扎仳1 ， l i e u ，是害0 边 选择满足( 木) 式，使得尼尽可能大的图g 则由引卿2 3 2 ，可设g 笋c ( n 一 1 ；1 ) 且g c ( n 一3 ，3 ；0 ) 论断2 0 1 4 论断2 的证明：假设0 1 5 令g 1 = t t u l u q i - - 1 乱，h = u ：2