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
    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
    0 references
    edge decomposition
    0 references
    Holyer problem
    0 references
    computational complexities
    0 references
    paths
    0 references

    Identifiers