Premium
Path decompositions of multigraphs
Author(s) -
Cai Leizhen
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190303
Subject(s) - multigraph , combinatorics , mathematics , vertex (graph theory) , conjecture , partition (number theory) , multiplicity (mathematics) , integer (computer science) , path (computing) , decomposition theorem , generalization , discrete mathematics , upper and lower bounds , graph , computer science , mathematical analysis , programming language
Let G be a loopless finite multigraph. For each vertex x of G , denote its degree and multiplicity by d ( x ) and μ( x ) respectively. Define Ø( x ) = the least even integer ≥ μ( x ), if d ( x ) is even, the least odd integer ≥ μ( 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 Ø( x ) paths in P. This result generalizes Lovász'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. © 1995 John Wiley & Sons, Inc.