摘要
本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了如下两个结果:(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.
出处
《应用数学学报》
CSCD
北大核心
2008年第1期173-179,共7页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金资助项目(10771062)以及教育部新世纪优秀人才支持计划项目
关键词
图
圈
最大亏格
上可嵌入
BETTI亏数
二部图
graph
cycle
maximum genus
upper embeddability
Betti deficiency number
bipartite graph
