Parallelism of stable traces

Keywords: Eulerian graph, parallel d-stable trace, nanostructure design, self-assembling, polypeptide


A parallel d-stable trace is a closed walk which traverses every edge of a graph exactly twice in the same direction and for every vertex v, there is no subset X ⊆ N(v) with 1 ≤ |N| ≤ d such that every time the walk enters v from X, it also exits to a vertex in X. In the past, d-stable traces were investigated as a mathematical model for an innovative biotechnological procedure – self-assembling of polypeptide structures. Among other, it was proven that graphs that admit parallel d-stable traces are precisely Eulerian graphs with minimum degree strictly larger than d. In the present paper we give an alternative, purely combinatorial proof of this result.