Cycle covering in bridgeless graphs (Q1069955): Difference between revisions

A cycle cover of a graph G is a system of cycles of G with the property that each edge of G is contained at least in one of them. A vertex cover of G with cycles is a system of cycles of G such that each vertex of G is contained at least in one of them. The length of such a cover is the sum of lengths of all of its cycles. (If weights are assigned to edges, then the length of a circuit is the sum of weights of all its edges; otherwise it is the number of edges.) For graphs with weighted edges it is proved that every bridgeless graph G admits a cycle cover of length at most \(m+5| t| /4\), where m is the number of edges and \(| t|\) is the maximal sum of weights of edges of a spanning tree of G. Every bridgeless graph G without weights of edges admits a cycle cover of length at most \(m+5(n-1)/4\), where n is the number of vertices of G. If G is a graph such that every vertex lies in a cycle, then G has a vertex cover with cycles of length at most 50(n- 1)/23. Some problems and conjectures are proposed.