TriangularEmbeddingsofDenseGraphs

• 作者: MADengju RENHan SHANSongling
• 来源期刊: 昆明理工大学学报（自然科学版）
• 学科: 数学
• 关键词: triangularembedding Hamiltonian-embeddings genuembedding
• 年，卷（期）: 2012,（2）
• 页码范围: 83-87
• 分类号: O157.5
• 语种: 中文

摘要

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.