In this paper, the cycle＇s structure of embedded graphs in surfaces are studied. According to the method of fundamental cycles, the set C （C contains all shortest） is found. A undirected graph G with n vertices has...In this paper, the cycle＇s structure of embedded graphs in surfaces are studied. According to the method of fundamental cycles, the set C （C contains all shortest） is found. A undirected graph G with n vertices has at most O（N5） many shortest cycles; If the shortest cycle of G is odd cycle, then G has at most O（N3） many shortest cycles; If G has been embedded in a surface 8g （Ng, g is a constant）, then it has at most O（N3） shortest cycles, moreover, if the shortest cycle of G is odd cycle, then, G has at most O（N2） many shortest cycles. We can find a cycle base of G, the number of odd cycles of G, the number of even cycles of G, the number of contractible cycles of G, the number of non-contractible cycles of G, are all decided. If the ∏-embedded graph G has ∏-twosided cycles, then, C contains a shortest ∏-twosided cycle of G, there is a polynomially bounded algorithm that finds a shortest ∏-twosided cycle of a ∏-embedded graph G, the new and simple solutions about the open problem of Bojan Mohar and Carsten Thomassen are obtained.展开更多
In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentia...In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings 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） scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s＋3, which show that there are at least1/2× （200/9）s distinct genus embeddings for K12s＋3.展开更多
In this paper, the chromatic sum functions of rooted biloopless nonsepavable near-triangulations on the sphere and the projective plane are studied. The chromatic sum function equations of such maps are obtained. From...In this paper, the chromatic sum functions of rooted biloopless nonsepavable near-triangulations on the sphere and the projective plane are studied. The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equations of such maps are derived. An asymptotic evaluation and some explicit expression of enumerating functions are also derived.展开更多
基金Supported in part by the National Natural Science Foundation of China under Grant No.10771225 and11171114the scientific research projects of state ethnic affairs commission(14ZYZ016)
文摘In this paper, the cycle＇s structure of embedded graphs in surfaces are studied. According to the method of fundamental cycles, the set C （C contains all shortest） is found. A undirected graph G with n vertices has at most O（N5） many shortest cycles; If the shortest cycle of G is odd cycle, then G has at most O（N3） many shortest cycles; If G has been embedded in a surface 8g （Ng, g is a constant）, then it has at most O（N3） shortest cycles, moreover, if the shortest cycle of G is odd cycle, then, G has at most O（N2） many shortest cycles. We can find a cycle base of G, the number of odd cycles of G, the number of even cycles of G, the number of contractible cycles of G, the number of non-contractible cycles of G, are all decided. If the ∏-embedded graph G has ∏-twosided cycles, then, C contains a shortest ∏-twosided cycle of G, there is a polynomially bounded algorithm that finds a shortest ∏-twosided cycle of a ∏-embedded graph G, the new and simple solutions about the open problem of Bojan Mohar and Carsten Thomassen are obtained.
基金Supported by the National Natural Science Foundation of China(No.10771225,11171114)
文摘In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings 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） scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s＋3, which show that there are at least1/2× （200/9）s distinct genus embeddings for K12s＋3.
基金Supported by the National Natural Science Foundation of China (No. 10771225 10871021+1 种基金 71071016) Fundamental Research Funds for the Central Universities
文摘In this paper, the chromatic sum functions of rooted biloopless nonsepavable near-triangulations on the sphere and the projective plane are studied. The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equations of such maps are derived. An asymptotic evaluation and some explicit expression of enumerating functions are also derived.
