String decompositions of graphs (Q2713617)

The authors prove, among other results, that a 2-connected graph \(G=(V,E)\) has a string decomposition (SD) iff \(G\) is not a cycle. An SD is a partition \(P\) of \(E\) into strings, which are defined to be the walks in \(G\) in which inner vertices do not repeat and the two distinct endvertices repeat each at most twice (a cycle is not a string), such that every vertex of \(G\) of degree at least 2 is the inner vertex of a unique string of \(P\). In path decompositions (PD) every string is in addition required to be a path. It is proved that every 3-connected graph has a PD. Necessary and sufficient conditions are given, in terms of end-blocks, for a graph with cut vertices to have an SD or a PD. The paper is at some places hard to understand because of its bad English.