On shortest cocycle covers of graphs (Q1070245)

Let G be a graph having vertex set V and edge set E. If \(S\subseteq V\), then the cocycle of G defined by S, denoted by \(\omega_ G(S)\), is the set of edges of G with exactly one end in S. A cocycle of G is any set of edges of the form \(\omega_ G(S)\) for some \(S\subseteq V\). A cocycle cover of the graph G is a family C of cocycles of G such that each edge of G belongs to at least one member of C. Further, the length of C, denoted by \(\ell (C)\), is the sum of the cardinalities of its members. The authors point out that for a loopless graph G, having edge set E, a cocycle cover C has length less than \(2| E|\). The authors further show that there exists no \(\alpha <2\) such that every loopless graph with edge set E has a cocycle cover with length at most \(\alpha\) \(| E|\). To accomplish this it is shown that the minimum length of all cocycle covers, of the complete graphs of order n, is \((n-1)^ 2\) for \(n>8\).