Minimum Genus Embeddings of the Complete Graph

In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding （or rotation） schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K12s＋8 in orientable surfaces, which show that there are at least 10/5 × （200/9）^s distinct minimum genus embeddings for K12s＋8 in orientable surfaces. We have also proved that K12s＋8 has at least 10/3× （200/9）^s distinct minimum genus embeddings in non-orientable surfaces.

The Cycle Structure for Directed Graphs on Surfaces

In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.

Chromatic Sums of Nonseparable Near-Triangulations on the Projective Plane

In this paper, we study the chromatic triangulations on the sphere and the projective plane. sum functions of rooted nonseparable near- The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equa- tions of such maps are derived. Applying chromatic sum theory, the enumerating problem of different sorts maps can be studied, and a new method of enumeration can be obtained. Moreover, an asymptotic evaluation and some explicit expression of enumerating functions are also derived.