### Deriving graphs with a retracting-free bidirectional double tracing

#### Abstract

A *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 3*h* 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.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.1

#### References

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.

DOI:10.1016/0012-365x(73)90067-8.

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.

DOI:10.5614/ejgta.2017.5.1.13.

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.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

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