An algebraic approach to enumerating non-equivalent double traces in graphs
Preprint
Abstract
Recently designed biomolecular approaches to build single chain polypeptide polyhedra as molecular origami nanostructures have risen high interest in various double traces of the underlying graphs of these polyhedra. Double traces are walks that traverse every edge of the graph twice, usually with some additional conditions on traversal direction and vertex neighborhood coverage. Given that double trace properties are intimately related to theefficiency of polypeptide polyhedron construction, enumerating all different possible double traces and analyzing their properties is an important step in the construction. In the paper, we study the automorphism group of double traces and present an algebraic approach to this problem, yielding a branch-and-bound algorithm.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Antiparallel d-stable traces and a stronger version of ore problemJournal of Mathematical Biology, 2016
- DNA origami and the complexity of Eulerian circuits with turning costsNatural Computing, 2014
- TOPOFOLD, the designed modular biomolecular folds: polypeptide‐based molecular origami nanostructures following the footsteps of DNAWIREs Nanomedicine and Nanobiotechnology, 2014
- Bidirectional retracting-free double tracings and upper embeddability of graphsJournal of Combinatorial Theory, Series B, 1990
- Finding a maximum-genus graph imbeddingJournal of the ACM, 1988
- Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations1978