（运筹学与控制论专业论文）关于图的上可嵌入性研究.pdf

摘要 自n o r d h a u s ，s t e w a r t 和w h i t e 1 】引进最大亏格以来，图的上可嵌入性 至今倍受人们的注意虽然x u o n g 2 ，l i u 3 】和n e b e s k y 4 】分别提供了不同 的确定图的上可嵌入性的充要条件，但对于什么类型的图是上可嵌入的 仍尚知不多 如果一个图的最大亏格能够取到最好的上界 z ( g ) 2 j ，则这个图就是 上可嵌入的近些年来，许多图论学者都在研究图的上可嵌入性与图的 各项参数之间的关系，并得到了一些上可嵌入图类本文结合图的圈中 顶点度，支配集，顶点a 划分得到了几类上可嵌入图具体内容如下 第一章和第二章，介绍了图的上可嵌入理论的背景以及所需要掌握 的基本概念和定理 第三章，结合圈中顶点最大度，得到了两类上可嵌入图 第四章，结合图的支配集，得到了两类上可嵌入图 第五章，结合图的顶点a 划分、顶点的度及其边连通性等条件确定 了一类上可嵌入图类，从而将已有这方面的结果作了较大的推广，完整 地刻画了这类图的上可嵌入情况 在结语中，介绍了关于上可嵌入性理论的研究前景和作者今后的工 作 关键词：上可嵌入；最大亏格；b e t t i 亏数；支配集；a 一划分 a b s t r a c t s i n c et h ei n t r o d u c t o r yi n v e s t i g a t i o no fm a x i m u mg e n u sb yn o r d h a u s ，s t e w a r t ，a n d w h i t e 1 ，t h eu p p e re m b e d d a b i l i t yo fg r a p h sh a sb e e nd e v e l o p i n g8 0f a r a l t h o u g h x u o n g 2 ，l i u 3 】a n dn e b e s k y 4 h a v er e s p e c t i v e l yp r o v i d e dd i f f e r e n tn e c e s s a x ya n d s u f f i c i e n tc o n d i t i o n so nt h eu p p e re m b e d d a b i l i t yo f 口印1 1 j s ，w ek n o wl e s sa b o u tw h a t c l a s s e so fg r 印1 1 sa r eu p p e re m b e d d a b l e i ft h eu p p e rb o u n do nt h em a x i m u mg e n u so fag r a p hgc a l la r r i v ea tt h e b e s tv a l u e 垆( c ) 2 j ，t h e nw ec a l ls u c hag r a p hgi su p p e re m b e d d a b l e i nr e c e n t y e a r s ，m a n yg r a p h st h e o r ys c h o l a r sr e s e a r c ho nt h er e l a t i o n sb e t w e e np a r a m e t e r s a n dt h eu p p e re m b e d d a b i l i t yo fg r a p h s t h e yh a v ea t t a i n e dm a n yc l a s s e so fu p p e r e m b e d d a b l eg r 印h s i nt h i sp a p e rw ep r o v i d es o m en e wc l a s s e so fu p p e re m b e d d a b l e 伊a p h sb yc o m b i n i n gw i t ht h em a xd e g r e eo fv e t e xi nc y c l e ，t h ed o m i n a t ev e r t i c e s s e to fg r 印l l s ，a n dt h ec o n t i d i o n so fa p a r t i t i o n t h ed e t a i l sa r ea sf o l l o w s i nc h a p t e ro n ea n dt w o ，w ei n t r o d u c et h eb a c k g r o u n da n dr e q u i r e dk n o w l e d g e o ft h eu p p e re m b e d d a b i l i t yo fg r a p h s ，a n dg i v ep r i m a r yc o n c e p t i o n sa n dt h e o r e m s i nc h a p t e rt h r e e ，c o m b i n i n g 祈t ht h em a xd e g r e eo fv e t e xi nc y c l e ，w ea t t a i n t w oc l a s s e so fu p p e re m b e d d a b l eg r 印h 8 i nc h a p t e rf o u r ，c o m b i n i n gw i t ht h ed o m i n a t ev e r t i c e ss e to fg r a p l l 8 ，w ea t t a i n t w oc l a s s e so fu p p e re m b e d d a b l eg r a p h s i nc h a p t e rf i v e ，c o m b i n i n gw i t ha p a r t i t i o n ，d e g r e eo fv e r t e xa n de d g e - c o n n e c t i v i t y , w ea t t a i ns o m en e wc l a s s e so fu p p e re m b e d d a b l eg r a p h s t h u sw eg e n e r a l i z ef u r t h e r t 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 ee n t i r e l ys u c hu p p e re m b e d d a b l eg r 印h 8 i nt h ee n d ，w ei n t r o d u c et h er e s e a r c h i n gp r o s p e c to ft h eu p p e re m b e d d a b i l i t y 0 fg r 印l l sa n ds t a t ea u t h o r sn e x tw o r k k e yw 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 ；t h ed o m i n a t e v e r t i c e ss e t ；a - p a r t i t i o n i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全 意识到本声明的法律后果由本人承担 学位论文作者签名：膨；篆蜂 仲多月d 日 i 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分 内容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密 ( 请在以上相应方框内打q 、力) 作者弥侈1 螺 导师签 石乃l 日腑雌知j f j 日 日期珈年6 月，护日 关于图的上可嵌入性研究 1 引言 图论是组合数学的一个重要组成部分，在最近的几十年里，它已经 发展成为数学的一个重要分支由于图论本身的魅力和其在信息社会中 一些学科领域诸如计算机，运筹学，系统工程以及物理学、电子学、化 学、通讯科学、生物遗传学、社会学等学科都有广泛应用，因此，越来越 受到科学界尤其是数学界的重视和关注由于组合数学，代数学，拓扑学 以及概率方法的结合，现代图论除了传统的研究领域外又扩大到包括代 数图论，拓扑图论，以及随机图论等分支在内的多个新的领域，促进了 图论的发展 拓扑图论是目前国际上一个非常活跃的图论分支，将图论与拓扑学 理论结合起来，极大地丰富了图论和拓扑学本身的研究，其中对图的拓 扑参数一最大亏格的研究又是一个十分重要的课题之一自从上世纪七 十年代初，由e n o r l d a u s ，b s t e w a r t 和a w h i t e 1 1 提出图的最大亏格以来， 很多图论学者都投身于这方面的研究，随着对其研究的深入，它越来越 多地与其它数学分支相互交叉，相互影响，极大的促进了亏格理论的发 展目前，关于图的最大亏格的研究主要表现在如下几个方面： ( 1 ) 特征结构 上世纪七十年代末，n h x u o n g 2 1 借助于图的支撑树上的补图，通过 引进b e t t i 亏数，给出了图的最大亏格的表示定理国内刘彦佩教授【3 】3 通 过应用确向树理论方法，证明了一个图是上可嵌入的当且仅当存在2 重 图上的标准e u l e r 圈，给出了一些图的嵌入的可约化模型，也构造性地解决 了图的不可定向最大亏格的存在性问题上世纪八十年代初，l n e b e s k y 【4 】 用图的去边子图给出了图的另一个b e t t i 亏数的组合表达式由此，黄元 秋教授和刘彦佩教授【5 】研究了图不是上可嵌入的充要条件 n h x u o n g ，j c h e n 和j l g r o 豁【6 】【7 】【8 】等人的工作表明对图的最大亏格的研究往往可 以转化为一个特殊的3 正则图的情形黄元秋教授和刘彦佩教授 9 】证 1 硕士学位论文 明了一个孓正则图的最大亏格等于其最大不可分离独立数，在结构上给 出3 - 正则图上可嵌入的充要条件另外，黄元秋教授和刘彦佩教授【1 0 通过引进图的扩张运算，研究了扩张运算与图的b e t t i 亏数之间的内在联 系，揭示了图的最大亏格与图的2 因子的某些联系然而，在探求图的 最大亏格的结构特征上，仍有广阔的前景 ( 2 ) 上可嵌入性 一个图是上可嵌入的表明其最大亏格可取到最好的上界虽然在早 些年x u o n g 2 ，l i u 3 】和n e b e s k y 4 】分别提供了不同的确定图的上可嵌入性 充要条件，但对于什么类型的图是上可嵌入的尚知不多学者k u n d u 1 l 】 最早证明了所有垂边连通图是上可嵌入的，j u n g e r m a n 1 2 1 在他的论文中 证明了确实存在3 - 边连通而非上可嵌入的图于是这方面的研究就只需 讨论什么样的k ( k 3 ) 一边连通图是上可嵌入的目前，结合图的其它参数 来讨论图的上可嵌入性已经有了许多结果例如l n e b e s k y 1 3 1 4 1 5 1 证明 了半局部连通图及2 局部连通图均是上可嵌入的m s k o v i e r 1 6 ，h u a n g - l i n f u 和m i n - c h e nt s c a i 1 7 分别考虑直径为2 和3 的图的上可嵌入性 m s k o v i e r ，r n e d e a l 1 8 1 证明了一个图嵌入曲面上使得每个面度的大小不 超过4 ，则该图是上可嵌入的，并提出了一个放松条件到每个面度的大小 不超过5 的猜想前些年，黄元秋教授和刘彦佩教授 1 9 】证明了这个猜 想近期，国内已有很多学者结合图的点和边连通性、直径、半径、围 长、顶点度、最小度、2 因子、独立数、匹配数、顶点划分等条件，得到 一些新的上可嵌入图类这些结果可以参阅文献 2 0 - 3 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 考虑了 2 关于图的上可嵌入性研究 3 - 边连通( 非简单) 图的情形黄元秋教授推广了上述工作，对任意k - 边 连通( 非简单) 图，给出了由图的最小度所表达的图的最大亏格的下界表 达式，证明了最小度趋向无穷大时，最大亏格趋近最好的上界最近，黄 元秋教授研究了图的最大亏格与图的余色数及团的关系，利用h e a d w o o d 着色定理揭示了图的最大亏格与图的亏格之间的联系这方面的文献可 以参阅f 纵1 】 本文在以上所述学者工作的基础上研究了图的上可嵌入性，分别结 合图的圈中顶点度，支配集，顶点a 划分得到了几类上可嵌入图，丰富 了这方面的相关结果具体安排如下 第二章，2 1 介绍了本文所需的一些基本概念，2 2 列出了本文结 果证明过程中用到的几个基本定理与事实 第三章，结合圈中顶点度，得到了两类上可嵌入图3 1 证明了一 般的参边连通简单图在其圈中顶点度满足一定条件后，该图就是一个上 可嵌入图3 2 讨论的则是2 - 边连通的简单二部图 第四章，结合图的支配集，得到了两类上可嵌入图4 1 讨论以轮 为支配集的上可嵌入图，4 2 讨论了以完全冬部图为支配集的上可嵌入 图 第五章，引入图的顶点a 划分，也同样得到了几类上可嵌入图，并 推广和深化了早先一些学者的结果 结语部分，介绍了关于上可嵌入性理论的研究前景和作者今后要努 力的研究方向 3 关于图的上可嵌入性研究 基本概念和相关定理 2 1 基本概念 本文考虑的图，若无指明均指有限无向的连通图其他未加说明的术 语和记号均同文献 4 2 】【4 3 】个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，惦) ， 其中v ( c ) 是非空的顶点集，e ( g ) 是不与v ( c ) 相交的边集，而惦是 关联函数，它使g 的每条边对应于g 的无序顶点对1 v i = n 称为图g 的阶设伽e ，则称顶点u ，t ，为相邻顶点，否则，称缸，u 为非邻顶点 假设y 是y 的一个非空子集，以为顶点集，以两端点均在中 的边的全体为边集所组成的子图，称为g 的由y 7 导出的子图，记为a v 1 g 的两个顶点t t ，u 称为连通的，如果在g 中存在从乱到钞的路连通是 顶点集v ( g ) 上的一个等价关系于是存在v ( g ) 的一个分类，把v ( v ) 分 成非空子集，k ，k ，使得两个顶点u ，秒是连通的当且仅当它们属于 同一个子集k 子图g f 】，g 【】，g 【蝈称为g 的连通分支若g 只有 一个分支，则称g 是连通的；否则，称g 是不连通的若v ( a ) 的子集 y 使得v ( a ) 一v 不连通，则y 7 称为v ( g ) 的顶点割k 顶点割是指有k 个元素的顶点割若g 至少有一对相异的不相邻顶点，则g 所具有的k 顶点割中最少的k ，称为g 的连通度，记为k ( g ) 若k ( g ) k ，则称g 为舡 连通的对v ( g ) 的子集s 和s 7 ，用【ss 7 】表示一个端点在s 中，另一个 端点在中的所有边的集合所谓g 的边割是指形为【s 刚的e ( g ) 的 子集，其中s 是v ( a ) 的非空真子集一个k 边割是指有k 个元素的边 割若g 是非平凡的，g 的所有k 边割中最少的k ，称为g 的边连通度， 记为( g ) 若( g ) k ，则称g 为舡边连通的称图日为图g 的子图， 如果v ( h ) 冬y ( g ) ，e ( h ) 冬e ( g ) ，并且妇是惦上的限制g 的生成子图 是指满足v ( h ) = v ( c ) 的子图日不含圈的图称为无圈图，连通的无圈图 称为树；g 的生成树是指g 的生成子图，它同时又是树设d 是g 的一 5 硕士学位论文 个点子集，即d y ( g ) ，若g 中每一点或者在d 中，或者与d 中某一点 邻接，则称d 是g 的一个支配集，g 中点数最少的支配集称为最小支配 集；最小支配集中点的数目称为支配数，记为r n ( a ) 曲面指一个连通紧致2 - 维闭流形曲面分为定向曲面与不可定向曲 面一个可定向曲面s 是由一个球面添上h 个环柄得到不可定向曲面 是由一个球面挖掉k 个圆盘而分别补上m s b i u s 带得到其中，岛称为 球面，毋称为环面，岛称为双环面；l 称为射影平面，2 称为克莱 因瓶 一个图g 在曲面s 上的一个开二胞腔嵌入是指g 能画在s 上使得 边与边之间除顶点外不再相交，且在s 上去掉g 的顶点与边之后的每个 连通分支与开圆盘同胚此时，每个开圆盘称为图g 在s 上的一个面 注意到，不连通的图在任意曲面上不存在2 胞腔嵌入图g 的最大定向 亏格( 简称为最大亏格) ，用伽( g ) 表示，是指最大的整数k 使得g 能2 - 胞 腔嵌入亏格为k 的定向曲面s 上图的定向亏格，用，y ( g ) 表示，( 或不可 定向亏格用彳( g ) 表示) 是指最小的整数k 使得g 在亏格为k 的定向( 或 不可定向) 曲面s 上有2 胞腔嵌入设g 是一个具有个点，( 条边的 图，若g 在一个亏格为g 的( 定向或不定向) 曲面有2 胞腔嵌入，且具有 7 - 个面，则由e u l e r 公式一e + r = 2 2 9 ( s 定向) 或一e + 7 = 2 一g ( s 不 定向) ，因为任何一个图在任意曲面上的2 - 胞腔嵌入中至少有一个面，由 最大亏格的定义及e u l e r 公式，即有伽( g ) 【竽j ，其中z ( a ) = e t ，+ 1 称为图g 的b e t t i 数，即圈秩数( 对任意实数z ，h 表示不超过z 的最大 整数) 同时，若7 m ( g ) = 【华j 称图g 是上可嵌人的 对于任意集合x ，用l x l 表示x 的基数；设y 为图g 的任意边子集， g y 表示从g 中去掉y 中的所有边所得到的图；设g 为连通图，且t 为g 的一棵生成树，记f ( g ，t ) 表示g e ( t ) 中边数为奇数的连通分支个 数，我们称( g ) = 吨n ( g ，t ) 为g 的b e t t i 亏数，这里m i n 取遍g 的所有生 成树t 由定义，对g 的任意生成树丁，均有( g ，t ) 三f ( g ) - - z ( a ) ( m o d2 ) 6 关于图的上可嵌入性研究 设a e ( g ) 为图g 的边子集，记号c ( g a ) 及b ( v a ) 分别表示g a 所有连通分支数及g a 的具有b e t t i 数为奇数的所有连通分支数设 r ，b ，最( 七2 ) 为图g 的k 个不相交的连通子图，记号e ( r ，易，r ) 表示g 中2 个端点分别在2 个不同的只和f j 0 歹，1 i ，歹k ) 中的边 集；另外，对g 的任意子图f ，记号e ( eg ) 表示g 中一个端点属于尸，而 另一个端点不属于f 的边集 本文将一个2 部图记为g = x ，y ；e ) ，其中v ( g ) = xuve ( g ) = e = z ! i z x ，y y 对任意的a e ( g ) ，只为g a 的一个连通 分支，记r = ( x ，m ；毋) ，i = 1 ，2 ，k 其中y ( 尻) = 五uy , ，e ( x ，g ) = e = x y l x 咒，y 譬y ( r ) ) ，e ( m ，g ) = e = x y y k ，z 譬y ( 冠) ，且 e ( e ，g ) = e ( 五，g ) u e ( k ，g ) 将图称为多重完全图，若它有一个基础图为完全图；将图称为多重 完全2 部图，若它有一个基础图为完全2 - 部图图g 的顶点d 划分 是指：g 的一个顶点划分 ，k ，使得每个g m 为多重完全图 ( 1 i 七) ；图g 的顶点b 划分是指：g 的一个顶点划分 ，k ) ， 使得每个g 瞰】为多重完全2 部图( 1 i 七) ；图g 的顶点a 划分是指： g 的一个顶点划分 ，圪) ，使得每个g 【吲为多重完全图或多重完 全二部图( 1 i 七) 7 硕士学位论文 2 2 相关定理与事实 图的上可嵌入性，是由一个图的最大亏格决定的前些年，文献【3 】 给出了最大亏格的计算公式和判断图是上可嵌入的充要条件 定理i 【3 】设g 为图，则 1 ) 伽( g ) = 华； 2 ) g 是上可嵌入的当且仅当( g ) 1 由定理i 知图的上可嵌入性和最大亏格由b e t t i 亏数( g ) 确定对 一个图g 的最大亏格的研究可转化为对参数( g ) 的研究，关于( g ) 文 献【4 】给出了如下组合表达式： 定理l i 【4 】若g 是一个图，则f ( g ) 2 m c e s ( x g ) c ( g a ) + 6 ( g a ) 一i a i 一1 ) 许多关于上可嵌入性研究的文献都用到了以下定理，也就是文献【5 j 给出的非上可嵌入图所具有的结构特征： 定理【5 】设g 为图，若g 不是上可嵌入的，即( g ) 2 ，则存在g 的边子集a 满足下列性质： ( 1 ) c ( g a ) = b ( a a ) 2 ，且对g a 的任意连通分支f ，都有 f l ( f ) = 1 ( r o o d2 ) ； ( 2 ) 对于g a 的任意连通分支f ，f 是g 的点导出子图； ( 3 ) 对于g a 的任意七忙2 ) 个不同连通分支只，b ，r ，有 i e ( 日，f 2 ，最) i 2 k 一3 ，特别的，当k = 2 时，i e ( f 1 ，兄) l l ； ( 4 ) ( g ) = 2 c ( g a ) 一i a i 一1 在定理的条件和结论下，很容易得到以下事实： 事实1 对g a 的任意连通分支f ，若g 是缸边连通的( k 1 ) ，则 i e ( eg ) i 七； 8 关于图的上可嵌入性研究 事实2 当g 是无环连通图时， i y ( 只) i 2 ，当g 是简单连通图时， i v ( f o i 3 ；特别的，当g 是简单连通2 - 部图时，i v ( f o i 4 ，且i x i 2 ，l k i 2 ； 土 事实3 当g 是简单连通图时，2 a l = el e ( f i ，g ) i ；特别的，当g 是 = 1 七蠡 简单连通二部图时， i a i = i e ( 五，g ) i = i e ( m ，g ) i ； i = li = l 事实4 必存在某个f c ( c a ) 使得1 l e ( f g ) i 3 9 关于图的上可嵌入性研究 3 图的上可嵌人性与圈中顶点度 结合图的一些参数来研究图的上可嵌入性，近年来成为许多图论学 者的研究方向目前，已有很多文献研究了最大亏格与图的点或边连通 性、直径、半径、围长、顶点度、最小度、2 - 因子等之间的关系关于 顶点度与图的上可嵌入性或最大亏格的关系研究，已经有部分学者做了 一些工作例如文献【2 2 】从非邻节点度和出发研究了图的上可嵌入性； 文献 2 5 】得到了二部图的上可嵌入性与相关顶点度和的关系；而文献【2 6 】 得到了范条件图是上可嵌入的本章则用图的圈中顶点最大度来研究图 的上可嵌入性，得到了一些新的结果 3 1 一般的2 - 边连通简单图 首先，我们讨论一般的二边连通简单图，根据第二章中定理关于 非上可嵌入图的充要条件，我们得到以下定理： 定理3 1 设g 是二边连通简单图，若对g 中任意圈c ，存在点z c 满足： d ( z ) 下i v ( c ) l + 1 ， 则图g 是上可嵌入的，且不等式的下界是不可达的 证明反证法假设g 是不能上可嵌入的，则存在边集a e ( g ) 满 足定理中所有性质令只，b ，最( 七= b ( g a ) ) 是g a 的所有连通 分支因为g 是二边连通图，所以i e ( r ，g ) i 2 , i = 1 ，2 ，k 由定理 ( 3 ) 知k 3 由事实2 知i y ( r ) i 3 ( 1 i 七) ，又因p ( 只) 为奇数，且g 为简单 图，易知足中必含一个圈，记为c ；i 由条件知必存在一点戤g 满足 d ( x i ) 峰掣+ 1 因为甄是分支r 内的一个点，所以分支e 内最多有 1 1 硕士学位论文 i y ( 只) i 1 个其它顶点与毛相邻；而e ( 只，g ) 表示g 中一个端点属于e ， 另一个端点属于其他分支的边集，又由定理( 3 ) 知任意两个分支最多有 一条边相连，则顶点甄最多与l e ( f i ，g ) 1 个分支有边相连故 对所有分支求和得 即 d ( x i ) i y ( e ) i 一1 + i e ( f i ，g ) i k知k d ( x t ) ( i y ( e ) i - 1 ) + i e ( 只，a ) l ， i - - - - ii = lt = 1 k七k e d ( x i ) l y ( e ) i k + l e ( f i ，g ) i ， i = li = 1i = l k七 其中l y ( r ) i = i v ( a ) 1 由事实3 知i e ( 只，g ) i = 2 川，并且i a i = i - - - - ii = l i e ( f 1 ，b ，f k ) i 2 k 一3 ，故有 七 d ( x i ) i v ( c ) l k + 2 ( 2 k 一3 ) ( 1 ) i = 1 由条件又有d ) 甲+ 1 ，则 毒堆抄( 掣娜 ( 2 ) l = l 由不等式( 1 ) 和( 2 ) 得： ( i v ( a ) 1 + 1 ) 七 l y ( g ) l k + 2 ( 2 七一3 ) ( 蠡3 ) ， 由上式变形可得 ( k 一3 ) i v ( a ) l 6 k 一1 8 ( k 3 ) 当k = 3 时，由上式得到一个矛盾不等式0 o ； 当k 4 时，由上式解得i y ( g ) i ”不能用冀打代替我们可以通过构造 下面的图类来说明这一点 g i 图3 1 ( a ) y g 2 图3 1 ( b ) 图3 1 图3 2 g 3 图3 1 ( c ) 在图3 1 中，g l ，g 2 ，g 3 是三个同构的图，它们均由2 m + l ( m = 0 ，1 ，2 ，) 个三 圈构成每个图的所有三圈都有一个公共顶点，我们将其称为。支点力 1 3 硕士学位论文 如图3 1 所示，三个图的支点分别记作z ，y 现在，我们依次连接三个 支点，得到一个图g 4 ( 见图3 2 ) 在g 4 中，l y ( g 4 ) i = 3 ( 2 ( 2 m4 - 1 ) 4 - 1 ) = 1 2 m4 - 9 , d ( x ) = d ( y ) = d ( z ) = 2 ( 2 m4 - 1 ) 4 - 2 = 4 m4 - 4 = v l k l 3 q d l4 - 1 ，容易看出图 g 4 的每一个圈中都至少存在一个度为。v l 业q 。_ d i4 - 1 井的顶点下面再说明 g 4 不是上可嵌入的取g 4 中边集a ，= z ! ，y z ，z z ) ，g 4 a l 有三个分支， 且不难观察到每个分支的b e t t i 数为奇数，即c ( g 4 a 。) = b ( g 4 a 。) = 3 由定理知 f ( g 4 ) c ( g 4 a 1 ) + 6 ( g 4 a 1 ) 一1 月l i 一1 = 2 从而g 4 不是上可嵌入的所以从图g 4 可得不等式中。 ”不能用q ” 来代替，也就是说定理中的界。甲4 - 1 丹是不可达的另外，由于m 可 以取0 或任意正整数，我们可以得到无穷多个这样的图例口 由定理3 1 很容易得到以下推论： 推论3 1 设g 是2 边连通简单图，若g 的最小度6 ( g ) 甲4 - 1 ， 则g 是上可嵌入的 3 22 - 边连通简单2 部图 在定理3 1 中我们讨论了一般的2 边连通简单图，本节我们讨论一 种特殊情况，也就是当这个图是简单二部图时，得到下面的一个定理和 简单的推论 定理3 2 设g = 【ky ；e ) 为简单2 部图，且是2 - 边连通的i x l = m ，i y i = n ( m ，n 3 ) ，若对g 中任意圈c ，存在点z c 且z x 满足： d ( z ) 詈“ 则图g 是上可嵌入的，且不等式的下界是不可达的 1 4 关于图的上可嵌入性研究 证明反证法假设g 是不能上可嵌入的，则存在边集a e ( g ) 满 足定理中所有性质令日，而，r ( 七= b ( c a ) ) 是g a 的所有连通 分支因为g 是一个二部图，所以g a 的每一个连通分支只也是一个 参部图记只= ( x ，k ；日) ，i = 1 ，2 ，七y ( r ) = 五u m 由定n i i i ( 3 ) 知 k 3 由事实2 知1 x i l 2 ，i k i 2 ，又因p ( r ) 为奇数，且g 为简单图，易知 r 中必含一个圈，记为g 由条件知必存在一点g 满足d 慨) 詈+ 1 因为置是分支r 内点集五中的一个点，所以分支e 内最多有l 1 个y 型顶点与戤相邻，而e ( x i ，g ) 表示g 中一个端点属于x ，另一个端点属 于其他分支的边集则顶点毛最多与l e ( x i ，g ) 1 个分支有边相连故 d ( x i ) si k i + i e ( x ，g ) i ， 对所有分支求和得 知 kk d ( 而) i y , i + i e ( x t ，c ) j ， i = 1i - - - - li = 1 其中el k i = i y i = 礼由事实3 知i e ( 置，g ) j = l a i ，且l a i = i e ( r ，f 2 ，r ) i 2 k 一3 ，故有 d ( 黾) n + ( 2 k 一3 ) ； ( 3 ) = l 由条件又有d ( 黾) 署+ 1 ，则 七 d ( z i ) ( ；+ 1 ) 七 ( 4 ) 由不等式( 3 ) 和( 4 ) 得： ( 三+ 1 ) 七 n + ( 2 七一3 ) ( 七3 ) ， 由上式变形可得 ( k 一3 ) - 3 k 一9 ( k 3 ) 1 5 硕士学位论文 当k = 3 时，由上式得到一个矛盾不等式0 o ； 当k 4 时，由上式解得n 一不能用“一代替和定理3 1 的证明类似，我 们可以通过构造下面的图类来说明这一点 a g 5 剪1 图3 3 ( a ) z 2 1 y 2 t j 6 图3 3 ( b ) 黝 蜘 ( i 7 图3 3 ( c ) 图3 3 1 6 关于图的上可嵌入性研究 在图3 3 中，g 5 ，g 6 ，g 7 是三个同构的2 部图，它们均由2 m + l ( m = 0 ，1 ，2 ， ) 个四圈构成每个图的所有四圈都有一条公共边，我们将其称为“支 边斗如图3 3 所示，上面三个图的支边分别记作x l y 。，x 2 y 2 ，x 3 蜘现在，我 们依次连接_ y a x 2 骨、。y 2 x a 力、_ y s x l ”，得到下面的一个图g 8 g s 图3 4 在图3 4 所示g 8 中，n = i y i = 3 ( 2 m + 2 ) = 6 m + 6 , d ( x i ) = d ( x 2 ) = d ( z 。) = 2 m + 3 = 詈+ 1 ，容易看出图g 8 的每一个圈中都至少存在一个度为 。詈+ 1 骨的x 型顶点下面再说明g s 不是上可嵌入的取g s 中边集 a 2 = z l y s ，z 3 y 2 ，z 2 y 。) ，g 8 a ：有三个分支，且不难观察到每个分支的b e t t i 数为奇数，即c ( g s a 2 ) = b ( g s a z ) = 3 由定理i i 知 ( g s ) c ( g s a 2 ) + b ( g s 2 ) 一i a 2 i 一1 = 2 从而g 8 不是上可嵌入的所以从图g 8 可得不等式中。 一不能用誓丹 来代替，也就是说定理中的界。詈+ 1 骨是不可达的另外，由于m 可以 取0 或任意正整数，我们可以得到无穷多个这样的图例 口 1 7 硕士学位论文 根据2 - 部图的性质，顶点集x 与y 在图中的地位和作用是对称的， 所以定理3 2 也可以写为下面的形式： 定理3 2 设g = x ，y ；e ) 为简单2 一部图，且是2 边连通的i x i = m ，i y l = n ( m ，t t 3 ) ，若下列条件有任意一个满足： ( 1 ) 对g 中任意圈c ，存在点z c 且z x 满足： d ( z ) 昙+ l ； ( 2 ) 对g 中任意圈c ，存在点y c 且9 y 满足： d ( y ) i t t4 - 1 ； 则图g 是上可嵌入的，且不等式的下界是不可达的 由定理3 2 很容易得到以下推论： 推论3 2 设g = x ，y ；e ) 为简单2 - 部图，且是2 - 边连通的i x i = m ，i y i = n ( m ，n 3 ) ，y ( g ) = xuy 若g 的最小度占( g ) 皿3 剑，则g 是上 可嵌入的 1 8 关于图的上可嵌入性研究 与支配集有关的上可嵌人图 在图的上可嵌入性与图的各项参数之间关系的研究中，支配集与支 配数是一个重要的方面图g 的一个支配集d 是指g 的一个点子集， 使得g 中每一点或者在d 中，或者与d 中某一点邻接g 中点数最 少的支配集称为最小支配集，最小支配集中点的数目称为支配数文献 【3 9 】利用图g 的支配数和围长给出了g 的b e t t i 亏数( g ) 的一个上界， 从而给出了最大亏格似( g ) 的一个下界本章则在此基础上考虑图g 的 支配集及一些相关条件，确定了两类上可嵌入图，丰富了这方面的结果 4 1 以轮为支配集的上可嵌人图 定义4 1 称图w 为一个轮，如果v ( w ) = z ，y l ，y 2 ，轨) ，e ( w ) = z 玑忙= 1 ，2 ，) u y t 犰+ 1 l i = 1 ，2 ，t ，t + l ( m o d ) 】，且点z 称为该轮w 的中心 在给出了轮的定义后，我们得到一类以轮为支配集的上可嵌入图 定理4 1 设g 是无环连通图，如果g 中含有一个子图为轮，且 v ( w ) = z ，y ，抛，y t ( t23 ) 为图g 的一个支配集，则图g 是上可嵌入 的 证明反证法假设g 是不能上可嵌入的，则存在边集a e ( c ) 满 足定理中所有性质令r ，尼，r ( 凫= c ( c a ) ) 是g a 的所有连通 分支，则k 2 我们先得到以下断言： 断言1 不存在连通分支只，使得v ( w ) y ( r ) 即支配集v ( w ) 中的 所有顶点不可能同时含于同一个连通分支中 证明若存在连通分支只，使得v ( w ) y ( 只) ，因为k 2 ，所以存在 连通分支乃o i ) ，而由事实2 知i v ( f j ) l 2 根据支配集的定义，马中 1 9 硕士学位论文 所有顶点均与v ( w ) 中顶点相邻于是l e ( f i ，b ) l 2 ，与定理( 3 ) 矛盾 故断言成立 断言2 对于任意一个连通分支最，有i v ( w ) n y ( 只) i 1 证明反证假设存在连通分支只，使得i v ( w ) ny ( 只) i 2 根据定 义4 1 ，设点z 为轮的中心分以下两种情况讨论： 情形jz y ( 只) 不妨设 z ，们) cy ( 只) 且y l + 1 y ( 毋) o i ) ，则因为 点z ，y t ，y t + 。都是轮中的点，z 又是轮的中心，故点z ，y l 均与点y l + l 相邻，于是i e ( 只，毋) l 2 ，与定理( 3 ) 矛盾 情形2z 譬v ( r ) 不妨设 饥，) cy ( r ) 且z y ( 乃) o i ) ，同理有 x y l ，z ) ce ( ) ，此时i e ( r ，乃) i 2 ，与定理( 3 ) 矛盾 由以上两种情况可知，断言2 成立 由断言2 可知，在g a 的k 个连通分支中，有t + 1 个分支分别含有 支配集v ( w ) 中的一个顶点不妨设该t + 1 个分支为r ，b ，r + l ，容 易得到e ( w ) e ( r ，局，只+ 1 ) 而l e ( w ) i = 2 t ，则i e ( r ，r ，r + 1 ) l i e ( ) i = 2 t 2 ( t + 1 ) 一3 此结果又与定理( 3 ) 矛盾故定理成立 口 4 2 以完全2 - 部图为支配集的上可嵌人图 本节讨论以完全2 部图为支配集的情况，为方便定理的证明，首先 给出一个引理 引理4 1 设，( z ，y ) = x y 一2 x 一2 y4 - 4 ，当z 3 ，y 4 时，有，( z ，y ) 1 ( 3 ，4 ) = 2 0 证明缸o f = y - 2 ，苗= x - 2 显然当z 3 ，y 4 时，鬈 o ，苗 0 所以 ，( z ，y ) 分别关于z ，y 是严格单调递增函数，故有，( z ，y ) f ( 3 ，4 ) = 2 0 引理证毕 口 定理4 2 设g 是无环连通图，如果g 中含有一个子图为完全2 - 部图 2 0 关于图的上可嵌入性研究 d = ( x ，y ；e ) ，且v ( d ) = xuy 为图g 的一个支配集( 其中l x i 3 ，i y i 4 ) ， 则图g 是上可嵌入的 证明反证法设g 不是上可嵌入的，则存在边集a e ( c ) 满足定 理所有性质令r ，尼，r ( 七= c ( g a ) ) 是g 以的所有连通分支， 则k 2 不妨设x = z 1 ，z 2 ，z m ，y = 箩1 ，v 2 ，) ，于是m 3 ，n 4 我们先得到以下断言： 断言1 不存在连通分支r ，使得v ( d ) y ( 只) 即支配集v ( d ) 中的 所有顶点不可能同时含于同一个连通分支中 证明证明过程完全同定理4 1 中断言1 类似 断言2 不存在连通分支只，使得x y ( 只) 或y y ( 只) 证明若x y ( 只) ，即 z 。，勋，) y ( 只) 则由断言1 知必存在 y l y ( 弓) 0 i ) 因为d = ( x ，y ；e ) 为完全二部图，则y z 与z l ，z 2 ，z 仇 都有边相连，此时有l e ( r ，毋) i 仇3 ，与定理性质( 3 ) 矛盾同理，不 存在连通分支只，使得y y ( e ) 故断言成立 断言3 对于任意连通分支只，有i xny ( 只) i 1 且i y ny ( 只) i 1 证明反证假设存在连通分支尻，使得l x ny ( e ) i 2 不妨设 z l ，勋】y ( 只) 由断言2 知必有一点肌y ( 乃) o i )