（基础数学专业论文）图依谱矩的排序.pdf

图依谱矩的排序 摘要 设g = ( ke ) 是一个n 阶简单连通图，y ( g ) 和e ( g ) 分别为g 的顶点 集和边集a 。a 。入n 是g 的特征值，则g 的所有特征值的七次幂 n 之和s 知= 称为图g 的七阶谱矩谱矩序列s 产( s o ，s l ，i s 。) 是图g i = l 的一个有限不变量序列 本文利用图的变换研究了任意图的零到四阶谱矩的变化，并依所得 结论主要研究了树、单圈图和双圈图依其谱矩序列s 。的字典序的排列，分 别给出了树、单圈图和双圈图依s 4 字典序排在前三位和后三位的图及其 特征 关键词：特征值，谱矩，树，单圈图，双圈图 高校教师在职硕士学位论文 a bs t r a c t l e tg = ( v e ) b eas i m p l ea i l dc o n n e c t e dg r 印h ，谢t ht h ev e r t 既跎ty ( g ) a n d t h ee d g es e te ( g ) a 1 a 2 入n 踟呛t h ee i g e n v a l u e si nn o n i n c r e a s i n go r d e r n o fag r a p hg t h en u m b e r a ( 七= o ，1 ，2 ) i sc a l l e dt h ek - t hs p e c t r 甜m o m e n to f l = l g ，d e n o t e db y 瓯t h es e q u e n c eb = ( s l ( g ) ，s 2 ( g ) ，s 七( g ) ) o fs p e c t r a lm o m e n t s i 8a 丘n i t es e ( 1 u e n c eo fi n v a r i a i l t so fag r a p hg i nt h i sp a p e r ，w es t u d yt h e 、，a 岍a t i o n s0 ft h es p e c t r a lm o m e n t sb yl l s i n gt r a n s f o r m a t i o n s ，a n do b t a j nt h el e ) 【i c o g r 印h i c 出o r d e ro ft r e 豁，u n i c y c l i cg r a p h sa n db i c y c l i c g r a p h 8w i t ht h es e q u e n c es 4 t h ef i r 8 tt h r e ea n dt h el a s tt h r e et r e 豁、u n i c y c l i c g r 印h sa n db i c y c l i cg r 印h s 丽t hr e s p e c tt ot h es e q u e n c es 4a r ec h a r a u c t e r i z e d k e yw o r d s ：e i g e n v a l u e ，s p e c t r a lm o m e n t ，t r e e ，u n i c y c l i cg r a p h ，b i c y c l i cg r a p h i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本 声明的法律结果由本人承担 学位论文作者签名多删穗乏日期：蝴月相 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留，使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本 人授权湖南师范大学可以将学位论文的全部或部分内容编人有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 ，保密口，在 年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打“ ”) 作者签名：潮狂 日期：刃噼j 嗍 导师签名： 习) 胺乏日期：夕窖年f 明日 图依谱矩的排序 第一章引言 1 1 研究背景 图论是一门应用广泛、内容丰富且较为活跃的数学分支，它起源于 瑞士数学家欧拉1 7 3 6 年解决的著名的。哥尼斯堡七桥问题”后来基尔 霍夫( k i r c h h o 丘) 在1 8 4 7 年运用图论解决了电路理论中求解联立方程的问 题，他引入了“树”的概念，可惜的是他的发展超越了时代而长期未被重 视。1 8 5 7 年凯莱( c a y l e ) r ) 非常自然的在有机化学领域里发现了一族重要 的称为树的图，它应用树来计算饱和烃g 飓。+ 。的同分异构体的数目 代数图论是代数与图论交叉的一个数学分支，它主要通过建立组合 结构的代数表示，应用代数理论来研究组合结构的拓扑性质，他和群论、 矩阵论等密切联系，在物理学，化学，生物学，经济学和通讯等领域中有 着重要的作用 图的邻接矩阵的特征值是代数图论关注的一个重要概念称n 阶图 g 的n 个特征值入l ( g ) ，a 2 ( g ) ，入n ( g ) 在入l a 2 入n 的情况下为图 g 的谱图的谱理论是图论的一个新兴领域，它起源于理论化学家和物 理学家为寻求一类偏微分方程的近似解而建立起的一套离散方法，它研 究的主要途径是通过图的矩阵表示，建立图的图谱结构和图的矩阵表示 的置换相似不变量之间的联系关于图谱的研究直到二十世纪中叶才逐 渐出现在文献中图谱理论虽然出现的时间比较晚，但经过短短几十年 的发展，图谱理论已经形成一个系统的、综合性的理论分支，其研究结果 在量子化学、物理、计算机、通讯网络以及信息科学中均有广泛应用 由于图谱应用的广泛性，很多学者都在致力于这方面的研究。目前 1 高校教师在职硕士学位论文 在图谱理论的研究和图的结构之间的关系、估计图的特征值、图谱和图的 各种不变量之间的关系几个方面研究较多。其中d m c v e t k 嘶c 【1 ，6 ，1 4 1 等 著的s p e c t r a lo fg r 印h st h e o 珂a n da p p l i c a t i o n 较为著名，且其新作r 胱e n t r e s u l ti nt h et h e o 巧o fg r a p hs p e c t r a l 等已经形成相当成熟的理论，国内外还 有大批学者【2 ，9 ，1 5 ，1 9 】，j r a d a 张福基等对图的谱理论研究也有出色贡献 在图的同构问题研究中，人们一直试图寻找图的全系不变量，因为 图的全系不变量在同构关系下唯一决定图起初，人们猜想图的邻接谱 是图的一个全系不变量，然而事实上，图的邻接谱并不能唯一决定图，文 献【1 】中d m c v e t l 洲c 和p r 0 w l i n s o n 就给出了三个具有不同度序列的同 谱图。尽管如此，人们仍希望利用图的邻接谱及它的特征值技巧，来建立 图的代数不变量与图本身的不变量之间的联系并刻画图的结构性质图的 谱矩序列就是其中一个很重要的不变量文献【1 】首先给出了图的前四阶 谱矩的计算公式，并刻画了树和给定圈长的单圈图依谱序列排列的最先 和最后的图的特征此外，k h a d i l 【a r 【7 】等得到了多烯( p o l y a u c e n e s ) 的谱矩的 一般表达式，g u t m a n 【1 6 ，2 0 】等给出了聚合物图( p o l y m e rg r 印h ) 的谱矩，z h 铋g 和b a l a s u b r a m a n i a n 利用谱矩导出了格图( s q u a r el a t t i c eg r 印h ) 的特征多项 式m a r k a 、r i c 3 ，4 ，1 1 ，1 2 】和s t a j k 0 、r i c 2 】研究了苯撑( p h e n y l e n e s ) 的前十阶谱矩， 在许多文献 5 ，1 0 ，1 7 】中，谱矩用来研究分子结构和估计分子的能量等 本文主要研究了树、单圈图和双圈图依其谱矩序列s 。的字典序排列， 利用图的变换分别给出了树、单圈图和三种形式的双圈图依谱矩序列s 。 的字典序排在前三位和后三位的图及其特征 文中有关的图论术语请参考文献【8 ，1 3 】，本文所讨论的图都是简单连 通图。 一2 图依谱矩的排序 1 2 本文主要结论 在文献【1 】的基础上，本文引入了五种图的变换，并且探讨了这几个变 换对任意图的谱矩的影响利用这些变换本文研究了树、单圈图和双圈图 的前四阶谱矩并依s 。的字典序给出排在前三位和后三位的图及其特征 主要结果如下： i 在所有n 阶树中，依s 4 的字典序 ( i ) 排在第一位的是n 阶路孤； ( i i ) 排在第二位的是度序列为( 1 ，1 ，1 ，2 ，2 ，3 ) 的n 阶树； ( i i i ) 排在第三位的是度序列为( 1 ，1 ，l ，l ，2 ，2 ，3 ，3 ) 的n 阶树； ( i v ) 排在最后一位的是珏阶星图 一。； ( v ) 排在倒数第二位的是n 阶树丑。) ( 见图3 - 1 ) ； 似) 排在倒数第三位的是扎阶树丑3 ) ( 见图孓2 ) ； i i 在所有礼阶圈长为p 单圈图中，依s 4 的字典序 ( i ) 排在第一位的是职，p ( 见图垂1 ) ； ( i i ) 排在第二位的是其中度序列为( 1 ，l ，2 ，2 ，3 ，3 ) 的圈图( 见图垂2 ) ； ( i i i ) 排在第三位的是其中度序列为( 1 ，l ，l ，2 ，2 ，3 ，3 ，3 ) 的图( 见图垂 3 ) ； ( i v ) 排在最后一位的是矾( 见图垂4 ) ； ( v ) 排在倒数第二位的是其中度序列为( 1 ，l ，2 ，2 ，3 ，n p + 1 ) 的 图( 见图缸5 ) ； ( 、r i ) 排在倒数第三位的是以嚣( 图垂6 ) ； i i i 在所有两个圈c g 和勺只有一个公共点的n 阶双圈图厶，g ) 中， 依s 。的字典序 ( i ) 排在第一位的是其中度序列为( 1 ，2 ，2 ，3 ，4 ) 的图( 见图5 1 ) ； 高校教师在职硕士学位论文 ( i i ) 排在第二位的是其中度序列为( 1 ，l ，2 ，2 ，3 ，3 ，4 ) 的图( 见图5 - 2 ) ； ( i i i ) 排在第三位的是其中度序列为( 1 ，l ，l ，2 ，2 ，3 ，3 ，3 ，4 ) 的图； ( i v ) 排在最后一位的是砖( p ，g ) ( 见图5 - 3 ) ； ( v ) 排在倒数第二位的是其中度序列为( 1 ，l ，2 ，2 ，3 ，n 一+ 口一 1 ) + 3 ) 的图； ( v i ) 排在倒数第三位的是月9 ( p ，q ) ( 见图5 - 4 ) ； i v 在所有两个圈勺和勺有m 个公共点的n 阶双圈图风，m ，口) 中， 依s 4 的字典序 ( i ) 排在第一位的是其中度序列为( 1 ，2 ，2 ，3 ，3 ，3 ) 的图( 见图5 - 5 ) ； ( i i ) 排在第二位的是其中度序列为( 1 ，l ，2 ，2 ，3 ，3 ，3 ，3 ) 或( 1 ，2 ，2 ， 3 ，4 ) 的图； ( i i i ) 排在第三位的是其中度序列为( 1 ，l ，1 ，2 ，2 ，3 ，3 ，3 ，3 ，1 ) 或( 1 ，l ， 2 ，2 ，3 ，3 ，4 ) 的图； ( i v ) 排在最后一位的是觥l ( p ，q ) ( 图5 - 6 ) ； ( v ) 排在倒数第二位的是其中度序列为啦p ，g ) ( 图5 7 ) ； ( 讥) 排在倒数第三位的是嗽( 弘鼋) ( 图5 8 ) ； v 在所有两个圈白和勺不相交的n 阶双圈图g ，口) 中，依的字 典序 ( i ) 排在第一位的是其中度序列为( 1 ，2 ，2 ，3 ，3 ，3 ) 的图； ( i i ) 排在第二位的是其中度序列为( 1 ，l ，2 ，2 ，3 ，3 ，3 ，3 ) 或( 1 ，2 ，2 ， 3 ，4 ) 的图； ( i i i ) 排在第三位的是其中度序列为( 1 ，l ，1 ，2 ，2 ，3 ，3 ，3 ，3 ，3 ) 或( 1 ，1 ，2 ， 2 ，2 ，3 ，3 ，4 ) 的图； ( i v ) 排在最后一位的是其中度序列为( 1 ，l ，2 ，2 ，3 ，札一( p + g ) + 3 ) 的图： - 4 一 图依谱矩的排序 ( v ) 排在倒数第二位的是其中度序列为( 1 ，1 ，2 ，2 ，4 ，n + g ) + 2 ) 的图； ( 、r i ) 排在倒数第三位的是其中度序列为( 1 ，1 ，2 ，2 ，3 ，n 一0 + g ) + 2 ) 的图； 图依谱矩的排序 第二章预备知识 2 1 谱矩序列的字典序 图g = ( ve ) 是凡阶简单图，其顶点集y = u 。，也，】，g 中与 顶点地关联的边数称为顶点顶点忱的度，记作d ( 优) ，称非负整数序列 ( d ( u 1 ) ，d ( 忱) ，d ( ) ) 为g 的度序列 g 的邻接矩阵是一个n n 矩阵a ( g ) = ( ) n 撕其中 = 三：当地与吻相翼茬： 称a ( g ) 的特征多项式p ( g ，a ) = l 入，一a i 的根为g 的特征值 设入。入：入n 是n 阶图g 的所有特征值，则g 的七阶谱矩 s 七( g ) 为g 的所有特征值的七次幂之和，即观( g ) = 砖 谱矩序列s t = ( s o ，s l 一，s 。) 是图g 的一个有限不变量序列，对于两个 n 阶图g 1 和g 2 ，若s ( g 1 ) = s i ( g 2 ) ，( i = 1 ，2 ，r 1 ) 且s r ( g 1 ) s ，( g 2 ) ，( 1 r t ) ，则称依s 。字典序g l 排在g 2 之前，简称为g 。依s 。序先于g 。或g 2 依s t 序后于g l ，记作g 1 s t ( g ，) 即依s t 序有g 7 先于g 证明由于上述两个图g 和g 7 是有相同的点数、边数、三角形个 数的简单图，所以由引理2 1 1 知s o ( g ) = s o ( g ，) s - ( g ) = s l ( g ，) ，s 2 ( g ) = s 2 ( g ) ，s 3 ( g ) = s 3 ( g ，) 又 s 4 ( g ，) 一s 4 ( g ) = 4 【c ：乞。( u ) + l + l 一9 乞。( u ) + 2 1 = 4 ( 一d g 0 ( u ) ) 如2 ，点t | 和u 分别粘合路m 和珊的到图g ，图g ，_ g 一仳+ l + + l 如图2 6 所示 - 1 0 图依谱矩的排序 ( 图2 6 ，变换) 引理2 2 4 对于上述两个图g 和g ，有s 0 ( g ) = s o ( g ，) s l ( g ) = s l ( g 7 ) ， s 2 ( g ) = s 2 ( g ，) ，s 3 ( g ) = s 3 ( g ，) s 4 ( g ) s 4 ( g ，) 即依s 4 序有g ，先于g 证明由于上述两个图g 和g 是有相同的点数、边数、三角形个 数的简单图，所以由引理2 1 1 知s o ( g ) = s o ( g ，) s - ( g ) = s 1 ( g ，) ，s 2 ( g ) = s 2 ( g ) ，s 3 ( g ) = s 3 ( g ) ，又 s 4 ( g ，) 一s 4 ( g ) = 4 【c 乞。( u ) + 1 一c 乞。( u ) + 1 1 = 4 ( 1 一d g o ( 让) ) 如，t 是一棵树，将t 中的顶点t t ，分别与g o 中顶点u 和u 粘合得到图 g 和g ，如图2 7 g ( u ) 如( u ( 图2 7 ，变换v ) 蕊、 高校教师在职硕士学位论文 引理2 2 5 对于上述两个图g 和g ，有s o ( g ) = s o ( g ，) s l ( g ) = s l ( g ，) s z ( g ) = s z ( g ，) s 。( g ) = s s ( g ，) s 4 ( g ) o 因此，依s 。序，有g ，后于g 。1 2 - 图依谱矩的排序 第三章树依& 字典序的排序 在本章中，我们将利用前一章的变换给出树图依s 。序排列在前三位 的树的特征和后三位的树由定理2 1 1 知任意佗阶树的零到三阶谱矩均 相等，故证明时只须考虑s 4 ，对零到三阶谱矩不再赘述 3 1 依s 4 字典序前三位的树 利用图的变换，有 定理3 1 ( 【1 】) 设s = ( s o ，s ，s 2 ，) 是所有谱矩构成的序列，在所有n 阶树中，按s 序排列，排在第一位的树是路p n 证明设t 是一棵礼阶树，若丁p n ，则对r 施行变换i i i 得到路p n ， 由引理2 2 3 知，路孙依s 4 序排列在第一位 定理3 2 设t 是一棵n 4 ) 阶树，若r 的度序列不是( 1 ，1 ，2 ，2 ) 或( 1 ，l ，1 ，2 ，2 ，3 ) ，则s 4 ( t ) s 4 ( 乃) s 4 0 n ) ，其中死是一棵度序列为 ( 1 ，l ，l ，2 ，2 ，3 ) 的n 阶树，即依s 4 字典序，度序列为( 1 ，l ，1 ，2 ，2 ，3 ) 的 n 阶树排在第二位 证明因为度序列不是不是( 1 ，1 ，2 ，2 ) 或( 1 ，l ，l ，2 ，2 ，3 ) 的扎阶树 至少有两个度大于2 的顶点，由变换i i i ，任意度序列不是( 1 ，1 ，2 ，2 ) 或 ( 1 ，1 ，1 ，2 ，2 ，3 ) 的死阶树丁均可变换成一棵树死，使疋恰有一个三度点， 即死的度序列为( 1 ，l ，l ，2 ，2 ，3 ) ，由引理2 2 3 和2 2 4 有s 4 ( t ) s 4 ( 死) ， 显然s t ( 乃) 5 4 ) ，所以有s 4 ( 丁) s 4 ( 死) s 。) ，即依s t 字典序度序列为 ( 1 ，l ，l ，2 ，2 ，3 ) 的n 阶树排在第二位 定理3 3 设r 是一棵n ( n 5 ) 阶树n 5 ，若丁的度序列不是 ( 1 ，1 ，2 ，2 ) 或( 1 ，1 ，1 ，2 ，2 ，3 ) 或( 1 ，l ，l ，1 ，2 ，2 ，3 ，3 ) ，则有s 4 ( t ) s 4 ( 死) s 4 ( 正) s 4 ( p n ) ，其中乃和乃分别是一棵度序列为( 1 ，l ，1 ，2 ，2 ，3 ) 和 ( 1 ，1 ，l ，l ，2 ，2 ，3 ，3 ) 的n 阶树 证明设t 是一棵礼阶树，若t 的度序列不是( 1 ，l ，2 ，2 ) 或( 1 ，l ，l ， 一1 3 _ 高校教师在职硕士学位论文 2 ，2 ，3 ) 或( 1 ，1 ，1 ，1 ，2 ，2 ，3 ，3 ) ，则t 至少有三个度大于2 的顶点或一 个度大于3 的顶点 对于前者可利用变换i i i 和将t 化为一棵度序列为( 1 ，l ，1 ，1 ，2 ， 2 ，3 ，3 ) 的树；对于后者利用变换i i i 和也可将t 化为一棵度序列为 ( 1 ，1 ，1 ，1 ，2 ，2 ，3 ，3 ) 的树，由引理2 2 3 和引理2 2 4 和引理2 2 5 知，s 4 ( 丁) s 4 ( 死) ，从而s 4 ( t ) s 4 ( 死) s 4 ( 乃) s 4 n ) 即依s 4 字典序度序列为( 1 ，1 ，l ，1 ，2 ，2 ，3 ，3 ) 的n 阶树排在第三位 3 2 依s 4 字典序的后三位的树 利用图的变换，有 定理3 4 ( 【1 】) 在所有n 阶树中，依s 4 字典序，星树硒扩，排在最后 证明对于任意死阶树t ，若丁k 。卜t ，则由变换i ，可将t 转化为 甄，n 1 由引理2 2 1 知，s 4 ( ，n _ 。) s 4 ( t ) 即依s 4 字典序，星树虬俨。排在 最后因此，依s 字典序，星树噩一。也排在最后 定理3 5 设n 阶树丁g 所p 1 ，丑2 ) 其中他4 ，则有s 4 ( 丁) s 4 ( 丑2 ) ) s t ( 死) s t ( 瓦) s 4 ( t ) ，因此，依s 4 字典序，死排 在倒数第二位 定理3 6 设n 阶树t 掣 琏严l ，丑2 ) ，丑s ) ，( 竹5 ) ，则有s 4 ( 丁) s 4 ( 丑3 ) ) s 4 ( 丑。) ) s 4 ( 。”。) ，即依s 4 字典序，丑s ) 排在倒数第三位，( 其中丑。) 如图3 _ 1 所示，正。) 如图孓2 所示) f 7 l 一4 【 r n 一4j ? ( 图3 2 ，丑3 ) ) 证明由引理2 2 5 ，显然s 4 ( 互3 ) ) 3 时，利用变换i 和i i ，可将t 转化为死( 图3 2 ) ，由引理2 2 1 和2 2 2 知，s 4 ( 死) s 4 ( t ) 显然s 4 ( 丑。) ) s 4 ( 死) ，所以有s 4 ( t ) s 4 ( 死) s 4 ( 丑3 ) ) s 4 ( 暖，p ) s 4 ( 阱，p ) ，其中暖，p 是 一个度序列为( 1 ，1 ，2 ，2 ，3 ，3 ) 且圈长为p 的n 阶单圈图，即依s 4 字典序， 度序列为( 1 ，1 ，2 ，2 ，3 ，3 ) 且圈长为p 的礼阶单圈图排在所有圈长为p 的 n 阶单圈图第二位 一1 7 高校教师在职硕士学位论文 g l _ _ _ _ _ o _ _ _ _ 一 仇 n p 一2 2 ，2 ( 图缸2 ，职，p ) i m p r g 2 证明若g 中的圈上至少有两个顶点的度大于2 ，则利用变换i i i 和i v ，g 可转化为g l ( 图垂2 ) ，由引理2 2 3 和2 2 4 知，s 4 ( g ) s 4 ( g 1 ) ，且g l 是度序列为( 1 ，1 ，2 ，2 ，3 ，3 ) 且圈长为p 的n 阶单圈图 若g 中的圈勺上只有一个顶点的度大于2 ，因g 畦川则利用变换 i i i 和v 可将g 转化为g 2 ( 见图垂2 ) ，由引理2 2 3 和2 2 5 知，s 4 ( g 2 ) s t ( 碟，p ) 所以依s 4 字典序，度序列为( 1 ，1 ，2 ，2 ，3 ，3 ) 且圈长为p 的n 阶单圈 图排在圈长为p 的n 阶单圈图中的第二位 定理4 3 若圈长为p 的n 阶单圈图g 的度序列不是( 1 ，2 ，2 ，3 ) 或( 1 ，1 ，2 ，2 ，3 ，3 ) ，或( 1 ，1 ，1 ，2 ，2 ，3 ，3 ，3 ) ，其中n p + 3 ，则有s 4 ( g ) s 4 ( 暖，p ) s 4 ( 职，p ) s t ( 昧，p ) ，其中畦，p 是一个度序列为( 1 ，1 ，1 ，2 ，2 ，3 ，3 ，3 ) 且圈长为p 的佗阶单圈图即依s 4 字典序，度序列为( 1 ，1 ，1 ，2 ，2 ，3 ，3 ，3 ) 且圈长为p 的佗阶单圈图排在所有圈长为p 的n 阶单圈图中的第三位 旺；! ；薹q g lg 2g 3 r + t + s = n p 一3 ，r 2 ，s 2 ，2 ( 图4 - 3 ，昵，p ) 证明分三种情况 1 8 一 l p r 1 t 8盐m 阶 _ 一鼽 一 图依谱矩的排序 ( 1 ) 若g 中的圈白上至少有三个顶点的度大于2 ，则利用变换i i i 和 i v ，g 可转化为g l ( 图4 - 3 ) ，由引理2 2 3 和2 2 4 知，s 4 ( g ) s 4 ( g 1 ) ，且g l 是 度序列为( 1 ，l ，1 ，2 ，2 ，3 ，3 ，3 ) 且圈长为p 的几阶单圈图 ( 2 ) 若g 中的圈唧上恰有两个顶点的度大于2 ，因g 度序列不为 ( 1 ，1 ，2 ，2 ，3 ，3 ) 则利用变换i i i 和v ，g 可转化为g 2 ( 图垂3 ) ，由引理2 2 3 和2 2 5 知，s 4 ( g ) s 4 ( g 2 ) ，且g 2 是度序列为( 1 ，1 ，1 ，2 ，2 ，3 ，3 ，3 ) 且圈长为 p 的n 阶单圈图 ( 3 ) 若g 中的圈勺上恰有一个顶点的度大于2 ，因g 度序列不为 ( 1 ，2 ，2 ，3 ) 或( 1 ，1 ，2 ，2 ，3 ，3 ) 则利用变换i i i 和v ，g 可转化为g 3 ( 图4 - 3 ) ，由引理2 2 3 和2 2 5 知，s 4 ( g ) s 4 ( g 3 ) ，且g 3 是度序列为( 1 ，1 ，l ，2 ，2 ，3 ，3 ，3 ) 且圈长为p 的n 阶单圈图 显然有s 4 ( g 1 ) = s 4 ( g 2 ) = s 4 ( g 3 ) s 4 ( 醒，p ) s 4 ( 畦，p ) ， 由( 1 ) ( 2 ) ( 3 ) 知，s 4 ( g ) s 4 ( g ( i ) ) ，( 江1 ，2 ，3 ) ，且g i 是度序列为( 1 ，1 ，1 ，2 ，2 ， 3 ，3 ，3 ) 且圈长为p 的n 阶单圈图，即依s 4 字典序，度序列为( 1 ，1 ，1 ，2 ，2 ，3 ，3 ，3 ) 且圈长为p 的n 阶单圈图排在第三位 4 2 依s 4 字典序后三位的单圈图 本节，我们依s 。字典序给出圈长为p 的n 阶单圈图的后三位的图及 其特征利用图的变换，有 定理4 4 ( 【l 】) 在所有圈长为p 的礼阶单圈图中，依s 序的排列，排在倒 数第一位的是“1 2 ，其中“2 是在一个长为p 的圈c p 上粘合星树七。，n p 的 中心点形成的单圈图，如图缸4 ， u l 忱 t 7 n p ( 图垂4 ，嘲) 证明若圈长为p 的n 阶单圈图g “2 ，则利用变换i 和变换i i ，g - 1 9 - 高校教师在职硕士学位论文 可转化为班2 ，由引理2 2 1 和引理2 2 2 知s 。( g ) s 。( 吸2 ) ，即依s t 字典序 的排列，排在圈长为p 的n 阶单圈图倒数第一位的是吮2 所以 依s 字典 序的排列，讲2 也排在倒数第一位 定理4 5 设圈长为p 的住阶单圈图g 不是咄或噶，则s 4 ( g ) s 。( 嗍) s 。( 呱1 2 ) ，其中碟2 如图垂5 ，即依5 4 字典序，图嗍排在所有圈长 为p 的礼阶单圈图倒数第二位 ( 图4 5 ) 证明。圈长为p 的n 阶单圈图g 畦且g 嘲，则有两种情况 ( 1 ) 若g 中的圈c p 上至少有两个顶点的度大于2 ，则利用变换i 和i i ， g 可转化为嗍( 图垂5 ) 由引理2 2 1 和引理2 2 2 知s 4 ( g ) s 4 ( 嗍) ，即依 s 4 字典序g 先于嗍 ( 2 ) 若g 中的圈c p 上恰有一个顶点的度大于2 ，由于g “譬，则利用 变换i ，g 可转化为g 。( 图4 5 ) ，再利用变换v ，g 。可转化为嗍由引理2 2 1 和引理2 2 5 知s t ( g ) s t ( 噶) ，即依s t 字典序g 先于蚓 由( 1 ) ( 2 ) 知，依s 4 字典序，蟛排在所有圈长为p 的n 阶单圈图倒数 第二位 定理4 6 设圈长为p 的礼( n 5 ) 阶单圈图g 不是酲2 ，嗍或蚓，嗍 如图缸6 ) 则s 4 ( g ) s 4 ( 蟛) s t ( 蟛) s 。( 嘲) 即依s 4 字典序，嘲排在 所有圈长为p 的n 5 ) 阶单圈图的倒数第三位 2 0 图依谱矩的排序 ( 图4 6 ) 嘲 证明度设圈长为p 的扎阶单圈图g 不是蟛，噶或嘲，则g 可分 为以下两类 ( 1 ) 圈勺外的树高度全是1 ，即所有的点都悬挂在圈勺外，对于此类 图做变换v 可得图g 1 ( 图垂6 ) ，由引理2 2 5 知s 4 ( g ) s 4 ( g 1 ) 当几一p 5 时，可计算出s 4 ( g 。) s 4 ( 嘴碧) 所以s 4 ( g ) s 4 ( 醚) s 4 ( 瞻) s 。( 咄) ( 2 ) 圈c p 外的树高度不全是l ，则至少有一棵树的高度大于等于2 ，对 此类图做变换i ，i i 和v 可得图蟛( 图4 6 ) ，由引理2 2 1 和2 2 2 和2 2 5 ，知 s 4 ( g ) s 4 ( 巩彗) ，即s 4 ( g ) s 4 ( 醴碧) s 。( 畦2 ) s 4 ( 以碧) 由( 1 ) ( 2 ) 知，s 。( g ) s 4 ( 畦碧) s 4 ( 以( p ，g ) ) ，即以( p ，g ) 依s 4 字典序排在月n ( p ，q ) 类在第一 位 定理5 2 设g a 。( p ，g ) 若g 的度序列不是( 1 ，2 ，2 ，3 ，4 ) 或( 1 ，l ，2 ， 2 ，3 ，3 ，4 ) 则s 4 ( g ) s 4 ( 群，口) ) s 4 ( 疋，口) ) ，其中走0 ，垡) 是一个度序列为 ( 1 ，l ，2 ，2 ，3 ，3 ，4 ) 的图，如图5 2 所示，即依s 4 字典序，在a n ( p ，口) 中度序 一2 3 高校教师在职硕士学位论文 列为( 1 ，1 ，2 ，2 ，3 ，3 ，4 ) 的图排在第二位 0 9 - o p g 2 g 3 ( 图5 - 2 ) 证明略，方法同上 同样可得 定理5 3 设g a 。白，口) 且g 的度序列不是( 1 ，2 ，2 ，3 ，4 ) 或( 1 ，l ，2 ， 2 ，3 ，3 ，4 ) 或( 1 ，l ，1 ，2 ，2 ，3 ，3 ，3 ，4 ) ) ，则s 4 ( g ) s 4 ( a ：，q ) ) s 4 ( a ：0 ，q ) ) s 4 ( 以( p ，q ) ) ，其中a ：，口) 是一个度序列为( 1 ，1 ，1 ，2 ，2 ，3 ，3 ，3 ，4 ) ) 的图，即 依s 4 字典序，在a 。( p ，g ) 中度序列为( 1 ，1 ，l ，2 ，2 ，3 ，3 ，3 ，4 ) ) 的图排在第三 位 5 2a ，口) 依s 4 字典序后三位的图 本节，我们依s t 字典序给出a 。( p ，g ) 类后三位的图的特征 定理5 4 在集合a n p ，g ) 中，依s 。字典序排列，排在最后的图是a 9 ( p ，q ) ， 其中a 9 ( p ，口) 是在圈勺与勺的公共点上悬挂几一( p + 口一1 ) 个点构成的图 ( 如图5 - 3 ) ( 图5 - 3 ，a 擘，g ) ) 1 ) + 4 证明若g a n ( p ，g ) 且g a 9 ( p ，g ) ，则对g 做变换i 和i i 即可得 a 9 ( p ，g ) ，由引理2 2 1 和2 2 2 知s 4 ( g ) a 9 ( p ，口) ，即依s 4 字典序a 9 ，g ) 排在a 。( p ，g ) 中的倒数一位 2 4 图依谱矩的排序 类似的，利用变换i 和i i ，可得如下结果，其证明略 定理5 5 若g a 。( p ，g ) ，g a 9 ，口) 且g 的度序列不是( 1 ，1 ，2 ， 2 ，3 ，n 一+ g 一1 ) + 3 ) ，贝4s 4 ( g ) s 4 ( a 窘0 ，g ) ) s 4 ( a 9 ( p ，口) ) ，其中a 窘，口) a ，g ) 是一个度序列为( 1 ，1 ，2 ，2 ，3 ，n 一( p + 口一1 ) + 3 ) 的图，即依s 4 字典序，4 n p ，g ) 中度序列为( 1 ，l ，2 ，2 ，3 ，n 一( p + g 1 ) + 3 ) 的图排在 倒数第二位 定理5 6 若g a 。0 ，g ) ，其中n p + g + 4 且g 的度序列不是( 1 ，1 ， 1 ，2 ，2 ，n 一加+ 口一1 ) + 4 或( 1 ，1 ，2 ，2 ，3 ，n 一0 + q 一1 ) + 3 ) 或 ( 1 ，1 ，2 ，2 ，佗一0 + g 1 ) + 3 ) ，贝0s 4 ( g ) s 4 ( a 窘0 ，口) ) s 4 ( b ：，m ( p ，g ) ) ，其中砩，。加，g ) 巩，m ( p ，q ) 是一个度序列为( 1 ，1 ，2 ，2 ，3 ，3 ，3 ，3 ) 或( 1 ，2 ，2 ，3 ，4 ) 的图，即 依s t 字典序，在风，m ，q ) 中度序列为( 1 ，1 ，2 ，2 ，3 ，3 ，3 ，3 ) 或( 1 ，2 ，2 ，3 ，4 ) 的图排在第二位 定理5 9 若g b n ，m 白，g ) 且g 的度序列不是( 1 ，2 ，2 ，3 ，3 ，3 ，) 或 ( 1 ，l ，2 ，2 ，3 ，3 ，3 ，3 ) 或( 1 ，2 ，2 ，3 ，4 ) 或( 1 ，l ，l ，2 ，2 ，3 ，3 ，3 ，3 ，3 ) 或( 1 ，1 ， 2 ，2 ，3 ，3 ，4 ) ，则有s 4 ( g ) s 4 ( 联，m ) s 4 ( 群，m ，q ) ) s 4 ( 碟m 积q ) ，其中 磁，m p ，q ) 是度序列为( 1 ，l ，1 ，2 ，2 ，3 ，3 ，3 ，3 ，3 ) 或( 1 ，1 ，2 ，2 ，3 ，3 ，4 ) 的图， 即依s 4 字典序在鼠，m ( p ，鼋) 中度序列为( 1 ，l ，l ，2 ，2 ，3 ，3 ，3 ，3 ，3 ) 或( 1 ，l ，2 ， 2 ，3 ，3 ，4 ) 的图排在第三位 5 4 既，m ( p ，留) 依s 4 字典序后三位的图 利用变换l 和i i ，可得b n ，m 0 ，q ) 中排在后三位的图，其过程略 定理5 1 0 在民。，g ) 中，依s 4 字典序排列，排在最后的图是堪0 ，g ) ， 其中磷_ ( p ，g ) 是如图5 6 ( 图5 6 ，b 是 ，g ) ) 定理5 1 1 在风，m ，g ) 中，依s 4 字典序排列，排在倒数第二位的图是 磁_ ( p ，口) 如图5 - 7 2 6 图依谱矩的排序 一m 、 ( 图5 - 7 ，b 踹( p ，q ) ) 定理5 1 2 在玩，。0 ，q ) 中，依s 4 字典序排列，排在倒数第三位的图是 嗽，g ) ，如图孓8 所示其中n 一( p + g 一仇) 5 ) 卜勺l ( 图5 8 ，端窖) ) 5 5g 0 ，g ) 依s 4 字典序的排序 利用前面的方法，类似的可给出集合g ( p ，口) 中图依s 。字典序的排序， 这里只列出结果，证明过程略 定理5 1 3 在g ( p ，g ) 中，依s 4 字典序排在第一位的是其中度序列为 ( 1 ，2 ，2 ，3 ，3 ，3 ) 的图 定理5 1 4 在g ，g ) 中，依s 4 字典序排在第二位的是其中度序列为 ( 1 ，l ，2 ，2 ，3 ，3 ，3 ，3 ，) 或( 1 ，2 ，2 ，3 ，4 ) 的图 定理5 1 5 在g ( p ，q ) 中，依s t 字典序排在第三位的是其中度序列为 ( 1 ，1 ，1 ，2 ，2 ，3 ，3 ，3 ，3 ，3 ) 或( 1 ，1 ，2 ，2 ，3 ，3 ，4 ) 的图 定理5 1 6 在g ( p ，g ) 中，依s 4 字典序排在倒数第一位的是其中度序 列为( 1 ，l ，1 ，2 ，2 ，3 ，n 一( p + g ) + 3 ) 的图 2 7 高校教师在职硕士学位论文 定理5 1 7 g ( p ，g ) 中，依s 4 字典序排在倒数第二位的是其中度序列为 ( 1 ，1 ，1 ，2 ，2 ，4 ，n 一0 + q ) + 2 ) 的图 定理5 1 8 g ( p ，g ) 中，依s 4 字典序排在倒数