Triangular Embeddings of Dense Graphs
Dengju Ma · Journal of Kunming University of Science and Technology · 2012
G.Ringel posed the problem to find a sufficient and necessary condition for a graph to triangulate an orientable surface.B.Mohar and C.Thomassen raised the following problem: Does there exist a number c:0c1,such that every graph with n vertices,whose minimal degree is at least cn and whose number of edges is divisible by 3,which triangulates an orientable surface? Here,in this paper we show that such number c does not exist,that is,for any number c:0c1,there are infitely many graphs of order n,with δG)≥cn,and |E(G)|≡0(mod 3) which can't triangulate any orientable surface.Furthermore,we investigate the Hamiltonian embeddings of Kn,n and show that Kn,n has at least((n-1)!)2 distinct embeddings in Sg,(g=n-1 2)),which implies that Kn,n,n has at least n!((n-1)!)2 distinct two-face colorable triangular embeddings in the same surface.