图的上可嵌入性与圈中顶点度  

Upper Embeddability of Graphs and the Degree of Vetex in Cycle

作　　者：任俊峰[1] 欧阳章东[1] 黄元秋[1] 

机构地区：[1]湖南师范大学数学与计算机科学学院,长沙 410081

出　　处：《应用数学学报》2008年第1期173-179,共7页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金资助项目(10771062)以及教育部新世纪优秀人才支持计划项目

摘　　要：本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了如下两个结果:(1)设G是2-边连通简单图,若对G中任意圈C,存在点x∈C满足:d(x)>3/|V(G)|+1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={X,Y;E}为简单二部图,且是2-边连通的.|X|=m,|y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足:d(x)>3/n+1,则图G是上可嵌入的,且不等式的下界是不可达的.Combined with the relationship between the upper embeddability of graphs and the max degree of vetex in cycle, this paper proves the following results by using a sufficient and necessary condition on non-upper embeddable graphs： （1） Let G be a 2-edge-connected simple graph.If for any cycle C in G, there is a vertex x satisfying d（x）〉3^--{V（G）}＋1, then 3 G is an upper embeddable graph and the bound is not achievable. （2） Let G^3={X, Y; E} be a simple bipartite graph, and G is 2-edge-connected.│X│=m,│Y│=n（m,n≥3）. If for any cycle C in G, there is a vertex x∈X and x∈X satisfying： d（x）〉3^--^n＋1, then G is an upper embeddable graph and the bound is not achievable.

关 键 词：图 圈 最大亏格 上可嵌入 BETTI亏数 二部图 

分 类 号：O157.5[理学—数学]