Let S = K1,3,K3, P4 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 non-empty S′ ⊆ 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 cubic, 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, and give graph-theoretic characterisations of S′-decomposable cubic graphs in some cases. © Springer International Publishing Switzerland 2016.
Decomposing cubic graphs into connected subgraphs of size three
RIZZI, ROMEO;
2016-01-01
Abstract
Let S = K1,3,K3, P4 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 non-empty S′ ⊆ 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 cubic, 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, and give graph-theoretic characterisations of S′-decomposable cubic graphs in some cases. © Springer International Publishing Switzerland 2016.File | Dimensione | Formato | |
---|---|---|---|
DecomposingCubicGraphs3.pdf
solo utenti autorizzati
Tipologia:
Versione dell'editore
Licenza:
Accesso ristretto
Dimensione
857.01 kB
Formato
Adobe PDF
|
857.01 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.