Minimum Cycle Bases of Graphs on Surfaces 1

In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparat-ing cycles. In particular, some known results such as P.F.Stadler’s work on Halin graphs[11] and J.Leydold et al’s results on outer-planar graphs[8] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpola-tion theorem for the number of one-sided cycles contained in MCB of an embedded graph. Key Words Cycle base, facial cycle, graph embedding. AMS Classification: (2000)05C10,05C30,05C45. 1Supported by NNSF of China under granted number 1027104