Multigraph Decomposition Into Multigraphs With Two Underlying Edges

Journal of Systemics, Cybernetics and Informatics

Miri Priesler¹  Michael Tarsi² 

[1] Ruppin Academic Center;Tel-Aviv University;

关键词: Decompositions;    Stars;    Intractability;    Multigraphs;    Multistars;   

DOI  :  

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown