Multigraph Decomposition Into Multigraphs With Two Underlying Edges
Miri Priesler, Michael Tarsi
Due to some intractability considerations, reasonable
formulation of necessary and sufficient conditions for decomposability
of a general multigraph G into a fixed connected multigraph H, is
probably not feasible if the underlying simple graph of H has three or
more edges. We study the case where H consists of two underlying
edges. We present necessary and sufficient conditions for H-
decomposability of G, which hold when certain size parameters of G
lies within some bounds which depends on the multiplicities of the two
edges of H. We also show this result to be "tight" in the sense that even
a slight deviation of these size parameters from the given bounds results
intractability of the corresponding decision problem. Full Text
|
