关于循环图的曲面嵌入.pdfVIP

2007，27A(6)：1 148 1 154 秀 数学物理学报 关于循环图的曲面嵌入 任韩 邓默 (华东师范大学数学系 上海200062) 摘要：该文集中探讨循环图的曲面嵌入性质．决定了所有循环图的最小亏格 (其中包括可定向 亏格与不可定向亏格)和最大亏格．对于固定的整数 f( 3)和充分大的自然数 n，只有一种 方式将4一正则循环图c(n，f)嵌入到环面上使得其每一个面都是4一边形．特别地，循环图 C(2l+2，j)在加入若干条新边后可以同时将环面与Klein瓶进行三角剖分． 关键词：循环图；嵌入；最小 (不可定向)可定向亏格． MR(2000)主题分类：05C10；05C45 中图分类号 O157．5 文献标识码：A 文章编号：1003—3998(2007)06—1148．07 1 引言 本文中的图都是简单连通图．所用术语采用文献 f1，5，61．一个曲面是一个紧致的无边界 2一维流形拓扑学中的一个经典结果就是曲面分类．它表明：所有的曲面可以分成两类：可 定向曲面(用 表示球面加入9( 0)个手柄)与不可定向曲面(用Ⅳh表示球面加入 ( 1) 个叉帽)．图G在曲面∑上的一个嵌入是图G在曲面∑上的一个画法使得边与边仅在节点 处相交而且∑一G的每一个连通分支 (通称为面)都同胚于一个开圆盘．如果一个面的边界 为 ，则称其是一个 一边形．嵌入在曲面∑上的图G的一个圈c被称为不可收缩的，如果 ∑一C中没有分支同胚于圆盘；否则， C是可收缩的．通常用来比较图的两个嵌入是否相 同的方法是看它们的面边界的集合是否相同．如果相同，则是相同的嵌入；否则，为不同的 嵌入． 设n和 l是两个自然数而n 21．一个n阶循环图G=c(n，1)是一个 n一圈 = (1，2，…，n)外加一些弦(i，J)∈E(G)，其中i与歹在 上的距离为1．循环图在图的理论研 究的作用在于，它们往往是某些典型图的缩影．例如，每一个广义Petersen图都含有某个循 环图为其子式(minor)，如图1所示． 图的曲面嵌入理论方面有许多重要结果．这里，我们列出一些 (作为我们的准备工作)． 下面第一个结果表明了图的最小与最大亏格在图的可定向曲面嵌入分布方面的作用． 定理 1【2J设 G是一个可以嵌入在 和 上的图．则对于m n的任何一个 ，G可以嵌入在 上． 收稿日期：2004—12—03；修订日期。2007-01—26 E—mail：hren@math．ecnu．edu．cn {基金项目；中国国家自然科学基金10671073)资助 No．6 任韩等：关于循环图的曲面嵌入 1149 图I广义Petersen图G(8，3)与其子式c(s，3) 下面的关于图的最大亏格的结果属于文献[12]． 定理2设G是一个连通图．则G的最大亏格为l j，其中 (G)是G的Betti 数而 (G)是 ∈(G)=ra—in Codd(G—E(T))， 这里的最小值是对于G的所有支撑树所对应余树的奇连通分支数进行的． 因此，人们为了决定图的最大亏格，往往转而寻求一个具有最少奇连通分支数的支撑 树．故，一个4一边连通图是上可嵌入的(可以嵌入到某个可定向曲面上，使的至多只有两个 面)，因为它们含有两个边不交的支撑树．由于Nebesky[8】的工作导致了计算图的最大亏格的 多项式算法，摆在人们面前的真正困难就是决定图的最小亏格问题．但是，Thomassen在 文献 f101中已经证明：图的最小亏格