Deriving graphs with a retracting-free bidirectional double tracing

Vladimir R. Rosenfeld

Department of Computer Science and Mathematics Ariel University, Ariel 4070000, Israel

vladimir rosenfeld@yahoo.com

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 6∈ Ω 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: spanning tree, cotree, retracting-free bidirectional double tracing

Mathematics Subject Classification: 05C45, 92E10, 94C15

DOI: 10.5614/ejgta.2022.10.2.1

Received: 5 December 2018, Revised: 17 April 2022, Accepted: 21 April 2022.

1. Preliminaries

In 1951, Ore [10] posed a problem, asking for a characterization of graphs that admit 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. The problem was partially solved in [15] and [1], and completely solved almost 40 years later by Thomassen [14]. The further results were obtained in [2, 6, 12, 13]. We denote by \(\Omega\) the class of all graphs about which Ore posed his question [10]. The closed walk under consideration [1, 10, 14, 15] is called here a retracting-free bidirectional tracing [14]. Studying the class \(\Omega\) [1, 2, 6, 10, 12–15] is, in particular, of practical use to nanotechnology [3, 7–9]. Nanotechnologists construct various molecular polyhedra from a single chain molecule by winding it onto a polyhedron's skeleton in a retracting-free bidirectional double-tracing way [3, 7–9].

Let Q=(V,E) be a simple cubic graph with the vertex set V and edge set \(E\left(|V|=n,|E|=m=3n/2\right)\). A spanning tree T of Q is a subtree covering all the vertices of \(Q\left(|V(T)|=n;|E(T)|=n-1\right)\). Its cotree \(Q-E(T)\left(|V(Q-E(T))|=n;|E(Q-E(T))|=(n+2)/2\right)\) is a graph Q less all edges belonging to T. Thus, the cotree Q-E(T) of a spanning tree T in a connected graph Q is the spanning subgraph of Q containing exactly those edges of Q which are not in T [4].

Thomassen proved the following (Theorem 3.3 of [14]):

Theorem 1. A connected multigraph G has a retracting-free bidirectional double tracing if and only if G has no vertex of degree 1 and has a spanning tree T such that each connected component of G - E(T) either has an even number of edges or contains a vertex which in G has degree at least 4.

A more specific result is [11]:

Corollary 1.1. A cubic graph Q admits 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 if and only if Q has a spanning tree T such that each (connected) component of the cotree Q - E(T) has an even number of edges and is either a proper cycle or simple path of length \(\geq 0\).

Another corollary is [11]:

Corollary 1.2. Let a cubic graph Q admit 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 \((Q \in \Omega)\). Then, Q has an odd number |E(Q)| = 3h of edges (where \(h = 3, 5, 7, \ldots\)).

The following lemma determines the number of all simple paths in a cotree Q - E(T) [11]:

Lemma 2. Let T be an arbitrary spanning tree of a simple cubic graph Q. Then, Q-E(T) contains exactly (n-2)/2 simple paths of lengths \(\geq 0\), while the other (connected) components, if any, are proper cycles. (Recall that for \(Q \in \Omega\), Theorem 1 imposes the restriction on each component of Q-E(T) to have an even number of edges.)

Denote by \(c_k\) and \(p_l\) the numbers of cycles of length k and paths of length l in Q-E(T), respectively, where \(k=4,6,8,\ldots,2h\) and \(l=0,2,4,\ldots,2h\) \((h\in\mathbb{N}\setminus2\mathbb{N})\). Some simple relations for these numbers are known, e.g. [11]:

Lemma 3. Let \(Q \in \Omega\) and let Q - E(T) obey Corollary 1.1. Then,

\[\sum_{k=4}^{n} kc_k + \sum_{l=0}^{n} (l-1)p_l = 2 \quad (k, l \in 2\mathbb{N}).\] (1)

Here, we turn to the main section, where we deduce some other results.

2. The main part

Let \(n_j = n_j(G)\) \((j \in \mathbb{N})\) be the number of vertices of valency j in a graph G. We state:

Lemma 4. Let T be a spanning tree of a simple cubic graph Q on n vertices. Then, T obeys the following conditions:

(i) \[n_1(T) = n_3(T) + 2\];
(ii) \(n_2(T) = n + 2 - 2n_1(T)\) \((n_2(T) \text{ is even})\).

