Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial (Q1354723)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial |
scientific article |
Statements
Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial (English)
0 references
3 June 1997
0 references
Let \(H\) be a fixed graph. We say that a graph \(G\) admits an \(H\)-decomposition if the set of edges of \(G\) can be partitioned into subsets generating graphs isomorphic to \(H\). Denote by \({\mathcal P}_H\) the problem of existence of an \(H\)-decomposition of a graph. The Holyer problem is to classify the problems \({\mathcal P}_H\) according to their computational complexities. In this paper we show that the problem \({\mathcal P}_H\) is polynomial when \(H\) is the union of \(s\) disjoint 2-edge paths.
0 references
edge decomposition
0 references
Holyer problem
0 references
computational complexities
0 references
paths
0 references