Shortest Co-Cycle Bases Of Graphs
Han Ren, J. P. Ren · 2009
In this paper we investigate the structure of the shortest co-cycle base(or SCB in short) of connected graphs, which are related with map geometries, i.e., Smarandache 2-dimensional manifolds. By using a Hall type theorem for base transformation, we show that the shortest co-cycle bases have the same structure (there is a 1-1 correspondence between two shortest co-cycle bases such that the corresponding elements have the same length). As an application in surface topology, we show that in an embedded graph on a surface any nonseparating cycle can’t be generated by separating cycles. Based on this result, we show that in a 2-connected graph embedded in a surface, there is a set of surface nonseparating cycles which can span the cycle space. In particular, there is a shortest base consisting surface nonseparating cycle and all such bases have the same structure. This extends a Tutte’s result [4].