Transition Polynomials, Double Covers, and Biomolecular Computing

Recent advances in biomolecular computing, assembling graphs from strands of DNA, require restricted oriented double coverings of the edges of a graph. We show that the generalized transition polynomial, a highly adaptable graph polynomial that encodes information about families of cycles in Eulerian graphs, provides a generating function formulation for this application. Although the requirements of the biomolecular construction are slightly different from a cycle double cover (an edge may be covered twice by the same “cycle ” for example), results from variations of cycle double covers inform the original problem from biomolecular computing. In particular, we use a theorem of C. Thomassen to specify precisely when a graph may be constructed from a single strand of DNA, and theorems of Hongbing and Zhu to characterize graphs that require at least m strands of DNA in their construction. Key words: graph polynomials, transition systems, Eulerian graphs, cycles, cycle double cover conjecture, bidirectional double tracing, oriented walks, biomolecular computing, DNA strands