SMALLEST (1,2)-EULERIAN WEIGHT AND SHORTEST CYCLE COVERING

The concept of a (1,2)-eulerian weight was introduced and studied in several papers recently by Seymour, Alspach, Goddyn, and Zhang. In this paper, we proved that if G is a 2-connected simple graph of order n (n greater than or equal to 7) and w is a smallest (1,2)-eulerian weight of graph G, then \E(w=even)\ less than or equal to n - 4, except for a family of graphs. Consequently, if G admits a nowhere-zero 4-flow and is of order at least 7, except for a family of graphs, the total length of a shortest cycle covering is at most \V(G)\ + \E(G)\ - 4. This result generalizes some previous results due to Bermond, Jackson, Jaeger, and Zhang. (C) 1994 John Wiley & Sons, Inc.