Parallelism of stable traces

Abstract

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\subseteq N(v)$ with $1\le |N|\le 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.

16 pages, 8 figures

References in corpus (1)

• Antiparallel d-stable Traces and a Stronger Version of Ore Problem