$E$-restricted Double Traces

Abstract

For a graph $G$ and $E\subseteq E(G)$, an $E$-restricted strong trace is a closed walk which traverses every edge from $E$ once in each direction and every other edge twice in the same direction, with no nontrivial repetition at any vertex. We characterize graphs admitting $E$-restricted strong traces as well as $E$-restricted $d$-stable traces, as well as directed (mixed graph) versions of these results. We explain how these characterizations upgrade the mathematical model for self-assembling polypeptide nanostructure design first presented by Gradi\v sar et al.\ in 2013.

29 pages, 4 figures; Substantially revised and expanded. Full proofs added (incl. mixed-graph versions), definitions sharpened, new corollary for E inducing a forest or cycle (subsuming results of Wang et al.), and a new section on algorithmic aspects (O(m^2) construction of the trace; tractability of the spanning-tree condition posed as a conjecture)