| Abstract: | Let (G, w) denote a simple graph G with a weight function w : E(G) ← {0, 1, 2}. A path cover of (G, w) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex v, w(v) is the sum of the weights of the edges incident with v; v is called an odd (even) vertex if w(v) is odd (even). We prove that if every vertex of (G, w) is incident with at most one edge of weight 2, then (G, w) has a path cover P such that each odd vertex occurs exactly once, and each even vertex exactly twice, as an end of a path of P. We also prove that if every vertex of (G, w) is even, then (G, w) has a path cover P such that each vertex occurs exactly twice as an end of a path of P. © 1995 John Wiley & Sons, Inc. |
