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 constru...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.展开更多
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 co...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.展开更多
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 chromati...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.展开更多
基金Supported by NSFC(Grant Nos.10771225,11171114)the Scientific Research Pro jects of State Ethnic Affairs Commission(Grant No.14ZYZ016)
文摘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.
基金Supported by NSFC(Grant No.10771225)Fundamental Research Funds for the Central University
文摘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.
基金Supported by National Natural Science Foundation of China (Grant No. 10771225)
文摘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.