Notes
In 2013, Gradišar et al. presented a novel self-assembly strategy for polypeptide nanostructure design. The main success of their research is a construction of a polypeptide self-assembling tetrahedron by concatenating 12 coiled-coil-forming segments in a prescribed order. More precisely, a single polypeptide chain consisting of 12 segments was routed through 6 edges of the tetrahedron in such a way that every edge was traversed exactly twice. In this way, 6 coiled-coil dimers were created and interlocked into a stable tetrahedral structure. A polyhedron ?$P$?, which is composed from a single polymer chain, can be naturally represented by a graph ?$G(P)$? of the polyhedron. As in the self-assembly process, every edge of ?$G(P)$? corresponds to a coiled-coil dimer, exactly two segments are associated with every edge of ?$G(P)$?. We therefore introduce a strong (and a ?$d$?-stable) trace of a graph as a closed walk that traverses every edge of graph twice, also called a double trace, and for every vertex ?$v$?, there is no subset ?$N$? of its neighbors, with ?$1 \leq |N| < d(v)$? (?$1 \leq |N| \leq d$?), such that every time the walk enters ?$v$? from ?$N$?, it also exits to a vertex in ?$N$?, respectively. We then establish the duality between single face embeddings of graphs into surfaces of higher genera and strong traces, and use classical results of Edmonds and Ringel to charecterize graphs that admit strong traces (every connected graph) and ?$d$?-stable traces (every connected graph ?$G$? with minimal degree ?$\delta(G) > d$?). Every edge is traversed twice in a double trace. Consequently, if a double trace ?$W$? traverses an edge ?$e$? in the same direction twice, then we call ?$e$? a parallel edge (with respect to ?$W$?), otherwise e is an antiparallel edge. A double trace ?$W$? of a graph ?$G$? is then a parallel double trace if every edge of ?$G$? is parallel (with respect to ?$W$?) and an antiparallel double trace if every edge of ?$G$? is antiparallel (with respect to ?$W$?). The motivation for this approach naturally arises from the properties of selfassembling nanostructures. We characterize graphs which admit: (i) parallel strong traces as Eulerian graphs, (ii) parallel ?$d$?-stable traces as Eulerian graphs with minimal degree ?$> d$?, (iii) antiparallel strong traces as connected graphs ?$G$? in which there exists a spanning tree ?$T$? with the property that every connected component of the co-tree ?$G - E(T)$? has an even number of edges, and (iv) antiparallel ?$d$?-stable traces as connected graphs ?$G$? with minimal degree ?$> d$? in which there exists a spanning tree ?$T$? with the property that every connected component of the co-tree ?$G - E(T)$? is even or contains a vertex of degree at least ?$2d + 2$?. The last result also generalizes a problem posed by Ore back in the 1950s and solved by Thomassen almost 40 years later. In our notation, problem raised by Ore could be read as characterizing the graphs, which admit antiparallel 1-stable traces. For solving this problem, we among other use some new discoveries about spanning trees similair to Xuong trees. The concept of ?$E$?-restricted traces, that is, a double trace where every edge from a set ?$E(G) \subseteq E$? is antiparallel and every edge from ?$E(G) \setminus E$? is parallel, on the one hand unify the results about parallel and antiparallel double traces while on the other hand also bid us more control over the properties of self-assembling nanostructures during their construction when being used as a mathematical model. Results regarding ?$E$?-restricted double traces were already well known and independently proven by Vastergaard and by Fleischner, while theorems about ?$E$?-restricted strong traces and ?$E$?-restricted ?$d$?-stable traces are new results. Since graphs admit multiple double traces, we define double traces ?$W$? and ?$W'$? of a graph ?$G$? to be equivalent, if ?$W'$? can be obtained from ?$W$? by reversion ?$W$?, by shifting ?$W$?, by applying a permutation on ?$W$? induced by an automorphisms of ?$G$?, or using any combination of the previous three operations. In order to be able to maximize the probability which strong trace to choose for a given nanostructure so that an appropriate polypeptide chain will self assemble into the desired structure, we develop two algorithms for generating all non equivalent strong traces for a given graph ?$G$?. The first algorithm is based on an algebraic approach and uses some new discoveries about the automorphism group of double traces, while the second relies on topological properties of a graph and has complexity ?$O(mf)$? for cubic graphs, where ?$m$? is the number of edges and ?$f$? is the number of faces in some fixed embedding of ?$G$?.