IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 52 (2014), 1197
ISSN 2232-2094
PARALLELISM OF STABLE TRACES
Jernej Rus
Ljubljana, March 24, 2014
PARALLELISM OF STABLE TRACES
Л
Jernej Rus
Faculty of Mathematics and Physics, University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia jernej.rus@gmail.com
IN
m
CD
CD CO
U
a
CD U
September 29, 2013
Abstract
Stable traces were investigated in [Stable traces as a model for self-assembly of polypeptide nanoscale polyhedrons, MATCH Commun. Math. Comput. Chem. 70 (2013) 317-330] as a mathematical model for an innovative biotechnological procedure. Two open problems posed there are discussed in the present paper. It is proved that graphs that admit parallel stable traces are precisely Eulerian graphs with minimum degree at least 4. It is also proved that a sufficient condition for a graph to admit an antiparallel stable trace is to contain an even spanning tree. Here a parallel (antiparallel) stable trace is a double trace with three additional conditions—having no retracing, no repetition, and traversing every edge twice in
00	the same (opposite) direction.
СЧ
Keywords: Eulerian circuit; parallel stable trace; antiparallel stable trace; even spanning tree
AMS Subject Classification (2010): 05C45, 05C05
CO
сч
1 Introduction
Л
О
О Ö
о»
All graphs considered in this paper will be connected, finite, and simple, that is, without loops and multiple edges. If v is a vertex of a graph G, then its degree will be denoted by dc(v) or d(v) for short if G will be clear from the context. The minimum and the maximum degree of G are denoted with 6(G) and A(G), respectively. A directed graph is a graph, where edges have a direction associated with them. In formal terms a directed graph is a pair G = (V, A), where V is a set of vertices and A is a set of ordered pairs of vertices, called arcs. A maximal connected subgraph of G is called a component of G, while a vertex which separates two other vertices of the same component is a cutvertex, and an edge separating its ends is a bridge. A maximal connected subgraph without a cutvertex is called a block. Thus, every block of a graph G is either a maximal 2-connected subgraph, or a bridge (with its ends), or an isolated vertex. For other general terms and concepts from graph theory not recalled here we refer to [8].
A double trace in a graph G is a circuit which traverses every edge exactly twice. We say that a double trace contains a retracing if it has an immediate succession of an edge e by its parallel copy. Further, if v is a vertex of a graph G with a double trace T and u and w are two different neighbors of v, then we say that T contains a repetition through v if the vertex sequence u ^ v ^ w appears twice in T in any direction (u ^ v ^ w or w ^ v ^ u). We next define a proper trace as a double trace that has no retracing and a stable trace as a proper trace without repetitions through its vertices.
In order to present a mathematical model for the biotechnological procedure from [3] the graphs that admit stable traces were characterized in [4] as follows:
Theorem 1.1 [4, Theorem 3.1] A connected graph G admits a stable trace if and only if 6(G) > 3.
CO
Let now T be a double trace of a graph G. Then every edge e = uv of G is traversed exactly twice. If in both cases e is traversed in the same direction (either both times from u to v or both times from v to u) we say that e is a parallel edge (with respect to T). If this is not the case we say that e is an antiparallel edge. A condition that all the edges of G are of the same type is called a parallelism. A double trace T is a parallel double trace if every edge of G is parallel and an antiparallel double trace if every edge of G is antiparallel.
In relation with parallelism of double traces in [4] two related open problems were posed. The first problem, [4, Problem 5.6] asks for a characterization of graphs which admit parallel stable traces. In Section 2 we solve this problem (Theorem 2.2) by proving that a connected graph admits a parallel stable trace if and only if it is Eulerian and its minimum degree is at least 4. The second open problem [4, Problem 5.7] asks for a characterization of graphs which admit antiparallel stable traces. In this direction we prove in Section 3 that a sufficient condition for a graph to admit an antiparallel
• и
m
CD
stable trace is to have an even spanning tree. We wonder whether this condition is also necessary and present some other results about even spanning trees.
2 Graphs that admit parallel stable traces
The following was observed in [4]:
Proposition 2.1 [4, Proposition 5.4] A connected graph G admits a parallel proper-trace if and only if G is Eulerian.
It was also proved in [4] that a graph G admits a parallel double trace if and only if G is Eulerian.
Our main result reads as follows:
О Ö

