（应用数学专业论文）关于一些特殊图的上可嵌入性研究.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，i 喀文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意。 作者签名：日期：迎4111 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于菲赢利目的的少量复制并允许论文进入学校图书馆被查阕。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位敝作者签名凄峋鹏 导师签名： 日期：甚q 垒：! ! 日期； 百磷 摘要 自从e n o r d h a u s ，b s t e w a r t 和a w h i t e 等人引进图的最大亏格概念以 来，图的上可嵌入性嵌入引起人们的广泛关注由r d u c k 图的亏格插值定理知： 考虑图g 的所有可定向嵌入的曲面，只需确定它的亏格r ( g ) 与最大亏格“( g ) 。 图g 的最大亏格h ( g ) 是指存在最大的整数k 使得g 在亏格为k 的可定向曲面 s 上有2 一胞腔嵌入由于图在任意曲面上的2 一胞腔嵌入至少有一个面，由e u l e r 公式知：n ( g ) 塑婴】，这里卢( g ) 爿e ( g ) i i 矿( g ) i + l 称为图g 的b e t t i 数 z 如果h ( g ) = 壁婴】，称图g 是上可嵌入的 z 关于图的上可嵌入性，刘彦佩 5 和n e b s k e y 7 分别给出了不同形式的充要 条件；黄元秋和刘彦佩 1 8 从另一相反角度出发，提供了一个关于不是上可嵌入 图的充要条件由此充要条件，本文主要对一些满足特殊条件的图的上可嵌入性 进行专门研究，共分为五章 在第一章中：集中探讨范条件图的上可嵌入性设g 是2 点连通图，若对任 对使d ( u ，v ) = 2 的点u ，v ，满足m s x d ( u ) ，d ( v ) 1 兰( 其中n = t v ( e ) 1 ) ， z 则称g 是满足范条件的图：我们证明了范条件图是上可嵌入的 在第二章中：集中探讨大次和条件图的上可嵌入性设g 是k 点连通图，若 对任一漉，x 。，x 。卜独立集均有d ( x i ) + d ( x ：) + + d ( x 。) n k ( n = 1v ( g ) m 则称g 是满足大次和条件的图；我们证明了2 类大次和条件图是上可嵌入的 在第三章中：集中探讨g 的立方图g 3 的上可嵌入性设g - ( v ，e ) ，定义g k = ( v ( g 。) ，e ( g ) ) ，其中v ( p ) = v ( c ) ，e ( g 。) = o = u vi 也( u 。v ) k ) ，则称 g 为g 的k 方图；我们证明了g 的立方图g 3 是上可嵌入的 在第四章中：集中探讨特殊二部图的上可嵌入性我们证明下述结果：( i ) 设g = ( x ，y ：e ) ，定义g 3 ：( v ( g 。) ，e ( 铲) ) ，其中v ( 口) = v ( g ) ，e ( g ) = e ( g ) u e = x yid ，( x ，y ) = 3 ，x x ，y y ，则g 3 是上可嵌入的；( 2 ) 设g = ( x ， y ；e ) ，i x = 1 y l ：n ( n 3 ) ，对任一对d g ( x ，y ) = 3 的x x ，y e y ，均有d ( x ) 十d ( y ) n t l ，则g 是上可嵌入的 在第五章中：简单地探讨3 一正则图的上可嵌入性。我们讨论3 - i e 则图的叶子 数与最大亏格h ( g ) 之间的关系并给出3 - 正则图最大亏格的一个计算公式： ( g ) = 争，( 7 ) + 儿一如】，这里t 是x u 。n g 树，t ( d t 的叶子数，儿，即分 别是g - e ( t ) 中偶长路数与奇长圈数 关键词： 图，最大亏格，b e t t i 亏数，上可嵌入 2 s t u d i e so ns a m es p e c i f i c i 概瞰1 曲酣d a b l eg r a p h s 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 n 朋g e n u sb yen o r d a 叫s s t e w a r t a n d 九w h i t e ，t h eu p - 删d a h i l i t yo f 田础h a sb e e np a i dg r e a ta t t e n t i o ns of a r 1 f 、 t h em i n i m e ma n dt h em a x i m j no r i e n t a b l e ( n o r r - o r i e n t e o l e ) g e n u so fgr e s p e c t i v e l y3 r e k n o w n ，t h e na l lt h ep o s s i b l eo r i e n t a b l e ( n o mo r i e n t a b l e ) s u l a c e so nw h i c ht h e 卿h ( ； c a nb ei n r a e d i a t e l yd e t e m i r 刮b yt h et h e o r e mo frd u c k t h em a x i n mg e n u sh ( g ) o f 1 c o n n e c t e dg r a p hgi st h em x i m t mi n t e g e rkw i t ht h ep r o p e r t yt h a te x i s t sac e il u a r e m b e d d i n go fgo nt h eo r i e n t a b l es u r f a c es ko fg e n u sk s i n c ea n yc e l l u a re m d o e d d i n gv e s t h a v e a t l e a s t o 僻f a c e ，t h e e l u e r p o l y h e d m l e q u a t i o n i m p l i e s a n u p p e r b ( n d o n t h er m x i n r n g e n u s ( g ) 旦旦 ，怕r e b ( g ) = i e ( g ) i i v ( o ) j + l ，t h e n t 岫e rb ( g ) i s l 讥c 孙t b 。 b e t t in 出ro ft h ec o n n e c t e d 舯p hg o nt h e 嶂p e re f i b e c 幽b i l i t y o f 昏鼍p h s ，l i u s a n d n e h e s k y i t h a v ei n d e p e n d e n t ly p r o v i d ed i f f e r e n tr l e o 自s s a r ya n ds u f f i c i e n tc o n d i t i o n s ；o nt h eo t h e r 试慨a m h i l l 18 p r o v i d ean e c e s s a r ya n ds u f f i c i e n tc o n d i t i o no i lt h en o n p e rc m b e d d a b l e 毋a p h s t h i s d i s s e r t a t i o nm a i n l ys t u d i e st h eu p p e re f f b e d d a b i l i t yo fs ( i l es p e c i a l g f a p h s ，itc o n s i s t so ff i v ec h a p t e r s i nc h a p t e ri ，w em a i n l yi n v e s t i g a t et h e 岍r 印b 引出b i l i t yo fg r a p h sw h i c h s a t 【s f y t h e f a n sc o n d i t i o n w ep r o v e t h e f o l l o w i n g r e s u l t ：l e t g b e a 2 - v e r t e xc o n n e c t e 【i g r a p h f b re v e r yp a i ro ft i e g ，v gw i t hd ( u ，v ) - - 2 , s u c ht h a t 憾x d ( u ) ，d ( v ) ： 昙( w h e r e 萨 v ( g ) f ) ，t h e n gi su p r 甘t b e d 由b l e i nc h a p t e r2 ，w em i n l yi n v e s t i g a t et h eu p p e re m n b e d d a b i l i t yo fs p e c i f i c d e 盯e e - s t mg r a p h s l e tgb eak - v e r t e xc o n n e c t e d 掣a p h ， x l ，轧，k 矗i sat 节n d o m i n d e p e n d e n ts e to fg ，i ts a t i s f i e st h ep r o p e r t yo fd ( x d ( x 9 + 州( i ) 打k ( w h e r e n - v ( g ) f ) ，w ep r o v et h ef o l l o w i n g i w or e s u l t s ：i fk = lo r2 ，t h e ngi su 旷e 妇d d a b h i nc h a p t e r3 w em i n l yi n v e s t i g a t et h eu p p e re i i b e d d a b i l i t yo fag r a p hg ! w e d r o v e t h e f o l l o w i n g r e s u l t ：l e t g b e a s i n l 。l e g r a p h a n d 晦释( g ，e ) ( w h e r e v ( g ) = v g b ， e ( c ) = e - - u v c l “v ) 3 ) ，t h e ng i su 删l e i ne h a g t e r4 w em a i n l yi n v e s t i g a t et h eu p p e r 酬础i l i t yo fs o e c i f i cb i l a r t it e g r a p h s w ep r o v et h ef o l l o w i n gr e s u l t ：( 1 ) l e tg ：0 【，y ；e ) a n dg - “( g ) ，e ( g ) ) ( w h e r e v ( g ( g ) ，e ( o ( g ) u e = x yl 成伍y ) = 3 ，x x ，y e y ) ，t h e ng i s 妒锄b e d d a b l e ； ( 2 ) l e tg = 0 ( ，y ；e ) a n dl x ， 一- - i = n ( n 3 ) ，f o re v e r ym i ro fx x ，y e yw i t hd ( x ， y ) 毡s u c ht h a td ( x ) + d ( y ) 材1 ，t h e n gi sl 矿酬) e d d 如l e i nc h a p t e r5 ，w es f m p l e l yi n v e s t i g a t et h el 印时印虹成b b i l i t yo f3 - r e g u l a r c o n n e c t e dg r a p h s w ed i s c u s st h er e l a t i m sb e t w e e nt h er l t l 妇 so fx u a n gt r e e sl e a f ，( t ) a n dt h em a x i m ng e n u s 矗( g ) ：a n dp r o v i d eaf o r m u l a0 nc c m l o u t i n gr 舸x i m a mg e n u so t 、a 1 3 - r e g u l a rc o n n e c t e dg r 硇：r h ( g ) = 去 ，( r ) + p 。一p 卢1 ，w h e r eti sax u o n gt r e eo i a 二 3 - r e g u l a rc o n n e c t e dm - a o n ，! ( t ) i st h el e a fn u m b e ro fg p 。i st h en u r a o e ro f e v e n - l e n g t h - p a t ho fg - e ( t ) ，p 口i st h e 腑o fo d d - l e r g t h i r c l eo fg - e ( t ) ， k e yw o r d s ： g r a p h ，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 ，u p p e re m b e d d a b l e 4 前言 一背景 图论是组合数学的一个主要分支，是一门发展迅速而又应用极其广泛的学 科它已广泛地应用于物理、化学、生物、计算机科学、信息学、神经网络、管 理科学以及社会科学等领域，其中拓扑图论结合了图论和低维拓扑学，现已成为 近年来一个十分活跃的研究方向象图论其他的分支一样，图在曲面上的嵌入性 也有其深厚的根基一著名的四色问题，自从c a y l e y 1 1 8 7 8 年正式公布著名的四 色问题后，图在一般曲面上的嵌入引起人们的广泛关注在1 8 9 0 年h e a w o o d 2 提出著名的地图着色问题后，h i i b e r t 等人又将它归纳为引线问题：即在曲面s 。 ( p 表示s 的亏格) 给定n ( n 3 ) 个不同点，能否用简单曲线( 引线) 两两连 接这n 个点使得这些连线在曲面上互不相交? 用图论术语而言，引线问题与确定 完全图k 。的亏格r ( k 。) 等价，自然确定一般图的亏格又是上述问题的推广为 解决引线问题，大量的关于图在曲面上的嵌入的研究工作产生了，直到1 9 6 8 年 才得以完全解决尽管地图着色问题得以完全解决，然而它却给图论开辟了一个 至今不衰的新课题图在曲面上的嵌入，它为图的理论研究与应用开辟广阔的 前景 这里，曲面通常是指一个紧的，2 一维流形s ( 定向或不定向) 其亏格表示为 g ( s ) 连通图g 在曲面s 上的一个嵌入意指存在一个拓扑同胚映射h ：g s ， 使得s h ( g ) 的每一个连通分支与圆盘拓扑等价；也有人称之为2 一胞腔嵌入图g 的亏格r ( g ) 是指最小的整数g ( s ) 使得g 在曲面s 上有2 胞腔嵌入，而图( ； 的最大亏格h ( g ) 是指最大的整数g ( s ) 使得g 在曲面s 上有2 一胞腔嵌入1 9 6 8 年，r d u c k 3 证明了图的亏格插值定理：即如果图g 在两个可定向曲面s ，和s 。 ( m n ) 上都有2 一胞腔嵌入。则g 在任意可定向曲面s 。( m k n ) 上也有2 一 胞腔嵌入，因此由图的亏格插值定理知：考虑图g 的所有可定向嵌入的曲面，只 需确定它的亏格f ( g ) 与最大亏格r 。( g ) 由于图在任意曲面上的胞腔嵌入至少有一个面，故由e u l e r 公式知：h ( ( ；) 【旦粤 ，这里( g ) 刮e ( g ) f v ( o ) i + 1 称为图g 的b e t t i 数如果f a ( ( ；) = 掣 ，称图g 是上可嵌入的基于图在不可定向曲面下，早在7 0 年代末 z r i n g l e 4 、刘彦佩 5 等独立地证明上述等号成立，因此对图的最大亏格的研究 一般都指在可定向曲面情形下自从7 0 年代初，由e n o r d h a u s ，b s t e w a r t 和 a w h i t e 6 等人引进图的最大亏格以来，至今这一领域仍然是拓扑图论中的一个 十分活跃的方面图的最大亏格是刻划囤在曲面上嵌入的一个拓扑参数，而与最 大亏格相关的图的上可嵌入性一确定一个图最大亏格的最好上界是拓扑图论 中一直感兴趣的问题，因此对图的上可嵌入性的研究是一项很有意义的课题 二图的上可嵌入性的相关研究 图的上可嵌入性的研究吸引了研究者的广泛关注，大量的研究成果涌现出 来关于图的上可嵌入性，刘彦佩 5 和n e b s k e y 7 分别给出了不同形式的充要条 件；在文 8 中，x u o n g 证明了一个连通图是上可嵌入的当且仅当芒( g ) l ：且 ( g ) ；丛旦；塑给定一些限制条件，许多文献都证明了一些图类是上可嵌入 z 的n e b s k e y 在文 9 中证明了每一个连通图，局部连通图是上可嵌入的在文 1 0 中证明了每一个局部半连通无环图g 是上可嵌入的图g 是这样得来：连接两个 具有偶b e r t i 数的上可嵌入图的相交顶点所得到的图：在文 1 1 中，j a e g e r ，p a y a n a n dx u o n g 证明了每一个这样的图g 是上可嵌入的在文 1 2 中，s k o v i e r a 证明 了每一个直径为2 的无环图是上可嵌入的在文 1 3 中，证明了下述结论：对简 单图g 。或者g 或者它的补图口是上可嵌入的；每一个2 k 一正则的二部图是上可 嵌入的；每一个( 4 k 十2 ) 一正则图是上可嵌入的在文 1 4 中，k u n d u 证明了每一 个4 一边连通图包含2 个边不相交的生成树，由此可见每一个4 一边连通图是上可 嵌入的由于4 一点连通图必是4 一边连通图，故每一个4 一点连通图是上可嵌入的 然而存在3 一点连通图是不能上可嵌入的 1 5 3 ( 如图所示) 反蜘 邛静eb 可嵌入的争点连通图 6 与图的上可嵌入性的研究成果不胜枚举，由于篇幅有限这里不再一阐述 2 0 0 1 2 0 0 4 年本人在华东师大数学系应忍数学专业以研究生毕业同等学力申请 硕士学位的研究生课程班学习，在此期间参与了任韩的课题研究，在任韩老师的 悉心指导下取得一定的成绩，共完成几篇文章：其中特殊二部图的一t - 可嵌入性 己被华东师范大学学报录用；范条件圉的上可嵌入性己发表在泉州师范学院 学报2 0 0 4 年第2 期：立方图g 3 的上可嵌入性已发表在沈阳师范大学学报2 0 0 4 年第4 期；l f r e e 的的上可嵌入性已发表在广西师范学院学报2 0 0 4 年第 3 期；大次和条件图的上可嵌入性待发表；3 一正负i j 图最大亏格的一个计算公 式( 第三作者) 待发表 三基本定义与引理 本文中考虑的图g = ( v ，e ) 均指有限，无向连通图一个称为简单图，如果它 不含重边和环其他未涉及的拓扑图论的基本术语与记号均可参见文 1 6 与e 【7 ： 定义1 ：图g 的最大亏格r 。( g ) 是指存在最大的整数k 使得g 在亏格为k 的可 定向曲面s 上有2 一胞腔嵌入 定义2 ：如果h ( g ) ：i 掣1 ( p ( g ) 爿e ( o ) i 一1 y ( g ) l + 1 ) ，则称图g 是上可嵌 入的 定义3 ：设t 为图g 的一棵支撑树，g e ( t ) 的一个连通分支k 称为奇分支如果 k 有奇数条边；否则，k 称为偶分支。记号f ( g ，t ) 表示g e ( t ) 中奇分支的 个数称善( g ) = m i n 4 ( g ，t ) 为g 的b e t t i 亏数这里m i n 取遍g 的所有支撑 树t 定义4 ：对g 的任意边子集a c _ e ( g ) ，c ( g a ) 表示g a 的连通分支数，b ( g a ) 表 示g a 中具有b e r ti 数为奇数的连通分支数， 引理a 7 ：一个连通图g 是上可嵌入的当且仅当c ( g a ) + b ( g a ) 一2 蔓l a i ， 对任意a c _ e ( g ) ；且亭( g ) = m a x c ( g a ) + b ( g a ) 一卜i a m 月c 【 引理b 【8 ：一个连通图g 是上可嵌入的善( g ) 蔓l ，( g ) ：丛g 安丛坠 第一章范条件图的上可嵌入性 1 1引言 自从n o r d h a u s 等引入图的最大亏格概念以来，图的最大亏格以及图的上 可嵌入引起了广泛关注由r d u c k 图的亏格插值公式知：考虑图g 的所有可嵌 入的可定向的蓝面，只需确定它的最小亏格r ( g ) ( 简称为亏格) 和最大亏格 r 。( g ) 设s 为一个可定向曲面( 曲面，这里是指一个紧的2 一维闭流形) ，一 个图g 在s 上的个2 一胞腔嵌入是指g 能画在s 上使得边与边之间除顶点外不 再相交，且在s 去掉g 的顶点与边之后的每个连通分支与圜盘同胚；而图的最 大亏格h ( g ) 是指最大的整数k 使得图g 的一个2 一胞腔嵌入到可定向的曲面 s 、上由e u i e r 公式，有h ( g ) 曼璺 ，这里b ( g ) ： e ( g ) f i v ( g ) + l z 称为图g 的b e r t i 数( 圈秩) ；如果h ( g ) ： 笪! 旦 ，称图g 是上可嵌 上 入的关于图的上可嵌入性，文 5 和文 7 分别给出了不同形式的充要条件；文 1 8 从另一相反角度出发，提供了一个关于不是上可嵌入图的充要条件，设g 是2 点连通图，若对任一对使d ( u ，v ) = 2 的点u ，v ，满足m a x d ( u ) ，d ( v ) 兰，( 其中n = l v ( g ) ! ) ，则称g 是符合范条件的图，而符合范条件的图g 是 2 h 一图；本章专门对范条件图的上可嵌入性进行研究，证明了范条件图是上可嵌 入的 1 2定义及引理 定义1 1 - 设g 是2 点连通图，若对任一对使d ( u ，v ) = 2 的点u ，v ，满足 m a x d ( u ) ，d ( v ) 昙，( 其中n 2 1 v ( g ) 1 ) ，则g 是符合范条件的图 定义1 2 ：对于任意的a _ e ( g ) ，c ( g a ) 表示g a 的连通分支数，b ( g a ) ： ( f if 是g a 的一个连通分支，且1 3 ( f ) ；1 ( m o d 2 ) ) ，b ( g a ) = l b ( g a ) | 定义1 3 ：对于g a 的两个不同连通子图f 、h e ( f ，h ) = ( e = u vu vo f ) ，v v ( h ) ) ， e ( f ，g ) = ( e ：u v lu e v ( f ) ，v 芒v ( f ) 定义1 4 ：设g ：( v ，e ) 是一个2 - 连通图，g 的闭包否定义如下： v ( g ) = v ( g ) ( j v ( g ) 1 = n ) ，弧，y v ，( x ，y ) e e 且d ( x ) + d ( y ) n ； 则( x ，y ) + g = g 。，再考察gz ，觇i ，y f v ，( ，y i ) 压且d ( xz ) + d ( y t ) - - - m 则( x 。，y ) + g 。= g ，依次类推如果我们从g 出发，相继地联结所得到的图中 次和不小于n 的不相邻点对，最后得到图g ，称g 为g 的闭包 引理1 1 7 】：若g 是一个简单连通图，那么 ( 1 ) g 是上可嵌入的当且仅当c ( g a ) + b ( g a ) 一2 l a l 对任意的a 量e ( g ) ； ( 2 ) e ( g ) = d l a x c 。( g ) c ( g a ) + b ( g a ) 一l a i 一1 引理1 2 1 1 8 ：g 是一个连通简单圉，如果g 是不能上可嵌入的，那么存在a g e ( g ) ，满足下列性质： ( i ) c ( g a ) = b ( g a ) 2 ：( i i ) 3 2 b ( g a ) i a i 4 ； ( i 1 1 ) 对于g a 的每个连通分支f ，f 是g 的一个导出子图i ( i v ) 对于g a 的两个不同连通分支f ，h ，j e ( f ，h ) j 1 注：由引理1 2 知：对g a 的每一个连通分支f 有以下结论： 事实l ：由性质( i ) 知，( f ) = t ( m o d 2 ) ； 事实2 ：g 是一个连通简单图， v ( f ) f 3 1 3 主要结果 定理1 1 ：设g 是2 点连通图，若对任一对使d ( u v ) = 2 的点u ，v ，满足 m a x d ( u ) 。d ( v ) 罢( 其中n = i v ( g ) ) ，则g 是上可嵌入的。 证明：假设g 是不能上可嵌入的，由引理l _ 2 知：存在a e ( g ) 满足引 理1 2 的( 1 ) 、( i v ) 性质令r = f ，f ：，f 。 ( t = b ( g a ) ) 是g a 的所有连 通分支 因为g 是2 点连通图，所以le ( f ；，g ) 2 ，i = l ，2 ，t 由事实l 及事实2 知：8 ( f ) = l ( m o d 2 ) ，j v ( f ，) 1 3 ，i = 1 ，2 ，t 再由引理1 2 的( j v ) 性质及g 的2 一连通性知：t - - b ( g a ) 3 ，下面我们将分 成t = 3 和t 1 4 两种情况加以讨论 ( 1 ) t = 3 假设f ，f 。，f 。是g a 的三个连通分支 由引理1 2 的( i v ) 性质及g 的2 连通性知；fe ( f ”f j ) e = i ，( i j ，i ，j = l ， 2 ，3 ) 不妨设e ( f 。，f 2 ) = i 1 l u ：1 ，e ( f i ，f 1 ) = v i u 。 ，e ( r ，f 。) = v 。v 。 ，其 中u i ，v 、仨v ( f 。) ，( 允许u i = v 。) u 2 ，v ：v ( f 2 ) ，u 。，v 。v ( r ) 由事实2 知：j v ( f ) 1 3 ，i = l ，2 ，3 ，所以至少存在一点毗v ( f ：) ，使得 u ：w ：e ( 1 3 ) 。这样得到d ( t 1 ，w 。) = 2 ；由定理1 1 的条件知： m a x d ( u ) ，d ( w 。) ) 昙 z 不妨设d ( u ；) 罢，同理至少存在一点w 。v ( f 3 ) ，使得v 3 w 。e ( g ) ，这样得 上 到d ( v ：，w ：1 ) = 2 ；由定理1 1 的条件知： m a x ( d ( v ：) ，d ( w 。) ) 昙 于是d ( v ：) 导或d ( w 3 ) 导这是不可能的 因为f 中节点的次大于等于詈，则g x a 的其它分支中的节点的次均小于等于要 故导致矛盾 ( 2 ) t 4 假设f ，f ：，f 。( t - - b ( g a ) ) 是g a 的所有连通分支 由引理1 2 的( i v ) 性质知：【e ( f ，f j ) f l ，( i j ，i ，j = 1 ，2 ，t ) 又因为g 是2 点连通图，故【e ( f ，g ) i 1 2 不妨设存在两个不同连通分支f ，f 使得e ( f ，f ) = u m ) ，e ( f ，f ) = iv l vf ， 其中u 。，v 。v ( f 。) ，( 允许u = v ，) v v ( f 、) ，v v ( f ) ；同理至少存在一个 连通分支r 使得e ( f ，f 。) = u i u k 其中u 。v ( f ) ，u 。v ( f 。) 由事实2 知：i v ( f ) 【 1 3 ，故至少存在一点w v ( f ) 且w l u ，v ，使得 vw ，e ( g ) ，于是得到d ( u 。w ) = 2 ；由定理1 1 的条件知： m a x d ( u 。) ，d ( w 。) 昙 不妨设d ( u 。) 罢，同理至少存在一点v 。v ( f k ) ，使得u 。v 。e ( g ) ，于是得 到d ( u ，v 。) - - 2 ；由定理1 1 的条件知。 m a x d ( u j ) ，d ( v 。) 罢 于是d ( u - ) 三或d ( v “) 兰这是不可能的 因为f t 中节点的次大于等于薹，则g a 的其它分支中的节点的次均小于等于兰2 ， 故导致矛盾综上所述：g 是上可嵌入的，定理1 1 证毕# 推论1 1 ：设g 是一个简单连通图，若6 昙，则g 是上可嵌入的 z 证明：因为g 是一个简单连通图且6 昙，所以对任一对使d ( u ，v ) ：2 z 的点1 j ，v ，均有m a x d ( u ) ，d ( v ) 兰( 其中n = i v ( g ) 1 ) ，满足定理1 1 z 的条件故由定理1 1 知：g 是上可嵌入的# 推论1 2 ：设g 是一个简单连通图，若对g 中任一对不相邻的点u ，v ，均有 d ( u ) + d ( v ) n ，则g 是上可嵌入的 证明：因为g 是一个简单连通图且对g 中任一对不相邻的点u ，v ， 均有d ( u ) + d ( v ) n ，则对任一对使d ( u ，v ) - - 2 的点u ，v ， 均有m a x d ( u ) ，d ( v ) ) 昙( 其中n = i v ( g ) 1 ) ，满足定理1 1 的条件 z 故由定理1 1 知：g 是上可嵌入的# 推论1 3 ：如果一个圈g 的田包石= k ，则g 是上可嵌入的 证明：因为图g 的闭包石- - k 。，则对g 中任一对不相邻的点u ，v ， 均有d ( u ) + d ( v ) n 。则对任一对使d ( u ，v ) = 2 的点u ，v ， 均有f f l a x d ( u ) ，d ( v ) ) 昙( 其中n = f v ( g ) ) ，满足定理i 1 的条件 z 故由定理1 1 知：g 是上可嵌入的# 第二章大次和条件图的上可嵌入性 2 1引言 早在7 0 年代末，r i n g e l 和刘彦佩等独立地解决了图在不可定向曲面上的 最大亏格和上可嵌入问题，因此图的上可嵌入性研究一般都指在可定向曲面上 由r d u c k 图的亏格插值公式知：考虑图g 的所有可嵌入的可定向的曲面，只需 确定它的最小亏格r ( g ) ( 简称为亏格) 和最大亏格h ( g ) 连通图的最大亏格 和上可嵌入性问题直是拓扑图论中的一个有趣的课题，特别是对图的上可嵌入 性和点连通度的关系的研究是近年来的一个活跃的课题关于图的上可嵌入性， 文 5 和文 7 分别给出了不同形式的充要条件；文 t 8 3 从另一相反角度出发，提 供了一个关于不是上可嵌入图的充要条件结合图的点连通度，本章对某些大次 和条件图的上可嵌入性进行探讨，证明了某些大次和条件图是上可嵌入的 2 2 定义及引理 定义2 1 ：给定图g = ( v ，e ) ，若集合i 冬v ，i 中任意两个点在g 中不相邻， 则称i 是g 的一个独立集g 的最大独立集的顶点数称为6 的独立数，记为a ( g ) 定义2 2 ：设g 是k 点连通图，若对任一k ，x 。，n j ) 独立集均有 d ( x ，) + d ( x ：) + + d + ，) n k ( n = ) v ( g ) gi ) ，则称g 是满足大次积条件的图 定义2 3 ：对于任意的a e ( g ) ，c ( g a ) 表示g a 的连通分支数，b ( g a ) = ( f ff 是g a 的个连通分支，且b ( f ) ；l ( m o d 2 ) ) b ( g k a ) = b ( o k a ) 定义2 4 ：对于g a 的两个不同连通分支f 、h e ( f ，h ) ：( e = h v lu v ( f ) ，v e v ( h ) ) ， e ( f ，g ) = ( e ：u v u v ( f ) ，v 芒v ( f ) ) 引理2 1 7 ：若g 是一个简单连通图，那么 ( 1 ) g 是上可嵌入髂当且仅当c ( g a ) + b ( g a ) 一2 a l ，对任意的 量e ( g ) ： ( 2 ) ( g ) = m 旺c 。( 。) c ( g a ) + b ( g a ) 一i a 卜1 1 ， 引理2 2 1 1 8 ：g 是一个连通简单图，如果g 是不能上可嵌入的。那么存在a e ( g ) ，满足下列性质： ( i ) c ( g a ) ；b ( g a ) 2 ； ( i i ) 3 2 b ( g a ) 一l a i 4 ； ( i i i ) 对于g a 的每个连通分支f ，f 是g 的一个导出予图： ( i v ) i e ( f 儿，f 。，f n ) l 2 k - 3 ，对g a 的任意k 个不同连通分支，特别对 于g a 的两个不同连通分支f ，i - ，i e ( f ，i - i ) j 1 注：由引理2 2 知，对g a 的每一个连通分支f 有以下结论： 事实l ：由性质( i ) 知，b ( f ) 9 1 ( m o d 2 ) ； 事实2 ：g 是一个连通简单图， vc f ) f 3 2 3 主要结果 定理2 1 ：设g 是l 点连通图，若对任一 x ，y 卜独立集均有d ( x ) + d ( y ) n - i ( n = 1 v ( g l ，则称g 是上可嵌入的 证明：假设g 是不能上可嵌入的，由引理2 2 知：存在a e ( g ) ，使得性质 ( i ) 、( n ) 成立由定理2 1 的条件知：不妨设ie ( f ，g ) i = 1 ，即存在f ：使得f ( f ，r ) = u v ) ，其中u e v ( f ，) ，v v ( f 2 ) 由事实2 知：1v ( f ) 1 3 ，故 至少存在一点u v ( f 、) 且u t u ，使得u l l i e e ( g ) ；同理至少存在一点v 。v ( r ) 且v ，v ，使得v t v e e ( g ) 由此u ，v 。在g 中彼此不相邻，这样 u ，v ，： 构成g 的一个2 一独立集，由定理2 1 的条件知： d ( u ) + d ( v 。) n 一1( 1 ) 而d ( u ，) ，v ( f 。) 【一l ，d ( v 。) i v ( r ) j _ l ， 故d ( u ，) + d ( v ，) ) v ( f ) f - l + jv ( r ) j - i n - 2 ( 2 ) 由( 1 ) ，( 2 ) 式知：这是不可能的，矛盾 综上所述；g 是上可嵌入的，定理2 1 证毕# 定理2 2 ：设g 是2 点连通圈，若对任- - x ，y ，z ) - 独立集均有d ( 曲+ d ( y ) + d ( z ) n 一2 ( n = v ( g ) i ) ，则称g 是上可嵌入的 证明：假设g 是不能上可嵌入的，由引理2 2 知，存在a e ( g ) ，使得性 质( t ) 、( 沁) 成立令f 。，f 矿一，f 。( t = b ( g a ) ) 是g a 的所有连通分支 1 1 因为g 是2 点连通图，所以ce ( p ，g ) i 2 ，i = 1 ，2 ，t 再由引理2 2 的( i v ) 条件知：t = b ( g a ) 3 ，下面我们将分成t = 3 和t i 4 两 种情况加以讨论 ( 1 ) t = 3 不妨设f ，r ，f 。是g a 的三个连通分支，由g 的2 点连通性及引理2 2 的( i v ) 条件失口：1 ia 1 = 3 令e ( f ，f 2 ) = u i u ：) ，e ( f 。，f ，) ： v ，v 。) ，e ( f 。，f ；) = v ：u ；l ， 其中u ，v v ( f 1 ) ，u ：，v 2 e v ( r ) ，u 。，v ，v ( f 。) 由事实2 知：l v ( f ，) 3 ，故至少存在一点x 。v ( f ，) 且x u i ，v 。，同理至少存在一点x 。苣v ( f 二) 且x ：u 。，v 2 ，至少存在一点x 。v ( f 。) 且x a u 。，v 。，使得x 。x ：，x ，在g 中 彼此不相邻这样 “x 。，x ， 构成g 的一个3 独立集，由定理2 2 的条件知： d ( x ) + d ( x ：) + d ( x 0 n 一2( 3 ) 而d ( x 。) v ( f ) j - 1 ，d ( x 。) v ( f 。) 卜l ，d ( x ：。) l v ( f ：。) 卜1 ， 故d ( x ) 州( x 2 ) + d ( x ；) f v ( f ) 卜1 + 1 v ( f ：) 1 一l + v ( f 。) 卜l n 3( 4 1 由( 3 ) ，( 4 ) 式知：这是不可能的，矛盾 ( 2 ) t 4 假设f 。，r ，f 。( t = b ( c a ) ) 是g a 的所有连通分支 由g 的2 点连通性及引理2 2 的( i v ) 条件知：不妨设i e ( f 。，g ) i ：2 ，即存在 两个不同连通分支为f 。，f 。，使得e ( f 。f j ) = u u j ) ，e ( f ，f k ) = v v 。 ，其中 u ，v v ( f ) ，u j v ( f 。) ， v 。v ( f k ) 由事实2 知：l v ( f ) l 3 ，故至少存 在一点x ，v ( f ，) 且x 。u 。，v ，同理至少存在一点x 2 v ( f ) 且x 。u ，至 少存在一点x ，v ( r ) 且x 。v 。，使得x 。，x z ，x 。在g 中彼此不相邻这样 x ， x x ，) 构成g 的一个3 一独立集，由定理2 2 的条件知： d ( x 、) + d ( x ：) + d ( x ，) n 一2( j ) 而d ( x 。) iv ( f ，) i - 1 ，d ( x ：) j v ( r ) ! _ l + t - 2 ，d ( x ：，) | v ( r ) j l 。t 一冀 故d ( x ；) + d ( x ：) + d ( x ，) ：iv ( f 。) 一l + i v ( f j ) 卜l + t 一2 + fv ( r ) 卜l + t 一3 n 一3 ( t - 3 ) + 2 t + 8 = n t + l n 一3( 6 ) 由( 5 ) ，( 6 ) 式知：这是不可能的，矛盾 综上所述：g 是上可嵌入的，定理2 2 证毕# 2 4 附记 1 定理2 1 中的条件：若对任一 x ，y 一独立集均有d ( x ) 十d ( y ) n 1 不能改 为d & ) + d ( y ) n 一2 ，否则g 不一定上可嵌入的 反例如图( 1 ) 所示：图( 1 ) 中的g 是l 点连通图且对任一 x ，y ) _ 独立集均 有d ( x ) + d ( y ) n 一2 ，但g 是不能上可嵌入的理由如下： 证明：取a = e 则i a i = l ，b ( g a ) = 2 ，c ( g a ) = 2 ，于是b ( g a ) + c ( g a ) 一i a 【= 3 术2 ； 由引理2 2 知：g