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 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.
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.