球面和射影平面上不可分地图的色和

给出了球面和射影平面上带根不可分地图的色和方程，从色和方程导出了球面和射影平面上带根一般不可分地图、二部地图的计数函数方程. 利用色和理论，研究不同类地图的计数问题，得到了一种研究计数问题的新方法. 此外，还得到了一些计数显示表达式.     

图的上可嵌入性与独立顶点的新度和

Let G be a k(k ≤3)-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/(4 k)} of G,if,then G is up-embeddable.     

关于图的最大亏格的结果

提供了一类新的上可嵌入图类,并且得到了一类直径为2的二连通伪图以及一类直径为4的重图的最大亏格的紧下界,这推广了Skoviera的一个结果．     

图的最大亏格与2-因子

图Ｇ的一个２因子Ｆ就是Ｇ的这样一个支撑子图，使其任何节点ｖ∈Ｖ的次ｄＦ（ｖ）＝２．易见，Ｇ的每个２因子均为无公共节点的圈之并．若Ｆ的每个圈的长均为３（或４），则称Ｇ含有一个三角形（或四边形）２因子．Ｍ．ｋ∨ｏｖｉｅｒａ［５］得到了含有三角形２因子的３－正则图的最大亏格．本文在３－正则图上，引进了扩张运算和讨论了与最大亏格和Ｂｅｔｉ亏数之间的关系．利用这些运算，得到了所有含四边形２因子的连通３－正则图是上可嵌入的，即γＭ（Ｇ）＝ｎ４（ｎ为Ｇ的节点数ｎ＝｜Ｖ（Ｇ）｜）．然后，基于此证明了含四边形２因子且所有节点ｖ∈Ｖ的次ｄＧ（ｖ）＝３（ｍｏｄ４）的图Ｇ均为上可嵌入的     

图的k-单圈划分中的优化问题

图的划分问题曾引起图论界的广泛关注，在文献[4]中讨论了k-单圈划分，本文进一步研究基于k-单圈划分的优化问题，即在一个赋权图中求一个最小权可k-单圈划分的支撑子图，以及对一个不存在k-单圈划分支撑子图的图，如何添最少的边使得它有k-单圈划分的支撑子图。     

极大平面图在不可定向曲面上强嵌入的一个注记

§ 1　IntroductionA strong embeddingμ( G) of a graph G in a surface S is such an embedding thateachface boundary of the surface is a circuit.( A strong embedding is also sometimes called acircular embedding,see[1 ] orclosed2 -cell embedding[2 ] ) .Graphsconsidered here are sim-ple( that is,they have no loops or multiple edges) .Terminology here follows those in[3] .In[1 ] ,Richter,Seymour and Siran proved that every3-connected planar graph canbe strongly embedded on some non-orientable sur…     

地图着色定理与图的曲面嵌入(Ⅲ)

<正> 用Z_(12s+6)(I)带附加条件 d3,若在一个次为3的顶点处有三个字母,如a,b,c,则各边流入的电流只能mod 3余1或2.而且,三个流入电流之和是Z_(12s+6)的由3的倍数形成的子群的生成元. 先构造一个梳图Γ_(2s+1).然后,通过结构变换把它变为Z_(12s+6)(I)的中心部分.最后,添上首尾部分.     

多重跳图的平面性

The infinite sequence {J^k5(G)} where Js(G) denotes the 5-jump graph of G, is planar if, and only if, G=cor(K3). For r-jump graph with r≥6, there does not exist a graph G such that the sequence {J^kr(G)} is planar.     

A POLYNOMIAL ALGORITHM FOR FINDING THEMINIMUM FEEDBACK VERTEX SET OF A3-REGULAR SIMPLE GRAPH

1IntroductionLetG=(VE)beaconnectedsimplegraph.AsubsetFofvertexsetViscalIedafeedbackvertexsetofGifthegraPhGFisaf0rest.ThecardinaIity0faminimumfeedbackvertexset0fGisdenotedbyf(G).AvertexsubsetJofvertexsetViscaJledallonseparatingindependentsetofG,ifJisanilldependentsetofVandGJisconnected.Thema-xiammcardinalityofnollseparatingindependelltsetofGisden0tedbyz(G)andiscalledthenonseparatingindepelldentnumberofG,AgraphGiscalledacactusifGisc0nnectedandanytwocyclesofGaredisjoint.Avertexvofacon…     

图的直径与Betti亏数

对于任意的正数Ｍ以及正整数ｄ≥４，存在直径为ｄ的ｉ－边连通无环图Ｇ使得ζ（Ｇ）≥Ｍ，其中ζ（Ｇ）是Ｇ的Ｂｅｔｔｉ亏数，ｉ＝１，２，３。