I
CSI 00 CSI CSI
Theorem 2.2 A graph G admits a parallel stable trace if and only if G is Eulerian and 5(G) > 4.
Proof. Suppose that a graph G admits a parallel stable trace. By definition, every stable trace is a proper trace. Thus by Proposition 2.1, G is Eulerian and hence by Theorem 1.1 we infer that 5(G) > 4.
For the converse assume that G fulfills the conditions of the theorem. We proceed by induction on A = A(G).
Let A = 4. Then 5(G) = A(G) = 4. By Proposition 2.1, G admits a parallel proper trace T'. If T' is not already a stable trace, T' contains a repetition through v, for some vertex v of G. To make the argument more transparent, assume first that T' contains a unique vertex v with a repetition through. If a vertex v with dG(v) = 4 has a repetition through in T', then it is not difficult to see that v has two repetitions through in T'. Let vi, v2, v3, and v4 be the neighbors of v. Without loss of generality, we can assume that A = v1 ^ v ^ v2 is the first and B = v3 ^ v ^ v4 is the second repetition through v in T'. That means that sequences A and B appear twice in T'. Because T' is a parallel proper trace, there are only two possibilities how occurrences of A and B are arranged in T '. These possibilities are AABB (Fig. 1, left) and AB AB (Fig. 2, left). Note that we left out all the other vertices in Figs. 1 and 2.
In the first case construct T from T' in G as follows. Let e' = xy be an arbitrary (oriented) edge of T'. If x,y G V (G) \ {v1, v2, v3, v4}, then we put xy into T. Put one occurrence of v1 ^ v ^ v2 and one occurrence of v3 ^ v ^ v4 in T as well. Replace the remaining occurrences with v1 ^ v ^ v4 and v3 ^ v ^ v2, respectively, such that T stays connected, see Fig. 1, right.
We construct T similarly in the second case, see Fig. 2, right.
We claim that in both cases T is a parallel stable trace of G. Note first that any edge e that appears in T has its unique corresponding edge e' in T'. Any edge e = xy in T, where x = v and y = v, is traversed twice in the same direction in T because it is
сч
л
о и d
in
0 Ö
о
сч
1
сч со сч сч
г
со со
Figure 1: Construction of a stable trace from a proper trace (case AABB)
m
CD
'H
CD CO
a
CD U
Figure 2: Construction of a stable trace from a proper trace (case AB AB)
traversed twice in the same direction in T'. Four remaining edges are traversed twice in the same direction by construction. Hence T is a parallel double trace. It is also clear that T is a proper trace. Vertex v is proper by construction and if any other vertex in T would not be proper, T' would not be proper. (If there would be a retracing of an edge e in T, it would lead to a retracing of its corresponding edge e' in T'.) Finally we
л
о и d
in
0 Ö
о
сч
1
сч со сч сч
г
со со
need to verify that T is stable. Vertex v has no repetition through by construction and if any other vertex u = v in T would have a repetition through, already T' would have a repetition through u = v. We conclude that T is a parallel stable trace of G. We have thus proved that if a 4-regular graph G admits a parallel proper trace T' with a single vertex with repetition through, then G also admits a parallel stable trace.
We now proceed by a second induction on the number Dmax(T') of vertices with a repetition through in T'. Let Dmax(G) > 2 and let v be an arbitrary vertex with a repetition through in T'. Then construct a parallel double trace T from T' by reconstructing T' in v as described above. Note that Dmax(T) < Dmax(T') and hence T can be transformed into a parallel stable trace by the induction on Dmax(T'). Hence any graph G with 6(G) = A(G) = 4 admits a parallel stable trace.
Assume now that A > 6 and that any graph H with A(H) < A which fulfills the conditions of Theorem 2.2 admits a parallel stable trace. To make the argument more transparent, assume first that a graph G, which fulfills the conditions of Theorem 2.2, contains a unique vertex v of degree A. Let vi,...,va be the neighbors of v and consider two cases.
Case 1: A = 2 (mod 4).
Construct the graph G' from G as follows. Remove from G the vertex v, add two new
vertices v' and v'', connect them by an edge, connect v' with vi,..., vд, and connect
2
v'' with the remaining neighbors of v, see Fig. 3.
v' v'
(a) G
(b) G
m
CD
'H
CD
m
и
а
CD U
Figure 3: Construction from the proof of Theorem 2.2 for the case A = 2 (mod 4)
Note that in G' all the vertices but v' and v'' are of the same degree as in G, while dG (v') = f + 1 and dG, (v'') = f + 1. It follows that A(G') < A. Since A > 6, we also infer that 6(G') > 4 (to be more precise we infer that dG/(v'),dG/(v') > 4, while degree of other vertices is unchanged). Because A = 2 (mod 4), the degrees dG/(v') = dG' (v'') = f + 1 are even, hence G is Eulerian and by the induction assumption on A,
v
л
G' admits a parallel stable trace T'.
Construct a parallel stable trace T in G from T' similar as in the base of induction (where A = 4). Put every edge from T' not incident with v' and v'' into T and replace uv', v'u, uv'', and v"u with uv, vu, uv, and vu, respectively. Finally, ignore the two occurrences of the edge v'v'' (or v''v') from T' in T.
To show that T is really a parallel stable trace of G, note first that any edge e that appears in G has its unique corresponding edge e' in G' (edge e' = v'v'' does not appear in G) and is therefore traversed twice in the same direction in T. Also if there would be a retracing of an edge e in T, it would lead to a retracing of its corresponding edge e' in T', which is not possible since T' is parallel stable trace. Hence T is a parallel proper trace. To verify that T is also stable, let e = xy and f = yz be two consecutive edges of T. If e and f are not incident with v, or if x = v or z = v, then e and f does not give a repetition through y because otherwise we would have a repetition through y in T'. Hence the only unchecked option is that y = v. Then x = v^ and z = vj are two neighbors of v. Depend on the origin of obtaining of e and f consider two
CO CO
subcases. In the first subcase let i, j < |"i|]. Then e, f were obtained from the edges
д
v^v', v'v j which do not have a repetition through v' hence e, f do not have a repetition through v. Analogous conclusion holds when i, j > |"i|] (just replace v' with v'' in the argument). In the second subcase let i < < j. Then e, f in T were constructed from vi v', v' v'', v''v j in T '. Since also v'v'' is traversed exactly twice in T ', fact that e and f have a repetition through v would mean that we have a repetition through v' in T', a contradiction. We therefore showed that T is a parallel stable trace of G.
Case 2: A = 0 (mod 4).
СЧ
Construct the graph G' from G as follows. Remove from G the vertex v, and add
three new vertices v', v'', and v'''. Connect v'' with v' and v''' by an edge, connect v'
with vi,..., vд _-,, connect v'' with vд and vд +, and connect v''' with the remaining 2 1 2 2 + 1 neighbors of v, see Fig. 4.
Similarly as in the first case note that in G' all the vertices except v', v'', and v''' are
of the same degree as in G, while de (v') = de (v''') = ^ and de (v'') = 4. It follows
that A(G') < A. Since A > 6, we also infer that ć(G') > 4. Because A = 0 (mod 4),
the degrees de (v') = de (v''') = ^ are even, hence G is Eulerian. By the induction
assumption on A, G' admits a parallel stable trace T'.
We next construct a trace T in G from T'. Let e = xy be an arbitrary (oriented)
edge of T'. If x,y G V (G') \ {v', v'', v'''}, then put xy into T. Let u = v' ,v'',v'''. If
CO e = uv', then replace e with uv in T. Similarly replace edges of the form v'u, uv'', v''u,
uv''', and v'''u with vu, uv, vu, uv, and vu, respectively. Finally, the two occurrences
of the edges v'v'' (or v''v') and v''v''' (or v'''v'') from T' are ignored in T.
We claim that T is a parallel stable trace of G. Note first that any edge e that
appears in G has its unique corresponding edge e' in G'. Clearly, e' = v'v'' and e' =
v''v'''. Since e' is traversed twice in the same direction in T', the edge e is traversed
• и
л
о и d
in
VA Vi
(a) G
(b) G'
0 Ö
o
СЧ
1
СЧ
co
СЧ СЧ
г
co co
co
CD
'H
Jh
CD СО
Figure 4: Construction from the proof of Theorem 2.2 for the case A = 0 (mod 4)
twice in the same direction in T. Hence T is a parallel double trace. It is also clear that T is a proper trace because otherwise T' would not be proper. (If there would be a retracing of an edge e in T, it would lead to a retracing of its corresponding edge e' in T'.) Finally we need to verify that T is stable. Let e = xy and f = yz be two consecutive edges of T. If {x,y,z} П {v} = 0, then e and f does not give a repetition through y because otherwise we would have a repetition through y in T'. The same conclusion holds if x = v or z = v. Assume hence that y = v. Let x = Vj and z = v j and consider two subcases. In the first subcase let i,j < A — 1. Then e and f were obtained from the edges vjv' and v'vj which do not have a repetition through v', hence e and f do not have a repetition through v. Analogous conclusion holds when i, j G {A, A + 1} or i, j > A + 1 (just replace v' with v'' or v''' in the argument). In the second subcase let i < A — 1 and j G {A, A + 1}. Then e and f were constructed from vjv', v'v'', and v''Vj in T'. Recall that v'v'' is traversed exactly twice in T'. Hence if e and f would have a repetition through v, we would have a repetition through v' in T', a contradiction. Analogous conclusion holds when i > A + 1 and j G {A, A + 1} or i < A — 1 and j > A + 1 (just replace v' with v'' or v''' in the argument). We conclude that T is a parallel stable trace of G.
We have thus proved that if G has a single vertex of degree A, then G admits a parallel stable trace.
We now proceed by a second induction on the number Dmax(G) of vertices of maximum degree of a graph G. Let Dmax(G) > 2 and let v be an arbitrary vertex of degree A. Then construct a graph G' from G in the same way as above. Note that Dmax(G') < Dmax(G) and hence G admits a parallel stable trace by the induction on
Dmax(G).	□
U
a
CD U
v
3 Graphs that admit antiparallel stable traces
In this section we present a sufficient condition for graphs to admit antiparallel stable
СЧ
л
о
traces.
Already in 1895 Tarry [6] observed that every graph admits an antiparallel double trace. In [7] Thomassen characterized graphs that admit antiparallel proper traces (thus solving a problem posed by Ore [5]):
Cti
Theorem 3.1 [7, Theorem 3.3] A graph G admits an antiparallel proper trace if and only if 6(G) > 2 and G has a spanning tree T such that each component of G — E (T) either has an even number of edges or contains a vertex v with dG(v) > 4.
Theorem 3.1 was later generalized by Fan and Zhu in [1]. We are interested in antiparallel stable traces. Suppose that a graph G admits an antiparallel stable trace. By definition every stable trace is a proper trace as well. Hence by Theorem 3.1, 6(G) > 2 and G has a spanning tree T such that each component of G — E (T) either has an even number of edges or contains a vertex v, dc(v) > 4. By Theorem 1.1 we also have 6(G) > 3.
To find a sufficient condition for the existence of antiparallel stable traces, we first consider cubic graphs:
Proposition 3.2 A cubic graph G admits an antiparallel stable trace if and only if G has a spanning tree T such that each component of G — E (T ) has an even number of edges.
CSI
Proof. Suppose first that a cubic graph G admits an antiparallel stable trace. By Theorem 3.1, G has a spanning tree T such that each component of G — E (T ) has an even number of edges.
Conversely, let G be an arbitrary cubic graph which has a spanning tree T such that each component of G — E (T) has an even number of edges. Then by Theorem 3.1, G admits an antiparallel proper trace S. Since all the vertices of G are of degree 3 and S is proper, it is straightforward to see that S is also a stable trace.	□
CO CO
We next present a construction of a cubic graph from an arbitrary graph G with 6(G) > 3.
Let G be an arbitrary graph, 6(G) > 3 and A(G) > 3. To make the argument more transparent, assume first that G contains a unique vertex v with d(v) > 3. We construct a cubic of G as follows. Denote d(v) with k. Let vi,..., vk be the neighbors of v in G. Put every vertex of V(G) — {v} into a cubic of G. Replace v in a cubic of G with k — 2 vertices w1,..., wk-2. Put every edge not incident with v in a cubic of G. Connect wi with wi-1 for 2 < i < k — 2. Connect w1 with v1 and v2, and connect wk-2 with vk-1 and vk. Finally connect wi with vi+1 for 2 < i < k — 3. It is not difficult to see that the constructed graph is cubic. If G has more than one vertex of degree
л
о и d
in
greater then 3, use the same procedure on each of them, see Fig. 5. Note that if G is cubic graph, then a cubic of G is isomorphic to G. We also point out that a graph G can have more than one cubic of G.
(a) W6
(b) cubic of W6
0 Ö
о
СЧ
1
СЧ 00 СЧ СЧ
£ CO CO
CO CD
'H
Jh
CD CO
и
a
CD U
Figure 5: Construction of a cubic of W6
Lemma 3.3 Let G be a graph with A(G) < 5 which admits an antiparallel stable trace. Then at least one cubic of G admits an antiparallel stable trace.
Proof. Let G be an arbitrary graph with A(G) < 5 which admits an antiparallel stable trace T. By Theorem 1.1, 6(G) > 3. We proceed by induction on the number k of vertices of degree greater than 3.
Let k = 0. Then G is cubic and by construction, a cubic of G is isomorphic to G. Assume now that k = 1. Denote the unique vertex of degree greater than 3 with v and proceed by the second induction on A = A(G) = dG(v). We have to consider two cases.
Let first d(v) = 4. Denote the neighbors of v with vi, v2, v3, and v4. It is straightforward to see that up to isomorphism, there is only one way how T behaves in v. T contains the next four sequences: v1 — v — v2, v2 — v — v3, v3 — v — v4, and v4 — v — v1. Otherwise T would obviously contain a retracing or a repetition through v. In every cubic of G, v is replaced with two new adjacent vertices v' and v". Connect v' with v1 and v2, and connect v'' with v3 and v4.
We next construct a trace T' in G'
as follows.
r,J
Replace the above mentioned se-v'' — v4, and
v3, v3
quences from T with v1 — v' — v2, v2 -v4 — v'' — v' — v1 in T', respectively. Leave all the other parts of T untouched. Then T' is an antiparallel stable trace in G'.
In the second case d(v) = 5. Denote the neighbors of v with v1, v2, v3, v4, and v5. Similarly as in the first case we observe that T contains next sequences: v1 — v — v2, v2 — v — v3, v3 — v — v4, v4 — v — v5, and v5 — v — v1. In every cubic of G, v is
л
replaced with three new vertices v', v'', and v'''. Connect v'' with v' and v'''. Connect v' with vi and v2, connect v'' with v3, and connect v''' with v4 and v5.
Similarly as in the first case construct a trace T' in G' as follows. Again replace the above five mentioned sequences from T with vi ^ v' ^ v2, v2 ^ v' ^ v'' ^ v3, v3 ^ v'' ^ v''' ^ v4, v4 ^ v''' ^ v5, and v5 ^ v''' ^ v'' ^ v' ^ vi in T', respectively. Leave all the other parts of T untouched. It is not difficult to see that T' is an antiparallel stable trace in G'.
Assume now that k > 1 and that for any graph H with A(H) < 5 which admits an antiparallel stable trace and has less than k vertices of degree greater than 3, at least one cubic of H admits an antiparallel stable trace as well. Let v be an arbitrary vertex of degree greater than 3. Then construct G' in the same way as above. The graph G' then admits an antiparallel stable trace and has less than k vertices of degree greater than 3. By induction assumption, at least one cubic of G' admits an antiparallel stable trace T'. Since every cubic of G' is also a cubic of G, at least one cubic of G admits an antiparallel stable trace.	□
£
Note that the construction of stable traces in cubics of graph from the proof of Lemma 3.3 cannot be generalized to graphs with vertices of degree greater than 5. Indeed, if a graph G which admits an antiparallel stable trace contains a vertex v of degree 6 (denote its neighbors with vi,..., v6), the next problem can occur. Sequences vi ^ v ^ v2, v2 ^ v ^ v3, and v3 ^ v ^ vi can all appear in a stable trace T. At least one repetition through one of the new vertices (through w2 to be more accurate) would then appear, if in the proof described construction is used.
To see that the condition described before Proposition 3.2 is not sufficient in the general case, consider the wheel graph W5. This graph fulfils that condition. On the other hand, computations made by computer program, based on backtracking, showed us that W5 does not admit an antiparallel stable trace. We can also prove
CO
this theoretically. An arbitrary cubic of W5, denote it with W5, has eight vertices and 12 edges. Every spanning tree T' in W5 has seven edges, hence W5 — E(T') has five edges. By Theorem 3.1, W5 does not admit an antiparallel proper trace, hence it does not admit an antiparallel stable trace as well. From Lemma 3.3 it then follows, that W5 does not admit an antiparallel stable trace as well. We have thus proved that the condition before Proposition 3.2 is not sufficient in general.
Let we call spanning trees that fulfills the condition from Proposition 3.2 as even spanning trees. We next prove three lemmas about even spanning trees.
CO
Lemma 3.4 Let G be a graph with 5(G) = 3 and A(G) = 4, which has an even spanning tree. If v is a unique vertex of degree 4, then at least one cubic of G has an even spanning tree.
m
Proof. Let T be an even spanning tree of G. Denote the neighbors of v with vi, v2, v3, and v4, and the edges connecting them to v with ei, e2, e3, and e4, respectively.

i
CSI 00 CSI CSI
л
о
о Ö
We claim that at least one cubic of G has an even spanning tree. In a cubic of G, v is replaced with two adjacent vertices v' and v". Denote the edge connecting them with e. Without loss of generality, v' and v'' can be adjacent to neighbors of v in any order (as long as they are both adjacent to exactly two of them). Depending on an even spanning tree T, we will determine how v', v'', and neighbors of v are connected with each other in a cubic of G.
Construct T' in a cubic of G from T as follows. First put every edge from T in T'. Then also put the new edge e in T'.
We claim that there exists an arrangement of neighbors of v between v' and v'' in a cubic of G, such that T' is spanning tree in a cubic of G. T' is connected because T is connected. Every vertex from G, except v, lies in T' because every vertex from G lies in T. Because e is in T', v' and v'' lie in T'. It is not difficult to see that if adding an edge e in T' would make a cycle C in T', C would already be in T. We conclude that T' is spanning tree in a cubic of G (we still did not arrange neighbors of v to v' and v''). We claim that for at least one cubic of G, denote it with G', T' is an even spanning tree. Next we have to determine, how v', v'' and neighbors of v are adjacent in G', so that T' would be an even spanning tree.
We first notice that G — E(T) and G' — E (T') distinguish only in v. Next we observe that every vertex of G' lies in exactly one component of G' — E(T'). From the construction of T' it is also obvious, that if v lies in component of G — E (T ) without any edge, then v' and v'' lie in two components of G' — E(T') without any edge, hence no matter how we connect the neighbors of v to v' and v'', the tree T' is an even spanning tree.
Assume now that v lies in a component of G — E (T) with even number of edges (> 0). Denote this component with B and consider two cases. In the first case let B and v have exactly one common edge f ; without loss of generality let f = ei (that means that e2, e3 and e4 are edges of T). Connect f and e2 with v' in G', and connect e3 and e4 with v'' in G'. Then v' would lie in an even component of G' — E(T') and v''
CO
would lie in a component of G' — E(T') without any edge, hence T' is an even spanning tree.
In the second case B and v have more than one common edge. That means that we can without loss of generality assume that e1 and e2 are not edges of T. Those common edges lie on some edge-disjoint paths in G' — E(T') — v. We have to consider two subcases. In the first subcase at least two of those paths, say P' and P'', have another common vertex u. We may assume that e1 lies on P' and e2 lies on P''. Connect v' with e1 and e3, and connect v'' with e2 and e4 in G'. Then the component B stays connected in G' — E(T ' ), and v' and v'' lie in a common component of G' — E (T ') with even number of edges, hence T' is an even spanning tree.
CD
In the second subcase, v is the only vertex where the paths on which common edges of B and v intersect in G' — E (T'). If some of these paths are of odd length, there should be an even number of them, because there is an even number of edges in B. If there is no such paths we could arrange v1, v2, v3, and v4 between v' and v'' in any order.
i
CSI 00 CSI
Otherwise, it follows that there are two paths P' and P" of odd length (if there were four, v would not lie in T, because no edge incident with v would be in T). Without loss of generality e1 lies on P' and e2 lies on P''. Connect v' with e1 and e2, and connect v'' with e3 and e4 in G'. Then v' and v'' lie on two even components of G' — E(T'),
hence T' is an even spanning tree. We conclude that G' has an even spanning tree T'. □
Л
О и (Ö
о
CSI
I
Lemma 3.5 Let G be a graph with 5(G) = 3 and A(G) > 4, which has an even spanning tree. If v is a unique vertex of degree greater than 3, then at least one cubic of G has an even spanning tree as well.
&
Proof. Let T be an even spanning tree of G. We proceed by induction on A = A(G) = d(v).
The base of the induction follows by Lemma 3.4.
Assume now that A > 4. Denote the neighbors of v with vi,..., va and construct G' as follows. Remove the vertex v from G, add two new vertices v' and v'', and connect them by an edge e. Connect v' with two neighbors of v, and connect v'' with the remaining ones. Similarly as in the proof of Lemma 3.4, v' and v'' can be adjacent to neighbors of v in any order (as long as v' is adjacent to exactly two of them and v'' is adjacent to all of the remaining ones). Depending on an even spanning tree T, we will again determine how the neighbors of v are connected to v' and v'' in G'.
We claim that G' is a graph with 5(G') = 3, A(G') < A and a unique vertex v'' of degree greater than 3, which has an even spanning tree T. It is not difficult to see that
СЧ
G' fulfills the first three conditions. Similarly as in the proof of Lemma 3.4, we next СЧ prove that G' has an even spanning tree. The only difference between the arguments is in the last subcase, because here can be more than two paths of odd length in B adjacent to v. However, their number is still even, so we connect two of them to v' and all the others (also paths of even length) to v''.
We conclude that G' has an even spanning tree T'. By induction assumption, at least one cubic of G' has an even spanning tree T''. Since every cubic of G' is also a cubic of G, at least one cubic of G has an even spanning tree.	□
Lemma 3.6 If a graph G with 5(G) > 3 has an even spanning tree, then at least one cubic of G has an even spanning tree.
CO
Proof. Let T be an even spanning tree of G. We proceed by induction on the number k of vertices of degree greater than 3.
Let k = 0. Then G is cubic and a cubic of G is isomorphic to G. Let next k = 1. By Lemma 3.5 at least one cubic of G has an even spanning tree.
Assume now that k > 1. Analogously as in case k = 1, we replace one of high degree vertices and construct a graph G' with k — 1 vertices of degree greater than 3
and an even spanning tree T'. By induction assumption, also cubic of G' has such a spanning tree. Since every cubic of G' is also a cubic of G, at least one cubic of G has an even spanning tree.	□
Using Lemmas 3.4, 3.5, and 3.6, we get:
Л
О
и
an antiparallel stable trace
Theorem 3.7 If a graph G has an even spanning tree T and 6(G) > 3, then G admits
Proof. If G is a cubic graph, then Proposition 3.2 claims that G admits an antiparallel stable trace. Assume now that A(G) > 4. By Lemma 3.6 at least one cubic of G, denote it with G', has an even spanning tree T'. Moreover, because G' is cubic, by Proposition 3.2, G' admits an antiparallel stable trace S'. We next construct a stable trace S in G as in the first case of the proof of Theorem 2.2 (by ignoring occurrences of edges newly created in a cubic of G). It is straightforward to see that S is an antiparallel stable trace.	□
Ö
To conclude the section we pose:
Problem 3.8 Is it true that a graph G admits an antiparallel stable trace if and only if 6(G) > 3 and G has an even spanning tree T ?
О
CSI
I
4 Concluding remarks
CSI CSI
In this section we present two concepts for constructing parallel stable traces. Unfortunately, when proving Theorem 2.2, we found examples of graphs, where either the first or the second concept cannot be applied. So both concepts presented here cannot be used in general.
The first idea how to construct parallel stable traces goes as follows. Let G be an Eulerian graph with n vertices (denoted with v\,...,vn) fulfilling conditions of Theorem 2.2 and let T be an Eulerian circuit of G. T induces a set of functions П = [n\,... ,nn}, where ni : V (G) \ {vi} —> V (G) \ {v^}, n^(v) = u if and only if v ^ vi ^ u is a sequence in T, for 1 < i < n. Note that u = v, because G is simple and T traverses every edge exactly once. Construct another Eulerian circuit T' in G such that it will induce a set of functions П' = {n',... ,n'n} with above described characteristics. In addition demand, that edges are traversed in the same direction as in T, and that if ni (v) = u then ni (v) = u and ni (u) = v. Let f = xy be the last
U
traversed edge in T. Concatenate Eulerian circuits T and T' in y to get a trace S. By construction it is obvious that in S every edge is traversed twice in the same direction and that S is without any retracing and repetition. Hence, if a graph G admits two Eulerian circuits with above described characteristic, G admits parallel stable trace as well.
л
о и d
in
0 Ö
о
сч
1
сч со сч сч
г
со со
со
CD
'Н
CD СО
а
CD Jh Оч
It turns out that, we cannot always construct a parallel stable trace of G by concatenating T and T'. For instance, the graph G from Fig. 6 has a parallel stable trace: vi ^ v2 ^ v3 ^ vi ^ v2 ^ v4 ^ v\ ^ v5 ^ v2 ^ v3 ^ v4 ^ v6 ^ v5 ^ v2 ^ v4 ^ v6 ^ v7 ^ v9 ^ vs ^ v6 ^ v7 ^ vio ^ vs ^ vil ^ v7 ^ v9 ^ vio ^ vil ^ v7 ^ vio ^ vil ^ v9 ^ vs ^ vil ^ v9 ^ vio ^ v8 ^ v6 ^ v5 ^ v3 ^ vi ^ v5 ^ v3 ^ v4 ^ vi, but because of the cut vertex v6, from any Eulerian circuit T of G we cannot construct another Eulerian circuit using the described construction.
Figure 6: Graph whose parallel stable trace cannot be constructed by concatenating two Eulerian circuits
Realizing that cut vertices cause problems, we could try to use another approach. Let G be an Eulerian graph fulfilling the conditions of Theorem 2.2. Denote blocks of G with Bi,...,Bk and cutvertices with vi,..., vk-i, where for cutvertex v which separates Bi and Bj the following is true: v G Bi П Bj. Let Ti,... Tk be parallel stable traces in Bi,..., Bk respectively. Note again that cutvertex v which separates Bi and Bj appears in both Ti and Tj. Let first k = 1. Then Ti is also a parallel stable trace of G. Assume now that k = 2 and let v be the unique cutvertex of G. Construct a double trace T in G as follows. Start in an arbitrary vertex of Bi and continue on Ti until coming to v. Traverse then every edge of T2 until finishing in v. Traverse now the rest of the edges in Ti. Since every edge e of G is traversed twice in the same direction in Ti or in T2, the edge e is traversed twice in the same direction in T. Hence T is a parallel stable trace. Let next e = xy and f = yz be two consecutive edges of T. If {x, y, z} n {v} = 0, then e and f does not give a repetition through y (retracing) because otherwise we would have a repetition through y (retracing) in Ti or T2. The same conclusion holds if x = v or z = v. Assume hence that y = v. Then e and f does not give a repetition through v (retracing) by construction. We have thus find an algorithm for construction of parallel stable traces in graphs with at most 2 blocks, with assumption that we can found a parallel stable trace in every block of graph.
We proceed by induction on the number k of blocks of graph G. Let k > 2 and
л
о и d
in
0 Ö
о
сч
1
сч со сч сч
г
со со
assume that for any graph H with strictly less than k blocks we can construct a parallel stable trace with above described construction (if we can found a parallel stable trace in every block of graph). Let v be an arbitrary cutvertex. Without loss of generality we can assume that v G B1 П B2. Then construct a parallel stable trace T1 in B1 U B2 from Ti and T2 the same way as above. Because |{Т',Тз,... ,Tk}| < k, by induction above described algorithm will find a parallel stable trace in G.
Again we cannot always construct a parallel stable trace of G using this construction. The problem lies in an assumption that we cab found a parallel stable trace in every block of graph G. As we have seen before, graph G from Fig. 6 admits a parallel stable trace. Vertex v6 is its unique cutvertex. Because in both blocks of G vertex v6 is of degree 2, by Theorem 2.2 blocks of G do not admit parallel stable traces. Similar problem occurs if one or more blocks of G are bridges.
If we instead of parallel stable traces in blocks demand parallel proper traces where repetitions occur only at cutvertices (retracings if block is bridge), we can still get parallel stable trace of G when concatenating those smaller parallel proper traces together. But even this modification is not enough to produce an algorithm which would work in general. By Theorem 2.2 the graph H from Fig. 7 has a parallel stable trace. However, two of its block have vertices of degree 3 (v1, v2, v3, and v4) and therefore by Proposition 2.1 do not admit neither parallel proper trace nor parallel stable trace.
Figure 7: Graph whose parallel stable trace cannot be constructed by concatenating parallel stable traces in blocks of a graph
CO CD
'H
CD
m
Acknowledgements
The author is grateful to Sandi Klavžar for several significant remarks which were of great help.
U
a
CD U
сч
References
[1]	H. Fan, X. Zhu, Oriented walk double covering and bidirectional double tracing, J. Graph Theory, 29 (1998) 89-102.
[2]	H. Fleischner, Eulerian Graphs and Related Topics. Part 1. Vol. 2., North-Holland, О Amsterdam, 1991.
[3]	H. Gradisar, S. Božic, T. Doles, D. Vengust, I. Hafner Bratkovic, A. Mertelj, B. Webb, A. Šali, S. Klavžar, R. Jerala, Design of a single-chain polypeptide tetrahedron assembled from coiled-coil segments, Nature Chemical Biology 9 (2013) 362-366.
[4]	S. Klavžar, J. Rus, Stable traces as a model for self-assembly of polypeptide nanoscale polyhedrons, MATCH Commun. Math. Comput. Chem. 70 (2013) 317330.
О
[5]	O. Ore, A problem regarding the tracing of graphs, Elemente der Math. 6 (1951) 49-53.
[6]	G. Tarry, Le probleme des labyrinthes, Nouv. Ann. (3) XIV (1895) 187-190.
о
[7]	C. Thomassen, Bidirectional retracting-free double tracings and upper embed-dability of graphs, J. Combin. Theory Ser. B 50 (1990) 198-207.
СЧ
[8]	D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 1996.
CO CD
'H
CD
m
и
a