Let S = { K 1 , 3 , K 3 , P 4 } be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph G into graphs taken from any nonempty S ' subset of S. The problem is known to be NP-complete for any possible choice of S ' in general graphs. In this paper, we assume that the input graph is subcubic (i.e., all its vertices have degree at most 3), and study the computational complexity of the problem of partitioning its edge set for any choice of S '. We identify all polynomial and NP-complete problems in that setting.

Decomposing subcubic graphs into claws, paths or triangles

Romeo Rizzi;
2021

Abstract

Let S = { K 1 , 3 , K 3 , P 4 } be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph G into graphs taken from any nonempty S ' subset of S. The problem is known to be NP-complete for any possible choice of S ' in general graphs. In this paper, we assume that the input graph is subcubic (i.e., all its vertices have degree at most 3), and study the computational complexity of the problem of partitioning its edge set for any choice of S '. We identify all polynomial and NP-complete problems in that setting.
decomposition
edge partition
NP-completeness
subcubic graph
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/1054197
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact