String Decompositions of Graphs

Abstract

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 $\varphi =(D_i|i\in I)$, then $\varphi$ is called a partition of $G$ and $E_i$ (or $D_i$) is an element of $\varphi$. Given a partition $\varphi =(D_i|i\in I)$ of $G$, $\varphi$ 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,\dots ,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,\dots ,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 $\varphi$, $\varphi$ is a string decomposition or $SD$ of $G$ if every element of $\varphi$ 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$.