Structures Of Co-cycle Spaces

In this thesis, we study the structure of co-cycle spaces of connected graphs, which is an important subject in graph theory. However, compared with the relatively mature circle space theory, co-cycle spaces has been much less researched. As they're mutually orthogonal, co-cycle spaces is closely related to cycle spaces. Firstly, we prove that the structure of shortest co-cycle bases is unique. Secondly, by the properties of co-cycles, we find that any separating cycle can't be generated by separating cycles. Moreover, we give a polynomial bounded algorithm for finding the shortest co-cycle. As an application, we partly answer the open question raised by Thomassen[18]. In the second part, we discuss the lower bound for the number of triangles having the same color in any 2-edge-colored complete graph, and find the exact number of such 0-1 triangles. The results will be given as follows:1. By using a Hall type theorem for base transformation, we show that the shortest co-cycle bases have the same structure (i.e. there is a 1-1 correspondence between any two shortest co-cycle bases such that the corresponding elements have the same length).2. By the definition of geometric dual multigraph G~* of an embedded graph G, we find that when C is a cycle of G, it's separating if and only if C~* is a co-cycle of G~*, where C~* is the set of edges corresponding those of C. As an application, we show that any nonseparating cycle can't be generated by separating cycles.3. By an improved Ford-Fulkerson algorithm, we obtain a polynomially bounded algorithm for finding the shortest co-cycle, meanwhile, in the case of projective plane embedded graph we answer the open question raised by Thomassen[18].4. By means of adjacency matrix, we get the lower bound for the number of triangles having the same color in any 2-edge-colored complete graph, and give a special case for the exact number.