（基础数学专业论文）一些图类的上可嵌入性.pdf

一些图类的上可嵌入性 摘要 本文主要研究拓扑图论的一个重要分支图的上可嵌入性以及图的 最大亏格的问题，其中图的最大亏格是刻划图在某个定向曲面上是否有 二包腔嵌入的一个特征参数，而确定一类图的上可嵌入性就是要确定图 的最大亏格结合图的一个或几个参数，给出了若干新的上可嵌入图 具体内容如下； 1 第三章结合图的距离及点度，根据不是上可嵌入的图的一个特征 结构，并利用反证法，确定了几类新的上可嵌入图； 2 第四章结合图的连通度和非邻节点度和条件，确定了几类新的上 可嵌入图； 3 第五章结合图的独立数和围长，确定了几类新的上可嵌入图，从 而将已有这方面的结果作了较大的推广，较完整地刻划了这些图类的上 可嵌入情况 关键词：上可嵌入； 最大亏格；b e t t i 亏数；点度；连通度；独 立数；围长 一些图类的上可嵌入性 a b s t r a c t t h i sp a p e rc h i e f l ys t u d i e sa 丑i m p o r t a n ts u b j e c ti nt o p o l o g i c a lg r a p h - t h ee l - b e d d i n ga n dg e n e r ao fag r a p h ，a n dt h em a x l m u i ng e n u so fg r a p hi sac h a r a c t e r i s t i c p a r a m e t e r , w h i c hd e t e r m i n e sag r a p hw h e t h e rh a sa2 - c e l le m b e d d m g i nac e r t a i no d - e n t a b l e s u r f a c e w h i l e t h e d e t e r m i n a t i o n o f a g r a p h u p p e re m b e d d a b i l i t y i 8 t o d e t e r - m i n eag r a p h u 1 9 1 x i m u l “g e n u s c o m b i n i n go n eo rm o r ep a r a m e t e r so fag r a p h ，8 0 m e c l a s s e so fn e wa n du p p e re m b e d d a b l e 舒8 p h 8w i l lb eg i v e ni nt h et h e s i sa 8f o l l o w s ： 1 d e t e r m i u i a gs o m ed a s s e so fn e wa n du p p e re m b e d d a b l eg r a p h si nc h a p t e r t h r e eb yc o m b i n i n gt h ed i s t a n c ea n dt h ev e r t i c ed e g r e e ，f u r t h e r m o r e ，b a s i s i n go na c h a r a c t e r i s t i cs t r u c t u r eo fau n u p p e re m b e d d a b l eg r a p h ； 2 d e t e r m i n i n gs o m ed a s s e so fn e wa n du p p e re m b e d d a b l eg r a p h si nc h a p t e r f o u rb yc o m b i n i n gt h ec o n n e c t e dd e g r e ea n dt h eg i r t h ； 3 d e t e r m i n i n gs o m ec l a s s e so fn e wa n du p p e re m b e d d a b l e 字a p h si nc h a p t e r f i v eb yc o m b i n i n gt h ei n d e p e n d e n t - n u m b e ra n db u mo ft h ed e g r e eo ft h eu n u e i g h - b o r e dv e r t e x e s t h u si tg e n e r a l i z e df u r t h e rt h er e l a t i v er e s u l t s ，a n dc h a r a c t e r i z e de l l - t i r e l yt h eu p p e re m b e d d g ! b i l i t yo fs u c hc k l 8 8 鹤o fg r a p h s ； k e y w o r d s ：u p p e re m b e d d a b l e ；m a x i m u mg e n u s ；b e t t id e f i c i e n c y ；v e r t i c ed e - g r e e ；c o n n e c t e dd e g r ；i n d e p e n d e n t - n u m b e r ；g i r t h i i l 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的研究成果除了文中特别加以标注引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完 全意识到本声明的法律后果由本人承担 学位敝储样：7 稚吮 叩年钥j 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研 究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分 内容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打“ ”) 作者签名 括声以 翩懿莒纰 日期：叼年6 月7 日 日期：却泸6 月日 一些图类的上可嵌入性 第一章引言 图论是组合数学的一个主要组成部分，近几十年里，它已经发展成 数学的一个重要分支由于图论本身的魅力和其在信息社会中一些学科 领域诸如计算机，运筹学，系统工程以及物理学，电子学，生物学，化学 等方面的广泛应用，因此，越来越受到科学界尤其是数学界的重视和关 注由于组合数学，代数学，拓扑学以及概率方法的结合，现代图论除了 传统的研究领域外已发展为包括代数图论，拓扑图论，以及随机图论等 分支在内的多个新的领域，促进了图论的发展 拓扑图论是目前国际上一个非常活跃的图论分支其中对图的拓扑 参数一最大亏格的研究又是一个十分重要的课题之一自从七十年代初， 由e n o r l d a u s b s t a i v a n t 和a w h i t e 提出图的最大亏格以来，很多图论学者 都投身于这方面的研究，但随着其研究的深入，它越来越多地与其它数 学分支相互交叉，相互影响，使之成为目前这方面研究的重要发展趋势 目前，图的最大亏格的研究主要表现在如下几个方面： ( 1 ) 特征结构 七十年代末，n h x u o n g 借助于图的支撑树上的补图，通过引进b e t t i 亏数，给出了图的最大亏格的表示定理国内刘彦佩教授通过应用确向 树理论方法，证明了一个图是上可嵌入的当且仅当存在2 - 重图上的标准 e u l e r 圈，给出了一些图的嵌入的可约化模型，也构造性地解决了图的不 可定向最大亏格的存在性问题八十年代初，l n e b e s k y 用图的去边子图 给出了图的另一个b e t t i 亏数的组合表达式由此，黄元秋教授和刘彦佩 教授研究了图不是上可嵌入的充要条件n h x u o n g ，j j c h e n 和j l g r o s s 等人的工作表明对图的最大亏格的研究往往可以转化为一个特殊的3 - 正 则图的情形黄元秋教授和刘彦佩教授证明了一个3 正则图的最大亏格 硕士学位论文 等于其最大不可分离独立数，在结构上给出3 - 正则图上可嵌入的充要条 件另外，黄元秋教授和刘彦佩教授通过引进图的扩张运算，研究了扩 张运算与图的b e t t i 亏数之间的内在联系，揭示了图的最大亏格与图的2 - 因子的某些联系然而，在探求图的最大亏格的结构特征上，仍有广阔 的前景 ( 2 ) 上可嵌入性 一个图是上可嵌入的表明其最大亏格可取到最好的上界虽然l i u 2 和n e b e s k y 4 分别提供了不同的确定图的上可嵌入性充要条件，黄元秋教 授和刘彦佩教授【5 】研究了图不是上可嵌入的充要条件，但对于什么类型 的图是上可嵌入的尚知不多，现综合已知为上可嵌入的图如下： 所有奎连通图( k u n d a 3 ) ；所有循环垂边连通图( j a e g e r ，p a y a n 和x u o n g ) ；局部连通的连通图( n e b e s k y1 7 ) ；局部拟连通的连通图( n e b e s k y 【鞠) ；4 k + 2 - 正则的连通图( k o v e r i a 【9 j ) ；在某曲面上可三角化的图( k l u k o v 1 【1 1 ) ；直径 为2 的简单图( k o v i e r a 1 1 1 ) ；在曲面上有一个嵌入使得每面边界长均不超 过5 的图( k 嘶e r a1 1 2 1 ) ；2 一局部连通的连通图( n e b e s k y 【1 3 】) 因而判定什么样的图类是上可嵌入的是很有意义的工作 ( 3 ) 最大亏格的下界与图的其它参数的联系 n h x u o n g 和l n e b e s k y 考虑了最大亏格与图的连通性的关系j c h e n 和j l g r o s s 给出了与连通性有关的简单图的最大亏格的下界估计式 d a r c h d e a c o n 考虑了3 - 边连通( 非简单) 图的情形黄元秋教授推广了上 述工作，对任意k - 边连通( 非简单) 图，给出了由图的最小度所表达的图 的最大亏格的下界表达式，证明了最小度趋向无穷大时，最大亏格趋近 最好的上界最近，黄元秋教授研究了图的最大亏格与图的余色数及团 的关系，利用h e a d w o o d 着色定理揭示了图的最大亏格与图的亏格之间的 联系 f j ( 4 ) 利用拟阵研究图的嵌入及有关算法 利用拟阵考虑图的嵌入是人们所熟知的工作t u t t 地和国内剂彦佩教 2 一些图类的上可嵌入性 授等人的工作表明图的平面嵌入的判断可转化为判断拟阵的图性和上图 性m l f t t r s t 和j l g r o s s 运用拟阵研究了图的最大亏格嵌入，给出了图 的最大亏格嵌入多项式算法是否存在多项式时间算法来判断图的同构 一直是一个公开性的问题，限定图的平均亏格，j c h e l a 和j l g r o s s 证明 了存在多项式时间算法来判断图的同构问题，邓汉元教授利用差集刻画 了拟阵正则自同构的充要条件，李荣衍教授在算法复杂性分析及问题复 杂性研究方面做过一定的研究工作目前邓汉元教授和李荣衍教授在算 法复杂性分析及问题复杂性分析研究方面做过一定的研究工作并且他 们在利用拟阵考虑图的有关嵌入算法以及研究判断图的同构问题的算法 方面的工作是属于起步性的 本文受文献【2 1 1 3 9 的启发，运用和发展了其中某些方法，根据图的 点度，独立数，围长，连通度以及其它条件，得到了一些新的上可嵌入 图，推广和深化了目前有关这方面的结果 3 一些图类的上可嵌入性 第二章基本概念和性质 2 1 基本概念 本文考虑的图，若无指明均指有限无向的简单连通图，其他未加说明 的术语和记号均同文献【1 】个图g 是指个有序三元组( g ) ，e ( g ) ，怕) 其中v ( a ) 是非空的顶点集，e ( a ) 是不与v ( g ) 相交的边集，丽惦是 关联函数，它使g 的每条边对应于g 的无序顶点对i v i = n 称为图g 的阶。设删e ，则称顶点u ，”为相邻节点，否则，称“，”为非邻节点 g 的两个顶点u ，”称为连通的，如果在g 中存在从u 到”的路 连通是顶点集v ( a ) 上的一个等价关系于是存在v ( a ) 的一个分类，把 v ( a ) 分成非空子集h ，亿，使得两个顶点u ，v 是连通的当且仅当它 们属于同一个子集k 子图，g m 】，g 【k 1 ，g f 吲称为g 的连通分支若 g 只有一个分支，则称g 是连通的；否则，称g 是不连通的若y ( g ) 的子集矿使得v ( g ) 一不连通，则称为y ( g ) 的顶点割k 顶点割是 指有k 个元素的顶点割若g 至少有一对相异的不相邻顶点，则g 所具 有的k 顶点割中最少的k ，称为g 的连通度，记为一( g ) 若一( g ) k ，则称 g 为k 连通的对v ( a ) 的子集s 和，用旧霸表示一个端点在s 中， 另一个端点在中的所有边的集合所谓g 的边割是指形为【s ，明的 e ( g ) 的子集，其中s 是v ( a ) 的非空真子集一个k 边割是指有k 个元 索的边割若g 是非平凡的，g 的所有k 边割中最少的k ，称为g 的边 连通度，记为一( g ) 若( g ) ，则称g 为k 边连通的称图片为图g 的子图，如果v ( h ) 呈y ( 回，e ( h ) 量e ( g ) ，并且妇是妒g 上的限制g 的 生成子图是指满足v ( h ) = v ( a ) 的子图日假如是矿的一个非空子 集以为顶点集，以两端点均在中的边的全体为边集所组成的子 图，称为g 的由y 导出的子图，记为g 【v 1 5 硕士学位论文 曲面是一个紧的连通的2 维闭流形曲面可分为定向曲面与不可定 向曲面一个可定向曲面s 是由一个球面添上h 个环柄得到不可定向 曲面是由一个球面挖掉k 个圆盘而分别补上m s b i u s 带得到其中，岛 称为球面，最称为环面，岛称为双环面；l 称为射影平面，2 称为 克莱因瓶 如果一个图画在曲面s 上使得它的边仅仅在端点处相交，则称这个 图嵌入到曲面s 上图g 嵌入曲面s 上称为2 _ 胞腔嵌人，如果s g 中 每个分支同胚于一个开圆盘此时，每个分支称为g 在曲面s 上的个 面图g 的最大亏格，记为撕( g ) ，是指最大的整数k 使得g 能2 胞腔嵌 入亏格为k 的定向曲面s 上因为图在任意定向曲面的暑胞腔嵌入中至 少有一个面，由e u l e r 公式易得一个图g 的最大亏格上界t m ( g ) 【譬j ， 其中芦( g ) = l e ( g ) 卜i y ( g ) l + 1 称为图g 的b e t t i 数( 对任意实数。，l z j 表示 不超过z 的最大整数) 同时，若啊( g ) = 【星擎j ，称图g 是上可嵌人的 对任意集合x ，l x l 表示x 的基数设y 为图g 的任意边集，g y 表示从g 中去掉y 中的所有边所得到图若t 为图g 的一棵生成树， 记号f ( g ，t ) 表示所有g e ( t ) 中边数为奇数的连通分支数称f ( g ) = n 知( ( g ，研) 为g 的b e t t i 亏数，其中m i n 取遍g 的所有生成树r 设 a e ( u ) 为图g 的边子集，记号c ( g a ) 及6 ( g a ) 分别表示g a 所有 连通分支数及其g a 的具有b e t t i 数为奇数的所有连通分支数一个顶 点口 ，( f ) ，若它为f g ) 中f 条边的端点，则称之为f 的一个i 一触点； 特别t = 0 表示口不与h ( h c ( g a ) ，) 中任何点相邻一个图g 的最 大独立集的顶点数称为g 的独立数，通常记为a ( g ) ；设耳为图g 的独立 集，中一顶点z 为g a 后一连通分支f 的i 一触点，若存在f 的另 一矿一触点一，使其代替z 后，在图g 中与中其它各顶点仍不相邻， 则称在f 中进行了一次顶点轮换d ( u ， ) = 2 表示图g 中距离为2 的两点 ”一若图g 中息与点”相邻，点”与点伽相邻。则稚“一，叫三点依次 j 2 1 ，则g 是上可嵌入的，且 条件中不等式的下界。鸶一1 ”是不可达的； 定理3 2 设g 是3 - 连通图，其中n = i 矿( g ) f ，若对任意依次相邻的三点 缸，口，伽，有”m d ( ) ，d ( ”) ，d c w ) 詈+ l ，则g 是上可嵌入的，且条件中不等 式的下界“2 + 1 ”是最好的 硕士学位论文 3 ，1 定理3 1 的证明 定理3 1 的证明用反证法假设g 不是上可嵌入的，则由定理c ，存在 a e ( g ) 使得性质( 1 ) 一( 4 ) 成立设f 1 ，足，f t 是g a 的连通分支，其 中l = b ( g a ) ，由引理l ( 1 ) 知f 3 由定理c 0 ) 知，对g a 的任意连 通分支冠，都有z ( a ) 毫1 ( r o o d 2 ) ，从而每一个分支只中至少存在一个圈 g ，又g 为简单图，且不含玛，因此圈q 中也不含飓，从而i y ( a ) i 4 对g 中所有距离为2 的点对，必有存在于g 中的( 不妨设为v 1 ) ，记 m a x d ( u t ) ，d m ) = d ) 下面分k3 和l 4 两种情形加以讨论； 情形1 当f - 3 时，由以上分析知，在只“= 1 ，2 ，3 ) 中至少存在一个 点u t “= 1 ，2 ，3 ) 因为g 是2 - 连通图，所以g a 的三个连通分支各分别 含两个一触点，又g 中不含飓，因此，d ( u ；) ( 1 y ( 冠) | - 2 ) + 1 ，从而 33 d ( 地) ( ( 1 y ( 只) i - 2 ) + 1 ) = n 一3 i = li = l 另外，由定理3 1 中条件有d ( u 。) ；一1 ，从而 3 d ( “t ) ( ；一1 ) x 3 = 昭一3 t = l 一 这样，则必有，l 一3 一1 ， 所以有如下不等式成立： d ( t ) ( ；一l ” 综上得t ( 一1 ) z n + 七一6 即：n 止驾烂 则g 是上可嵌入的，进而，这个下界是最好的 大家知道，确定一个图的独立数是一个n p 完全问题，结合图的独 立数以及连通度，文献f 1 9 1 中定理1 , 2 ，3 ( 即引理4 2 ) 证明了； 引理4 2 1 1 9 】( 1 ) 设g 是一个1 边连通简单图，若口( g ) s1 ，则g 是上可嵌 入的； ( 2 ) 设g 是一个冬边连通简单图，若a ( g ) 2 ，则g 是上可嵌入的； ( 3 ) 设g 是一个孓边连通简单图，若a ( g ) 曼5 ，则g 是上可嵌入的 对文献【1 8 】和文献【1 9 】的结果进行推广，得到了如下定理，即本章的 主要结果： 定理4 1 设g 为2 - 边连通简单图，且a ( g ) 3 ，若对于任何彼此不相邻 的三个顶点q a ：1 ，2 ，3 ) 都有3 如( 仇) i v ( g ) l 一2 ，则g 是上可嵌入的 i = l 而且条件中不等式的下界。l y ( g ) i - 2 ”是最好的 定理4 2 设g 为3 - 边连通简单图，且a ( g ) 6 ，若对于任何彼此不相邻 1 7 。 硕士学位论文 的六个顶点铫0 ：l ，2 ，6 ) ，都有6d g ( 地) i v ( g ) l + 1 ，则g 是上可嵌入 = l 的，而且条件中不等式的下界“l y ( g ) l + 1 ”也是最好的 在证明本章主要结果之前，先证明如下引理； 引理4 3 ( i ) 若g 是2 - 边连通简单图，任取g a 的3 个连通分支，不妨 设为只0 = 1 ，2 ，3 ) ，甄y ( 只) ，使得 z 1 ，现，蜘 为g 的独立集5 ( ) 若g 是3 - 边连通简单图，任取g a 的6 个连通分支，不妨设 为只0 = 1 ，2 ，6 ) ，3 x i y ( 只) ，使得 z 1 ，现， 为g 的独立集 证( i ) 若g 是2 - 边连通简单图，则由引理4 ( 5 ) 知c ( g a ) 3 ，任取 g a 的3 个连通分支，不妨设为e 0 = 1 ，2 ，3 ) ，由引理4 ( 1 ) ，l y ( 只) l 3 ，而根 据引理3 ( 3 ) 有：l e ，r u 最) l 2 ( s k ，s ，t ，k = 1 ，2 ，3 ) 所以j 戤y 慨) ， 且以不与毋a j ，l ，j ；1 ，2 ，3 ) 的任何顶点相邻，从而 z 1 ，娩，如为g 的 独立集；。 ( h ) 若g 是3 - 边连通简单图，则由引理4 ( 5 ) 知e ( g a ) 6 ，任取g a 的6 个连通分支，不妨设为最0 = 1 ，2 ，6 ) ，现在我们按如下方式构造一 个新图，记为g ；，g ；中的点q “= 1 ，2 ，6 ) 1 1 对应于只，g ；中任意两点 与仇连一条边，当且仅当，根据引理3 ( 3 m 和d t 分别对应的兄和r 有i e ( 只，冠) l = l ( s ，s ，t = 1 ，2 ，6 ) ，即g l 中的边1 1 对应于6 个连通 分支彼此间的连边，下面我们先证明如下断言： 断言1 任取 毋，如，r ) 中的5 个连通分支，不妨设为 日，尼，昂 则j 墨y ( 只) ，使得 z l ，x 2 ，如) 为g 的独立集 证设k = 。t ，也， ，把优【吲记为g 玉则一定存在某个顶点， 不妨设如，使得d g ；) s2 ，否则，若对0 = 1 ，2 ，5 ) 都有d 嚷( 仉) 3 ， 则 f ( g ；) f = ；电( 执) 2f 萼1 = 8 ，这与l e ( g ) i = i 曰假，尼，日局，丹) j 2 5 3 = 7 矛盾设k = h ，忱，诒，q ，把q l 吲记为q ，则一定存在某个 顶点，不妨设，使得蛔似) 2 ，杏则，若a ；1 ，2 ，3 4 l 都有电慨) 3 ， 1 8 一些图类的上可嵌入性 则i e ( g ；) i = ；d g ：( 忱) 等 一6 ，这与i e ( g ；) i = i e ( f t ，b ，晶，丹) is 一话l 一 4a 2 4 3 = 5 矛盾；这说明i e ( 咫，u 只) is2 ，i e ( f 4 ，u 最) i 2 ，又由性质( 1 ) 有i y ( 最) f23 ，所以孔5 矿限) ，使得x 5 不与鼠0 = 1 ，2 ，3 ，4 ) 中任何顶点相 邻，3 r , 4 y ( 凡) 使得2 4 不与只( t = l ，2 ，3 ) 的任何顶点相邻，特别有x 4 与 如不相邻现只考虑b ，b ，玛，则由上( i ) 可知，3 x t b 0 = 1 ，2 ，3 ) ，使得 轧勋，霜 为g 的独立集，从而 卫l ，勋，汹 也为g 的独立集因此断 言获证 下面分3 种情况讨论： 情形1 在图佛中若存在某个顶点，不妨设使得d 诺( 。) 2 ；因为 l v ( f d l23 ，所以j y ( r ) 使得不与毋o = 1 ，2 ，5 ) 中的任何顶点 相邻，又由断言1 知t 孤t y ( 只) a = 1 ，2 ，5 ) 使得 z l ，x 2 ，如 为g 的独立集，从而 z l ，x 2 ，粕 也为g 的独立集 情形2 在图g ；中若存在某个顶点，不妨设1 1 1 使得d g ；( ”- ) 24 ；则必 存在某个顶点，不妨设使得屯( ) s2 ，否则，若w ( i = 2 ，3 ，6 ) 都 有d a ；( v i ) 23 ，则i e ( g ；) i = ；d g ；( 地) 石1v 4 + 3 5 1 - 1 0 ，这与i e ( g ；) i ； l e l b ，b ，f 4 ，f 5 ，r ) l 2 6 3 = 9 矛盾接下来同情形1 可知丑甄 y ( 最) 0 = 1 ，2 ，6 ) 使得 z 1 ，勉，y 9 6 ) 为g 的独立集 惰形3 若对于任何q o = l ，2 ，6 ) 都有商g ；慨) = 3 ，分2 种情况讨 论： 1 ) 若存在某个g a 的连通分支，不妨设r ，使得存在x 6 v ( f 6 ) 不 与b “= 1 ，2 ，5 ) 的任何顶点相邻，而由断言1 可知，玉t v ( f d ( i = 1 ，2 ，5 ) 使得 z l ，x 2 ，如 为g 的独立集，从而 z l ，勋，粕) 也为g 的独立集 2 ) 若r 的顶点都与毋( i ，j = l ，2 ，6 且i j ) 中的某些顶点相 邻，因g 是简单图，所以最只可能是完全图蚝，又任意6 阶三正刚镶， 1 9 硕士擘位论文 单图必同构图2 所示的g 5 或g 6 ，这是因为，对于任意6 阶三正则简单图 g ，= ( ，f ) ，v 7 = 口i ，呓，嵋 ，必有a ( g ，) = 2 或3 ，否则，j “= 1 ，2 ，6 ) 使得如，( 叫) 3 若a ( g ，) = 2 ，不妨设 ”i ，呓 为g ，的一个最大独立 集，因如( 嵋) ；3 ，不妨设四( g ，) “= 3 ，4 ，5 ) ，呓e ( g ，) ，此时必有 呓瑶e ( g ，) ，否则 ”i ，呓，诺 为g ，的独立集，这与n ( g ，) = 2 矛盾，同样 因如( 呓) = 3 ，不妨设呓啦，呓呓e ( ) ，此时显然有嵋嵋ee ( g ，) ，否则，因 略( 呓) _ ( 嵋) = 3 ，必有嵋e ( g ，) ，嵋e ( g ，) ( = 4 ，5 ) ，这导致d g ，( 吐) 24 矛盾；不妨设磁曰( g ，) ，此时必有呓e ( g ，) ，这样得到的图同构于g 6 ； 若o ( g ，) = 3 ，不妨设 啦，呓，诟 为g ，的一个最大独立集，则，因如( ”i ) = 3 ， 所以必有。i e ( g 7 ) 0 = 4 ，5 ，6 ) 同理，t 1 5 ，诟叫e ( g ，) 0 = 4 ，5 ，6 ) ，这样 得到的图同构于g 5 将所构造的新图g 还原，于是在g i uy ( 只) 】中取 协，现，粕) ，显然以y ( 冠) ，且 轧z 2 ，x 6 为g 的独立集 综上三种情形知引理4 3 获证 证毕 g 5 图2 2 0 g b 一些图类的上可嵌入性 4 1 定理4 1 的证明 定理4 1 的证明用反证法若g 不是上可嵌入的，则由定理b 知存在边子 集a ，使得g a 满足其所有性质，由引理l ( 3 ) 可知：i c , ( g a ) u c a ( g a ) 23 ， 不妨设f l ，b ，r q ( g a ) u g ( g a ) ，丽结合引理4 3 及独立数的定义 知t3 o ( g 【uy 假) 】) sn ( g ) ，即有3 q ( g ) ，下面分z = c ( g a ) = 3 和 l = c ( g a ) 4 两种情况讨论： 情形1 当l - c ( a a ) = 3 时，因g 是2 - 边连通图，由定理b ( 3 ) 和引 理3 ( 1 ) 可知：i e ，g ) i = 2 ，0 = l ，2 ，3 ) 从而只至多包含两个s ( s o ) 一触 点由于g 是简单图，由引理1 ( 5 ) 得只至少包含一个o - 触点，记弘为 只的m 触点，则由触点的定义可知：戤不与乃( ，j = l ，2 ，3 且t j ) 的任 何顶点相邻，于是有 d g ( z i ) i 矿( 最) i 一1 ，i = 1 ，2 ，3( 1 ) 这样，扛- ，现，黝 是的独立集，由定理条件有 3 i v ( g ) t 一2 d g ( ) i = 1 联合( 1 ) ( 2 ) 有 33 v c c 9 l 一2 d g ( 甄) ( i y ( 只) f 一1 ) = i v ( g ) l 一3 = 1 = l 显然矛盾 情形2 若扛c ( c a ) 4 ，因为冠岛( g a ) u 岛( g ) ( = 1 ，2 ，3 ) ，所 以最至多包含3 个s ( s o ) 一触点，这样只的触点只可能是如下图3 所示 的五种情况 2 1 硕士学位论文 ( 1 )( 2 )( 4 )( 5 ) 图3 ：足的触点可能出现的五种情况 而由引理4 3 可知：弘y ) 0 = 1 ，2 ，3 ) 使得协，锄，铂 为g 的独立集 从图3 不难看出，若存在某个顶点不妨设使得z 。为毋的2 或3 - 触 点，我们总可以找到妨y ( 日) ( 妨。) 且硝是日的o - 触点，即 辑，勋，妇 仍为g 独立集，对x 3 通过类似的方法，总共最多经过三次这样的顶点 轮换，总可以找到y ( 只) ，使得为只的0 或1 一触点，且 西，磊，呓) 为g 的独立集，于是就有 d g ( ) i y ( 只) l ，t = 1 ，2 ，3 由定理条件有 3 i v ( g ) l 一2 d g ( z ：) 1 = 1 又因为f _ c ( g a ) 4 ，且i y ( f ) f 3 ( v f c ( e 4 ) ) ，所以 3 i v ( f , ) tsi v ( c ) l 一3 = 1 由( 1 ) ( 2 ) ( 3 ) 有 33 v c g ) i 一2 如( ) i v ( f , ) i i v ( g ) i 一3 = l- = 1 这又导致矛盾。 。 综合以上二种情况，定理4 1 的前一结论得证 - 2 2 - ( 2 ) 一些图类的上可嵌入性 下面说明下界。l y ( g ) l - 2 ”是最好的，首先注意到这个下界。l y ( g ) i - 2 ”不能被“l y ( g ) | - 3 代替，现构造反例图g 1 ( 见图1 ) 容易验证，g - 是2 边连通的，而且对任何彼此不相邻的三个顶点仇“= l ，2 ，3 ) ，都有 3 乏二d g 。( 弘) 6 = i v ( c 1 ) l 一3 穹l 然而，若取a = e ，e 2 ，e 3 ) ，则有 “g l a ) 4 - b ( g 1 a ) 一i i l = 2 由引理2 知，( g 。) 2 ，所以g - 不是上可嵌入的，从而定理4 1 的后一结 论得证 注记2由定理4 1 易证得：当引理4 1 ( 1 ) 中条件满足时，结论显然成立 证毕 2 3 硕士学位论文 4 2 定理4 2 的证明 定理4 2 的证明用反证法若g 不是上可嵌入的，则由定理c 知存在 边子集a ，使得g a 满足其所有性质，由引理1 ( 4 ) 可知：l 伤( g a ) i 6 ， 不妨设日，乃，r 岛( g ) ，而结合引理4 3 及独立数的定义知：6 a ( a uy ( 只) 】) o ( g ) ，即6 a ( g ) ，因为只，尼，f 6 仍( g a ) ，所以只 至多包含3 个8 ( s o ) 触点，这样只的触点只可能是如图3 所示的五种 情况而由引理4 3 可知；j 翰y ( e ) 0 = 1 ，2 ，6 ) 使得扛1 ，。2 ，z 6 为g 的独立集从图3 不难看出，若存在某个顶点不妨设轧使得现为 r 的2 或3 触点，我们总可以找到吐y ( f 1 ) ( 硝z 。) 且妨是目的o - 触点，即 研，物，) 仍为g 独立集，对a = 2 ，3 ，6 ) 通过类似的方 法，总共最多经过六次这样的顶点轮换，总可以找到y ( 日) ，使得 为只的0 或1 一触点，且 ，吐，) 为g 的独立集，于是就有 如( ) i y ( e ) i ， = 1 ，2 ，6( 1 ) 由定理条件有 i v ( a ) l + 1 d g ( ) ( 2 ) i = 1 由( 1 ) ( 2 ) 有 i v ( a ) l + 1 d g ( ) i v ( f ) i i v ( g ) i t = li = l 显然矛盾从而定理的前一个结论得证 其中，下界“i y ( g ) i + 1 ”不能改进为“l y ( g ) i ”，否则将有反例g 2 ( 见 图1 ) 容易验证g 。是3 _ 边连通的三正则简单图，所以对任何不相邻的六 个顶点地0 = 1 ，2 ，6 ) ，都有 6 屯( 忱) z1 8 = i v ( a d l 暑1 2 4 一些图类的上可嵌入性 然而，若取a = e 1 ，e 2 ，c 9 ) ，则有 g 2 a ) + b ( g 2 a ) 一i a i 一1 = 2 由定理b 知，f ( g 2 ) 2 ，所以g 2 不是上可嵌入的，这就得到了定理4 2 的 后一个结论 g 7 图4 注记3 ( 1 ) 由定理4 2 易证得：当引理4 1 ( 2 ) 中条件满足时，结论显然成 立 ( 2 ) 现在我们可以找到一个用引理4 1 不能判定，但用定理4 2 可 以判定是上可嵌入的图g t ( 见图4 ) 一方面，图g ，为3 - 边连通简单图，且在g 7 中任意六个不相邻的 顶点的度和大于等于1 9 ，即大于等于i y ( g 7 ) i4 - l ，根据定理4 2 得g 7 是上 可嵌入的； 另一方面，对图g 7 中任意两个不相邻的顶点z ，y ( x ，g ，钆n 2 ，o 。) ， 都有 如( 。) 4 - d g , ( y ) ：6 掣 显然用引理4 1 不能判定图g ，是上可嵌入的 证毕 2 5 一些图类的上可嵌入性 第五章。独立数，围长与上可嵌人性 由定理a 知，研究图g 的上可嵌入性，即研究图g 的b e t t i 亏数f ( g ) 是否小于或等于1 而f ( g ) 的大小图g 的一些参数确定下来，如h u a n g yq ，l i uy p 在文献【2 0 】中讨论了f ( g ) 与独立数，围长的关系，得出了如 下结果： 引理5 1 【2 0 1 ：设g 为图，则f ( g ) 翥倍； 引理5 2 【2 0 j ：设g 为图，则啊( g ) 譬，其中m = 坐g ( o 盟) - i 本章受文献【1 9 】和文献【2 0 j 的启发，结合了图的连通度，独立数，国 长，将文献【1 9 】中的结果进行改进和推广，得到了如下定理，即本章的 主要结果： 定理5 1 设g 是一个1 一边连通简单图，且不含完全子图飓，若o ( g ) 3 ， 则g 是上可嵌入的，且在这种意义下，独立数上界是最好的 定理5 2 设g 是2 - 边连通简单图，且不含完全子图娲，若a ( g ) 5 ，则g 是上可嵌入的，且在这种意义下，独立数上界是最好的 定理5 3 设g 是一个3 _ 边连通简单图，且不含完全子图娲，若a ( g ) 1 0 则g 是上可嵌入的，在这种意义下，独立数上界是最好的 在证明主要结果之前，先证明如下引理： 引理5 3 设h 为g 的点导出子图，则有n ( g ) n ( h ) 2 7 硕士学位论文 证设叱忱，( 日) 为h 的最大独立集，则由定义1 ，地，v a ( h ) 也 是g 的一个独立集，不然，则存在v l 与是相邻的0 1 ，j a ( 日) ) 又因为h 为g 的点导出子图，则佻与v j 在h 中也是相邻的，矛盾从 而o ( g ) o ( 日) 证毕 由于在图g 中增加一条边，独立数最多减少1 ，从而有如下引理： 引理5 4 t 2 0 1 ：设g 为图，e e ( g ) ，若g e 为连通图，则n ( g ) o ( g e ) o ( g ) + 1 2 8 一些图类的上可嵌入性 5 1 定理5 1 的证明 定理5 1 的证明用反证法设g 不是上可嵌入的，由定理c 知，存在边 子集a e ( g ) 使得c a 的所有连通分支f 1 ，易，最( f = c ( g a ) ) 满足定 理b ( 1 ) 一( 4 ) ；又g 是1 一边连通的，由引理1 知i 耳只，g ) i t ( i = 1 ，2 ，1 ) ，k “g a ) 2 任取两个连通分支r ，局，设如，岛) = e = v t v 2 ，由引理1 ( 5 ) 知 i y ( 凡) i 4 ，l v ( f 2 ) l 4 ，则日中总存在两点 l ，她口l ，使得t ，l ，耽在r 中不相邻，同理，马中总存在两点w 3 ， i v 4 v 2 ，使得i u 3 ，坝在f 2 中也不 相邻，从而( 叫l ，毗，耽，地为g 的独立集，由引理5 3 知，q ( g ) 24 ；当 l e o ( f , ，f 2 ) i = 0 时，同样有a ( g ) 4 ，这样，与题设d ( g ) 3 矛盾 注记4 这里，独立数上界3 是最好的，由图5 中反倒g 8 知o ( g ) = 4 时，g 8 不是上可嵌入的另外，定理中条件。l - 边连通简单图”是必要 的，否则，改为“1 一边连通图”时，g 不一定是上可嵌入的，见图5 中 反例g 9 ，显然g 9 也不是上可嵌入的 证毕 口 图5 2 9 硕士学位论文 5 2 定理5 2 的证明 定理5 2 的证明设g 不是上可嵌入的，由定理c 知存在边子集a e ( g ) ， 使得g a 的所有连通分支日，易，f , q = c ( g a ) ) 满足引理c 0 ) 一 ( 4 ) ；又由引理1 知：i y ( 只) i 4 | e ( f ig ) i 2 ；c a ) 3 ；c ( g a ) l 岛( g a ) ug ( g a ) i 3 任取g a 中的3 个连通分支，不妨记为 只，咒，乃记h 1 = g 【u 嫠。y ( r ) 1 下面分两种情形进行讨论。 情形1 当l l h ( f l ，f 2 ，兄) l = 3 时，点h ( r ，玛，尼) 只可能出现以下4 种情况，见图6 图6 ( 2 ) ( 4 ) 子情形1 1 若忍( 一l ，2 ，3 ) 都包含两个1 一触点( 即圈6 ( 1 ) ) 这时在 3 0 - 一些图类的上可嵌入性 r o = l ，2 ，3 ) 中，分别取s l ，t 1 y ( 日) ，且s l ，t l u 2 ；s 2 ，t 2 y ( 玛) ，且 s 2 ，t 2 地；8 3 ，t 3 y ( 玛) ，且s 3 ，t a 也；同时满8 与如o = i ，2 ，3 ) 不相邻显 然， s - ，t t ，8 2 ，如，如，b ) 构成图矾的一个独立集，有n ( 研) 6 子情形1 2 若r “= 1 ，2 ，3 ) 中有一分支包含一个2 触点，其余两分 支各包含两个1 触点( 见图6 ( 2 ) ) 用类似子情形i i 中的方法，在y ( f 1 ) 中可找到两个不等于u ，且不相邻的两点s 。，t 。；在y ( 岛) 中可找到两个不 等于硼l ，且不相邻的点s 2 ，t 2 ；在y ( r ) 中可找到两个不相邻的点8 3 ，3 显 然，s l ，t 1 ，s 2 ，如，8 3 ，3 也构成图凰的一个独立集，有a ( n 1 ) 之6 子情形1 3 若r 0 = i ，2 ，3 ) 中有两个分支包含一个奢触点，一个分 支包含一个i 一触点( 见图6 ( 3 ) ) 易证a ( h i ) 6 ，方法同子情形i i 子情形1 4 若足“= 1 ，2 ，3 ) 中三个分支均包含一个2 - 触点时，易证 o ( h i ) 6 ，方法同子情形i i p p ( 1 ) ( 3 ) 图7 3 1 ( 2 ) ( 4 ) 硕士学位论文 情形2 当l ( 日，玛，f s ) l s2 时，e 日。( 乃，马，b ) 可能出现以下4 种情况， 见图7 ： 子情形2 1 若只“= 1 ，2 ，3 ) 中只有m 触点，见图7 ( 1 ) ，在r 0 = 1 ，2 ，3 ) 中各找出两个不相邻点s l t ；构成凰的一个独立集，从而a ( 玩) 6 子情形2 2 若最“= 1 ，2 ，3 ) 中有两个分支都有且只有一个1 一触点， 另一分支中只有0 - 触点，见图7 ( 2 ) ，在日中找到两个不相邻的点s t ，t l ；在 尼中找到两个不等于”，且不相邻的点s 3 ，t 3 ；在乃中任找两个不相邻的点 s 2 ，t a ，这样， s l ，t l ，s