Path decompositions of multigraphs

✍ Scribed by Leizhen Cai

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

✦ Synopsis

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and p(x) respectively. Define the least even integer 2 p(x), if d(x) is even, the least odd integer 2 p(x), if d(x) is odd.

In this paper it is shown that every multigraph G admits a faithful path decomposition-a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly 4(x) paths in P . This result generalizes Lovasz's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture. 0 1995 John Wiley & Sons, Inc. *An odd graph is a graph where each vertex is incident with an odd number of edges.