Proof. Obviously, (i) is true for any tree on n vertices with degrees \(\leq 3\). Indeed, recalling that \(n = n_1 + n_2 + n_3\) and m = n - 1, we have:

\[m = \frac{n_1 + 2n_2 + 3n_3}{2} = \frac{n + n_2 + 2n_3}{2} = n - 1.\]

Hence,

\[n + n_2 + 2n_3 = 2n - 2\].

Thus,

\[n_3 = (2n-2) - n - n_2 - n_3 = n_1 - 2,\]

which is tantamount to (i). Now, transform the R. H. S. of (ii) and obtain:

\[n+2-2n_1=(n-n_1)+2-n_1=n_2+n_3+2-n_1=n_2+(n_1-2)+2-n_1=n_2,\]

where the last but one equality is due to (i), and the last side is equal to the first side, which proves (ii). This completes the proof. \(\Box\)

The following corollary is the dual of Lemma 4.

Corollary 4.1. Let Q - E(T) be the cotree of a spanning T of a simple cubic graph Q on n vertices. Then, the following conditions are obeyed by Q - E(T):

(j) \[n_2[Q - E(T)] = n_0[Q - E(T)] + 2;\]

(jj) \[n_1[(Q - E(T))] = n + 2 - 2n_2[Q - E(T)]\] \((n_1[Q - E(T)] \text{ is even}).\)

A caterpillar, or caterpillar tree, is a tree in which all the vertices are within distance 1 of a central path [5]. Here, we deal with the simple caterpillars having all vertex degrees ≤ 3. Such a caterpillar C2^h is obtained by attaching exactly one pendent vertex to each vertex of a path P^h on h vertices (of length h − 1); thus, C2^h is a tree on 2h vertices. Throughout this text, we use odd numbers h ≥ 3, which is not a restriction for a caterpillar, in general.

Imagine an h-angular prism P2h, whose one h-angular face is consecutively labeled by the numbers 1, 2, . . . , h, while the other such face is similarly numbered by h + 1, h + 2, . . . , 2h; and two vertices g and g + h g ∈ {1, 2, . . . , h} are the ends of a vertical edge. For h > 3, consider a path of length h−1, consecutively spanning h vertices, 2 +h, 2, 3, . . . , h−1, 2h−1. By attaching to this path h pendent vertices, 1 + h, 1, 3 + h, . . . , h, 2h, respectively, we mark a spanning simple caterpillar C2^h in the skeleton of a prism P2h. In the skeleton of the missed triangular prism P⁶ (h = 3), a spanning caterpillar tree C⁶ takes the form of a 'double fork' (term), with a lateral edge of the prism as its middle one. Then, we may represent any prism by its plane graph (map) and make all our construction on the latter. Denote by Q2^h and T2^h a plane graph of P2^h and that of its spanning caterpillar tree C2^h ⊂ P2h, respectively.

Here, we state a technical lemma, viz.:

Lemma 5. Let Q2^h |V (Q2h)| = 2h be the graph of an h-angular prism (h is an odd number ≥ 3) and T2^h be its spanning caterpillar tree. Then, the cotree Q2^h − T2^h is the union of a cycle of length 4 (representing a lateral square face), a simple path of length h − 3, and h − 2 isolated vertices.

Proof. Sketch the proof, which follows from the construction. It is easy to establish that the length of a simple path and the number of isolated vertices are such as stated. What remains uncovered by the path and isolated vertices comprises 2h − (h − 2) − (h − 2) = 4 vertices and 3h − (2h − 1) − (h − 3) = 4 edges. Such quantities of vertices and edges exclude an instance of disconnected subgraph. While a simple subgraph having 4 vertices and 4 edges may be either a triangle with an attached pendent edge or a cycle of length 4. The former is excluded because vertex degrees in the cotree Q2^h − T2^h cannot exceed 2; consequently, such a connected subgraph can only be a cycle. Whence we arrive at the proof.

The following corollary to Lemma 5 may be of use in nanotechnology (cf. [3, 7–9]).

Corollary 5.1. Let Q2^h |V (Q2h)| = 2h be a cubic graph of an h-angular prism, then Q2^h affords a retracting-free bidirectional double tracing if and only if h is an odd number ≥ 3.

