Multigraph decomposition into multigraphs with two underlying edges

Abstract

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.

Keywords

• decomposition
• multigraph
• npc
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]