Deriving graphs with a retracting-free bidirectional double tracing
| Main Author: | Rosenfeld, Vladimir R.; Department of Computer Science and Mathematics, Ariel University, Ariel 4070000, Israel |
|---|---|
| Other Authors: | Ministry of Absorption of the State Israel (through fellowship “Shapiro”) |
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2022
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/739 https://www.ejgta.org/index.php/ejgta/article/view/739/pdf_226 https://www.ejgta.org/index.php/ejgta/article/downloadSuppFile/739/111 |
Daftar Isi:
- 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.