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.展开更多
基金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.
