Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184362
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:37:28 AM
Last modification on : Tuesday, January 1, 2019 - 6:46:02 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:00:20 AM

File

dmAE0146.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184362, version 1

Collections

Citation

Miri Priesler, Michael Tarsi. Multigraph decomposition into multigraphs with two underlying edges. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.231-234. ⟨hal-01184362⟩

Share

Metrics

Record views

290

Files downloads

823