Decomposition of multigraphs into isomorphic graphs with two edges (Q2761048)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Decomposition of multigraphs into isomorphic graphs with two edges |
scientific article; zbMATH DE number 1682910
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Decomposition of multigraphs into isomorphic graphs with two edges |
scientific article; zbMATH DE number 1682910 |
Statements
17 December 2001
0 references
graph
0 references
multigraph
0 references
decomposition into isomorphic subgraphs
0 references
matching
0 references
Decomposition of multigraphs into isomorphic graphs with two edges (English)
0 references
The authors consider the question of decomposing the edge set of a given graph into disjoint subsets, each of them inducing a subgraph isomorphic to a parameter graph \(H\). They solve the question for two-edge graphs \(H\) giving characterization theorems and polynomial time decision algorithms for the cases of \(H\) being two disjoint edges and a path of length two (the case of \(H\) being a duplicate edge is trivial, in that case \(G\) has a decomposition if and only if every edge of \(G\) has even multiplicity). Their algorithms improve on the time complexity of previously known ones.
0 references
