COVERING WEIGHTED GRAPHS BY EVEN SUBGRAPHS

A weighted graph is one in which each edge e is assigned a nonnegative number w(e), called the weight of e. The weight of a subgraph is the sum of the weights of its edges. An even graph is a graph every vertex of which is of even degree. A cover of a graph G is a collection of its subgraphs which together cover each edge of G at least once. A cover is called an (l, m)-cover if each edge of G is covered either exactly l or exactly m times. We prove that every bridgeless graph has a (2, 4)-cover by four even subgraphs of total weight at most ( 20 9) w(G). As a corollary, this result yields a weighted generalization of a result found by J. C. Bermond, B. Jackson, and F. Jaeger (J. Combin. Theory Ser. B 35, 1983, 299-308) and N. Alon and M. Tarsi (SIAM J. Algebraic Discrete Methods 6, 1985, 345-350). © 1990.