Proof. The necessity follows from Corollary 1.2. By virtue of Lemma 5, all components of the cotree Q2^h − E(T2h) satisfy Theorem 1 (and Corollary 1.1), which is a sufficient condition. This gives the proof.

The operation of inserting a new 2-valent vertex into an edge is called a subdivision of an edge. Also, the subdivision (graph) S(G) of a graph G is the graph obtained by subdivision of every edge in G. Two graphs are homeomorphic if both can be obtained from the same graph by a sequence of subdivisions of edges [4]. The following statement is fundamental.

Theorem 6. Let G¹ and G² be two homeomorphic simple graphs. Then, G¹ ∈ Ω iff G² ∈ Ω.

Proof. First, let a graph \(G_1\) belong to \(\Omega\), and let \(\sigma_1\) be a retracting-free bidirectional double tracing in it. Let the tracing \(\sigma_1\) traverse an edge uv first from vertex u to vertex v, then, after traversing some other edges, traverse the same edge uv in an opposite direction, from v to u. Replace the edge uv by an elementary path \(\varpi\) consecutively visiting vertices \(u, w_1, w_2, \ldots, w_p, v\), where all intermediate vertices \(w_j\) (\(j \in \{1, 2, \ldots, p\}\)) are 2-valent in a derived homeomorphic graph \(G_2\). Evidently, \(G_2\) also admits a retracting-free bidirectional double tracing \(\sigma_2\) which, in place of traversing in opposite directions the edge uv, similarly traverses the path \(\varpi\). While the other edges of \(G_2\) are traversed by \(\sigma_2\) in the same order as these are traversed by \(\sigma_1\) in \(G_1\). Conversely, let \(\varpi'\) be an elementary path in \(G_2\), consecutively visiting vertices \(u', w'_1, w'_2, \ldots, w'_{p'}, v'\), where all vertices \(w'_k\) (\(k \in \{1, 2, \ldots, p'\}\)) are 2-valent in \(G_2\). It can similarly be demonstrated that replacing an elementary path \(\varpi'\) in \(G_2\) by a single edge u'v' allows a retracting-free bidirectional double tracing \(\sigma'_1\) in an obtained homeomorphic graph \(G'_1\). This in sum proves that \(G_1 \in \Omega \Leftrightarrow G_2 \in \Omega\).

Now on the contrary, let \(G_1 \not\in \Omega\), and let \(\xi_1\) be an arbitrary bidirectional circuit where an edge uv is consecutively traversed in both directions (from u to v, then, immediately, backwards to u). Substitute for the edge uv an elementary path \(\varpi\) consecutively visiting vertices \(u, w_1, w_2, \ldots, w_p, v\), where all inner vertices are 2-valent in \(G_1\). By this substitution, the circuit \(\xi_1\) is transformed into a circuit \(\xi_2\) of a derivative homeomorphic graph \(G_2\), while preserving in \(G_2\) the same order of traversing all edges that are inherited from \(G_1\). Under such conditions, \(\xi_2\) cannot avoid immediately traversing in an opposite direction one end edge \((uw_1 \text{ or } w_p v)\) of \(\varpi\). Conversely, let \(\varpi'\) be an elementary path in \(G_2\) consecutively visiting vertices \(u', w'_1, w'_2, \ldots, w'_{p'}, v'\), where all inner vertices are 2-valent in \(G_2\). If \(\varpi'\) is consecutively traversed in both directions, substitution of an edge u'v' for \(\varpi'\) also cannot avoid immediately traversing this edge in an opposite direction. Hence, we in sum conclude that \(G_1 \not\in \Omega \Leftrightarrow G_2 \not\in \Omega\). Taking in account both considered cases, when \(G_1, G_2 \in \Omega\) and \(G_1, G_2 \not\in \Omega\), we arrive at the overall proof.

An undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. Note that two homeomorphic graphs \(G_1\) and \(G_2\) always have a common minor H that is their common homeomorph without 2-valent vertices. Within such a broadened context, we come here to another statement, which adds to Theorem 6.

Theorem 7. Let G be a simple graph belonging to \(\Omega\), and let G(u,v) be a graph obtained by identifying two arbitrary vertices u and v of G, without forming a loop from edge uv, if any \((|V[G(u,v)]| = |V(G)| - 1; |E(G)| - 1 \le |E[G(u,v)]| \le |E(G)|)\). Then, \(G(u,v) \in \Omega\).

Proof. Let \(\sigma\) be a retracting-free bidirectional double tracing in G, which consecutively traverses edges \(e_1, e_2, \ldots, e_{2|E(G)|}\) (each of |E(G)| edges is traversed in this sequence twice, in opposite directions). First, let u and v be nonadjacent vertices in G. Then, identifying vertices u and v allows us also to use the same cyclic sequence of edges for a retracting-free bidirectional double tracing \(\sigma'\) in G(u,v), which satisfies our statement. Now let u' and v' be adjacent vertices in G. In this case, deleting an edge u'v' and identifying vertices u' and v', of G, produces another connected cyclic sequence of edges, where edge u'v' is missing. However, missing the edge u'v' of \(\sigma\) does not change the order of traversing the other edges (borrowed from \(\sigma\)) in the last reduced sequence (and the direction of traversing each edge therein). Thus, such a reduced sequence also comprises a retracting-free bidirectional double tracing \(\sigma''\) in G(u',v'), which implies that \(G(u',v') \in \Omega\). The

last fact in combination with that G(u, v) ∈ Ω, for nonadjacent vertices u and v, completes the proof.

The nanobiological field [3, 7–9] needs finding working rules that allow researchers to construct bigger graphs belonging to Ω from smaller ones. The latter graphs may or may not themselves belong to Ω; in particular, they may be Eulerian graphs. Below, we present some rigorous assertions that contribute to this topic.

Let Θ be the class of all Eulerian simple graphs. For convenience, we also introduce a combined class Φ := Θ ∪ Ω which is comprised of all Eulerian and all Ω-graphs. For these classes of graphs, we give here the following three theorems.

Theorem 8. Let G¹ ∈ Φ and G² ∈ Ω be two simple graphs with vertices v¹ and v2, respectively. Also, let G be a graph obtained by connecting vertices v¹ and v² with a simple path $ of length l (l ∈ N+). Then, G ∈ Ω.

Proof. Divide the proof into two parts.

Case 1. Let G¹ ∈ Θ and G² ∈ Ω. We start from vertex v¹ of G¹ and traverse all edges of an arbitrary Eulerian circuit ε 'in a positive direction' to complete this circuit and return to the original vertex v1. Then, we move along the connecting path $ to vertex v² of G² and traverse its edges to exactly complete an arbitrary retracting-free bidirectional double tracing thereof and return to vertex v2. From v2, we move along the connecting path $ in an opposite direction into vertex v¹ from which we traverse all edges of the Eulerian circuit ε, of G1, now in an opposite, 'negative direction' and return to our original point v1. Clearly, our walk used each edge of G exactly once in each direction and without immediately passing through any edge in an opposite direction (only doing this after traversing other edges). This proves Case 1.

Case 2. Let G1, G² ∈ Ω. We can traverse from vertex v¹ all edges of an arbitrary retracting-free bidirectional double tracing of a subgraph G1, then, move along the connecting path $ into point v2, traverse all edges of an arbitrary retracting-free bidirectional double tracing of a subgraph G² and through the path $ return in an opposite direction into our original point vertex v1. This proves Case 2 and completes the overall proof.

Theorem 9. Let G1, G² ∈ Φ be two graphs with vertices v¹ and v2, respectively. Also, let G(v1, v2) be graph obtained by identifying of vertices v¹ and v² of graphs G¹ and G2, respectively. Then, G(v1, v2) ∈ Ω.

Proof. It is similar to the proof of Theorem 8, and we only sketch it. What is new is that there are now three cases: G¹ ∈ Φ, G² ∈ Ω; G1, G² ∈ Ω (both as in Theorem 8); and, additionally, G1, G² ∈ Θ. To prove the first two cases, it is sufficient to repeat the respective steps of the proof to Theorem 8; however, since there is no connected path between subgraphs G¹ and G2, the demonstration is shorter. The third case can be proven by traversing first an arbitrary Eulerian circuit of a subgraph G1, then, a similar circuit of G2; while traversing starts and terminates at vertex v obtained by identification of vertices v¹ and v² of graphs G¹ and G2, respectively. Then, we repeat the procedure, while traversing the same Eulerian cycle in G¹ in an opposite direction and, similarly, the same Eulerian cycle in G² in an opposite direction, to return to vertex v. This completes a retracting-free bidirectional double tracing. Whence the proof follows.

Theorem 10. Let \(G = \bigcup_{j=1}^s G_j\) be a connected vertex union of graphs \(G_1, G_2, \ldots, G_s \in \Phi\) without identifying edges \((|V(G)| \leq \sum_{j=0}^s |V(G_j)| - s + 1; |E(G)| = \sum_{j=1}^s |E(G_j)|)\). Then, \(G \in \Omega\).

Proof. It is due to repetitive application of Theorems 9 and 7. First, construct from all graphs \(G_1, G_2, \ldots, G_s\) an intermediate connected graph G' in which any two subgraphs \(G_j\) and \(G_k\) \((j, k \in \{1, 2, \ldots, s\})\) share either 0 or 1 common vertex. By virtue of Theorem 9, \(G' \in \Omega\). Further, by continuing identification (merging) of pertinent vertices of G', eventually produce a graph G. By Theorem 7, the graph G also belongs to \(\Omega\), which is the proof.

Theorems 7–10 can be used for recursively constructing \(\Omega\)-graphs that can be regarded as models of intricate molecular constructs designed for nanotechnological applications (consult [3, 7–9]).

The next theorem affords a partial solution to the problem posed by Ore.

Theorem 11. Let G be a noncycle Eulerian graph \((|E(G)| - |V(G)| \ge 1)\). Then, \(G \in \Omega\). That is, every Eulerian graph which is not a cycle admits a retracting-free bidirectional double tracing.

Proof. Recall that each noncycle Eulerian graph G is a vertex union (without identifying edges) of proper cycles. It is sufficient to note that the cycles are themselves Eulerian graphs. Hence, by virtue of Theorem 10, we conclude that \(G \in \Omega\), which proves the statement.

The line graph L(H) of a simple graph H is the graph whose vertex set V(L) is in one-to-one correspondence with the set of edges E(H) of the graph H, with two vertices of L(H) being adjacent if and only if the corresponding edges are incident in H.

As a last statement, we consider the following theorem.

Theorem 12. Let L(H) be the line graph of a noncycle simple graph H. Also, let all vertices of H have either only odd degrees > 3 or only even degrees > 2. Then, \(L(H) \in \Omega\).

Proof. Since every vertex in L(H) has an even degree, L(H) is an Eulerian graph. Hence, by Theorem 11, \(L(H) \in \Omega\), which is the proof.

Acknowledgments

The support of the Ministry of Absorption of the State Israel (through fellowship "Shapiro") is acknowledged.

References

• [1] R.B. Eggleton and D.K. Skilton, Double tracing of graphs, Ars Combin. 17A (1984), 307–323.
• [2] G. Fijavž, T. Pisanski, and J. Rus, Strong traces model of self-assembly polypeptide structures, MATCH Commun. Math. Comput. Chem. 71 (2014), 199–212.

• [3] H. Gradisar, S. Bo ˇ ziˇ c, T. Doles, D. Vengust, I. Hafner Bratkovi ˇ c, 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.
• [4] F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
• [5] 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.
• [6] 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.
• [7] V. Kocar, S. Bo ˇ ziˇ c Abram, T. Doles, N. Ba ˇ siˇ c, H. Gradi ´ sar, 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.
• [8] V. Kocar, J.S. Schreck, S. ˇ Ceru, H. Gradi ˇ sar, N. Ba ˇ siˇ c, 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.
• [9] A. Ljubetic, I. Drobnak, H. Gradi ˇ sar, and R. Jerala, Designing the structure and folding path- ˇ way of modular topological bionanostructures, Chem. Commun. 52 (2016), 5220–5229.
• [10] O. Ore, A problem regarding the tracing of graphs, Elem. Math. 6 (1951), 49–53.
• [11] 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.
• [12] 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.
• [13] J. Rus, Parallelism of stable traces, Preprint series, IMFM, ISSN 2232-2094, no. 1197, March 24, 2014 (2014), 1–16.
• [14] C. Thomassen, Bidirectional retracting-free double tracings and upper embeddability of graphs, J. Combin. Theory Ser. B 50 (1990) 198–207.
• [15] D.J. Troy, On traversing graphs, Amer. Math. Monthly 73 (1966), 497–499.