Edge Decomposition into Isomorphic Copies ofsK1, 2Is Polynomial

Zbigniew Lonc


LetHbe 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.
Author Zbigniew Lonc (FMIS / DAC)
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
Journal seriesJournal of Combinatorial Theory Series B, ISSN 0095-8956
Issue year1997
ASJC Classification1703 Computational Theory and Mathematics; 2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
URL http://www.sciencedirect.com/science/article/pii/S0095895696917359
Score (nominal)40
Score sourcejournalList
Publication indicators Scopus Citations = 7; WoS Citations = 7; Scopus SNIP (Source Normalised Impact per Paper): 1999 = 1.627; WoS Impact Factor: 2006 = 0.792 (2) - 2007=0.927 (5)
Citation count*9 (2015-02-23)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?