String Decompositions of Graphs

For a graph \(G\), if \(F\) is a nonempty subset of the edge set \(E(G)\), then the subgraph of \(G\) whose vertex set is the set of ends of edges in \(F\) is denoted by \(_G\). Let \(E(G) = \cup_{i \in I} E_i\) be a partition of \(E(G)\), let \(D_i = _G\) for each \(i\), and let \(\phi = (D_i | i \in I)\), then \(\phi\) is called a partition of \(G\) and \(E_i\) (or \(D_i\)) is an element of \(\phi\). Given a partition \(\phi = (D_i | i \in I)\) of \(G\), \(\phi\) is an admissible partition of \(G\) if for any vertex \(v \in V(G)\), there is a unique element \(D_i\) that contains vertex \(v\) as an inner point. For two distinct vertices \(u\) and \(v\), a \(u-v\) walk of \(G\) is a finite, alternating sequence \(u = u_0, e_1, u_1, e_2, \ldots, v_{n.1},e_n,u_n = v\) of vertices and edges, beginning with vertex \(u\) and ending with vertex \(v\), such that \(e_i = u_{i-1}u_i\) for \(i = 1, 2, \ldots, n\). A \(u-v\) string is a \(u-v\) walk such that no vertex is repeated except possibly \(u\) and \(v\), i.e., \(u\) and \(v\) are allowed to appear at most two times. Given an admissible partition \(\phi\), \(\phi\) is a string decomposition or \(SD\) of \(G\) if every element of \(\phi\) is a string.

In this paper, we prove that a \(2\)-connected graph \(G\) has an \(SD\) if and only if \(G\) is not a cycle. We also give a characterization of the graphs with cut vertices such that each graph has an \(SD\).