Edge Decomposition into Isomorphic Copies ofsK1, 2Is Polynomial
AbstractLetHbe a fixed graph. We say that a graphGadmits anH-decomposition if the set of edges ofGcan be partitioned into subsets generating graphs isomorphic toH. Denote by PHthe problem of exisitence of anH-decomposition of a graph. The Holyer problem is to classify the problems PHaccording to their computational complexities. In this paper we show that the problem PHis polynomial whenHis the union ofsdisjoint 2-edge paths.
|Journal series||Journal of Combinatorial Theory Series B, ISSN 0095-8956|
|ASJC Classification||; ;|
|Publication indicators||= 7; = 7; : 1999 = 1.627; : 2006 = 0.792 (2) - 2007=0.927 (5)|
|Citation count*||9 (2015-02-23)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.