Path covers of weighted graphs

✍ Scribed by Genghua Fan

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 318 KB
• Volume: 19
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190190114

✦ Synopsis

Let (G, w ) denote a simple graph G with a weight function w : €(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 u , w ( v ) is the sum of the weights of the edges incident with U ; U is called an odd (even) vertex if w ( v ) is odd (even). We prove that if every vertex of (G, w ) is incident with a t 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 .