【摘要】 任韩和李刚在图的最大亏格综述一文"Survey of maximum genus of graphs"[J East China NormUniv Natur Sci,Sep.2010,No.5,1-13]中,全面地阐述了近30年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想:猜想1设G为简单连通图,且G的每条边含在一个三角形K3中,则G是上可嵌入的.猜想2设c为任意的正数,则存在一个自然数N(c),使得对每一个图G,若G的点数n N(c),且最小度δ(G)cn,则G是上可嵌入的.本文的主要工作是否定上述两个猜想,同时探讨上述猜想成立的条件且得了一些新结果,并提出有关进一步研究的问题.更多还原

【Abstract】 In "Survey of maximum genus of graphs" [J East China Norm Univ Natur Sci, Sep. 2010, No. 5, 1–13], Ren and Li reviewed research developments on maximum genus of graphs in graph embedding theory since 1971, and presented the following two conjectures: Conjecture 1. Let G be a simple connected graph such that each edge is contained in a triangle K3. Then G is upper-embeddable. Conjecture 2. Let c be an arbitrary positive number. Then, there exists a natural number N(c) such that for every graph G of order n N(c) and minimum degree δ(G) cn, G is upper-embeddable. In this paper, we negate the above two conjectures, and discuss the condition for which the above conjectures is true and obtain some new results. Finally, we present several research problems that would be developed in the future.更多还原