Deriving graphs with a retracting-free bidirectional double tracing

Vladimir R. Rosenfeld


retracting-free bidirectional double tracing in a graph G is a closed walk which traverses every edge exactly once in each direction and such that no edge is succeeded by the same edge in the opposite direction. Studying the class Ω of all graphs admitting a retracting-free bidirectional double tracing was proposed by Ore (1951) and is, by now, of practical use to (bio)nanotechnology. In particular, this field needs various molecular polyhedra that are constructed from a single chain molecule in a retracting-free bidirectional double-tracing way.

A cubic graph Q ∈ Ω has 3h edges, where h is an odd number ≥3. The graph of the triangular prism is the minimum cubic graph Q ∈ Ω, having 6 vertices and 9 edges. The graph of the square pyramid is the minimum polyhedral graph G in Ω, having 5 vertices and 8 edges.

We analyze some possibilities for deriving new Ω-graphs from a given graph G ∈ Ω or G ∉ Ω using graph-theoretical operations. In particular, there was found that every noncycle Eulerian graph H admits a retracting-free bidirectional double tracing (H ∈ Ω), which is a partial solution to the problem posed by Ore.


spanning tree, cotree, retracting-free bidirectional double tracing

Full Text:




R.B. Eggleton and D.K. Skilton, Double tracing of graphs, Ars Combin. 17A (1984), 307–323.

G. Fijavz, T. Pisanski, and J. Rus, Strong traces model of self-assembly polypeptide structures, MATCH Commun. Math. Comput. Chem. 71 (2014), 199–212.

H. Gradisar, S. Bozic, T. Doles, D. Vengust, I. Hafner Bratkovic, A. Mertelj, B. Webb, A. Sali, S. Klav ˇ zar, and R. Jerala, Design of a single-chain polypeptide tetrahedron assembled from coiled-coil segments, Nat. Chem. Biol. 9(6) (2013), 362–366.

F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.

F. Harary and A.J. Schwenk, The number of caterpillars, Discrete Mathematics 6(4) (1973), 359–365.


S. Klavzar and J. Rus, Stable traces as a model for self-assembly of polypeptide nanoscale polyhedrons, MATCH Commun. Math. Comput. Chem. 70(1) (2013), 317–330.

V. Kocar, S. Bozic Abram, T. Doles, N. Basic, H. Gradisar, T. Pisanski, and R. Jerala, TOPO-FOLD, the designed modular biomolecular folds: polypeptide-based molecular origami nanostructures following the footsteps of DNA, WIREs Nanomed. Nanobiotechnol. 7 (2015), 218–237.

V. Kocar, J.S. Schreck, S. Ceru, H. Gradisar, N. Basic, T. Pisanski, J.P.K. Doye, and R. Jerala, Design principles for rapid folding of knotted DNA nanostructures, Nat. Commun. 7 (2016), 1–8.

DOI: 10.1038/ncomms10803.

A. Ljubetic, I. Drobnak, H. Gradi ˇ sar, and R. Jerala, Designing the structure and folding path-way of modular topological ionanostructures, Chem. Commun. 52 (2016), 5220–5229.

O. Ore, A problem regarding the tracing of graphs, Elem. Math. 6 (1951), 49–53.

V.R. Rosenfeld, Traversing every edge in each direction once, but not at once: Cubic (polyhedral) graphs, Electron. J. Graph Theory Appl. (EJGTA) 5(1) (2017), 132–141.


J. Rus, Antiparallel d-stable traces and a stronger version of Ore problem, J. Math. Biol. (2016), to appear. DOI: 10.1007/s00285-016-1077-2.

J. Rus, Parallelism of stable traces, Preprint series, IMFM, ISSN 2232-2094, no. 1197, March 24, 2014 (2014), 1–16.

C. Thomassen, Bidirectional retracting-free double tracings and upper embeddability of graphs, J. Combin. Theory Ser. B 50 (1990) 198–207.

D.J. Troy, On traversing graphs, Amer. Math. Monthly 73 (1966), 497–499.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats