The Cycle's Structure of Embedded Graphs in Surfaces

Zhao-xiang LI^{1}, Han REN^{2}

1 Department of Mathematics, Minzu University of China, Beijing 100081, China;
2 Department of Mathematics, East China Normal University, Shanghai 200062, China

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 Gwith n vertices has at most O(n^{5}) many shortest cycles; If the shortest cycle of C is odd cycle, then G has at most O(n^{3}) many shortest cycles; If G has been embedded in a surface Sg (Ng, g is a constant), then it has at most O(n^{3}) shortest cycles, moreover, if the shortest cycle of G is odd cycle, then, G has at most O(n^{2}) 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 and 11171114, the scientific research projects of state ethnic affairs commission (14ZYZ016).

Bondy, J.A., Murty, U.S.R. Graph theory with applications. The Macmillan Press Ltd., New York, 1976

[2]

Cabello, Sergio. Finding shortest contractible and shortest separating cycles in embedded graphs. ACM Transactions on Algorithms, 6(2), Article 24: 1-18 (2010)

[3]

Cummins, R.L. Hamilton circuits in tree graphs. IEEE Trans Circuit Theory, 13: 82-96 (1966)

[4]

Glover, F., Klingman, D. Finding minimum spanning trees with a fixed number of links at a node, Com- binatorial Programming: Methods and Applications. D. Reidel Publishing Company, Dordrecht, 1975, 191-201

[5]

Gribb, D.W., Ringeisen, R.D., Shier, D.R. On cycle bases of graph. Congressus Numerantium, 32: 221-229 (1981)

[6]

Halford, T.R., Chugg, K.M. An algorithm for counting short cycles in bipartite graphs. IEEE Transactions on Information Theory, 52(1): 287-292 (2006)

[7]

Holzmann, C.A., Harary, F. On the tree graph of a matroid. SIAM J. Appl. Math., 22: 187-193 (1972)

[8]

Horton, J.D. A polynomial-time algorithm to find the shortest cycle base of a graph. SIAM. JComput., 16: 359-366 (1987)

[9]

Liu, G.Z. On the connectivities of tree graphs. Journal of Graph Theory, 12: 453-454 (1988)

[10]

Mackay, D.J., Neal, R.M. Near shannon limited performance of low density parity check codes. IEE Electron.Lett., 32: 1645-1646 (1996)

[11]

Mohar, B., Thomassen, C. Graphs on surfaces. The Johns Hopkins University Press, Baltimore, London, 2001

[12]

Monien, B., Paderborn. The complexity of determining a shortest cycle of even length. Computing, 31: 355-369 (1983)

[13]

Ren, Han, Liu, Y.P., Ma, D.J., Lu, J.J. Generating cycle spaces for graphs on surfaces with small genera. European Journal of Combinatorics, 25: 1087-1105 (2004)

[14]

Thomassen, C. Embeddings of graphs with no short noncontractible cycles. Journal of Combinatorial Theory, Series B, 48: 155-177 (1990)

[15]

Thomassen, C. Five-coloring maps on surfaces. J. of Combin. Theory, Ser. B., 59: 89-105 (1993)

[16]

Tutte, W.T. A homotopy theorem for matroids I. Trans AMS, 88: 144-160 (1958)

[17]

White, A.L. Theory of Matroids. Cambridge University Press, London, 1986, 63-80

[18]

Zha, X., Zhao, Y. On nonnull separating circuits in embedded graphs. In Graph structure theory (Seattle, WA, 1991). Contemp. Math. 147, Amer. Math. Soc, Providence, RI, 1993, 349-363