TriangularEmbeddingsofDenseGraphs

摘要：

G.Ringelposedtheproblemtofindasufficientandnecessaryconditionforagraphtotriangulateanorientablesurface.B.MoharandC.Thomassenraisedthefollowingproblem:Doesthereexistanumberc:0<c<1,suchthateverygraphwithnvertices,whoseminimaldegreeisatleastcnandwhosenumberofedgesisdivisibleby3,whichtriangulatesanorientablesurface?Here,inthispaperweshowthatsuchnumbercdoesnotexist,thatis,foranynumberc:0<c<1,thereareinfitelymanygraphsofordern,withδG)≥cn,and|E(G)|≡0(mod3)whichcanttriangulateanyorientablesurface.Furthermore,weinvestigatetheHamiltonianembeddingsofKn,nandshowthatKn,nhasatleast((n-1)!)2distinctembeddingsinSg,(g=n-1()2),whichimpliesthatKn,n,nhasatleastn!((n-1)!)2distincttwo-facecolorabletriangularembeddingsinthesamesurface.

关键词：triangularembedding、Hamiltonian-embeddings、genuembedding

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2012-08-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：83-87