ISSN 2590-9770
The Art of Discrete and Applied Mathematics 2 (2019) #P1.07
https://doi.org/10.26493/2590-9770.1251.b76
(Also available at http://adam-journal.eu)
Parallelism of stable traces
Jernej Rus ∗
Abelium d.o.o., Kajuhova 90, 1000 Ljubljana, Slovenia
Received 18 May 2018, accepted 19 September 2018, published online 8 August 2019
Abstract
A parallel d-stable trace is a closed walk which traverses every edge of a graph exactly
twice in the same direction and for every vertex v, there is no subset X ⊆ N(v) with
1 ≤ |N | ≤ d such that every time the walk enters v from X , it also exits to a vertex in
X . In the past, d-stable traces were investigated as a mathematical model for an innovative
biotechnological procedure – self-assembling of polypeptide structures. Among other, it
was proven that graphs that admit parallel d-stable traces are precisely Eulerian graphs
with minimum degree strictly larger than d. In the present paper we give an alternative,
purely combinatorial proof of this result.
Keywords: Eulerian graph, parallel d-stable trace, nanostructure design, self-assembling, polypep-
tide.
Math. Subj. Class.: 05C45, 05C85, 94C15
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
dG(v) or d(v) for short ifG will be clear from the context. The minimum and the maximum
degree of G are denoted with δ(G) and ∆(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
∗The author is grateful to Sandi Klavžar and anonymous reviewers for several significant remarks and sug-
gestions which were of great help. The authors acknowledge the financial support from the Slovenian Research
Agency H2020 SME2 and the SPIRIT Slovenia - Public Agency for Entrepreneurship, Internationalization, Fore-
ign Investments and Technology - KKIPP.
E-mail address: jernej.rus@gmail.com (Jernej Rus)
cb This work is licensed under http://creativecommons.org/licenses/by/3.0/
2 Art Discrete Appl. Math. 2 (2019) #P1.07
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. A subtree T of a graph G is a subgraph of
G that is also a tree (any pair of vertices u, v ∈ V (T ) ⊆ V (G) are connected by exactly
one path in T ). For other general terms and concepts from graph theory not recalled here
we refer to [12].
A circuit is a closed walk allowing repetitions of vertices and edges. An Eulerian circuit
in G is a circuit which traverses every edge of G exactly once. G is called Eulerian if it
admits an Eulerian circuit. A double trace in a graph G is a circuit that traverses every
edge exactly twice. For a set of vertices X ⊆ N(v), we say that a double trace W has
an X-repetition at vertex v (nontrivial X-repetition in [3]), if X is nonempty, X 6= N(v),
and whenever W comes to v from a vertex in X it also continues to a vertex in X . An
X-repetition (at v) is a d-repetition if |X| = d (repetition of order d), see Figure 1. Clearly
if W has an X-repetition at v, then it also has an (N(v) \X)-repetition at v (symmetry of
repetitions). We call a double trace without any repetition of order ≤ d a d-stable trace.
Note, that for every d′ ≤ d, a d-stable trace is also a d′-stable trace.
u
e
(a)
v
(b)
v
(c)
w
(d)
Figure 1: Possible 1-, 2- and 3-repetitions at vertices w, u and w, respectively.
In order to present a mathematical model for the biotechnological procedure from [6]
graphs that admit d-stable traces were characterized in [3] (thus generalizing results of
Sabidussi [11] and Eggleton and Skilton [2] about 1-stable traces and Klavžar and Rus [8]
about 2-stable traces) as follows:
Proposition 1.1 ([3, Proposition 3.4]). A connected graph G admits a d-stable trace if and
only if δ(G) > d.
Let now W 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 W ). If
this is not the case we say that e is an antiparallel edge. The condition that all the edges
of G are of the same type is called a parallelism. A double trace W is a parallel double
trace if every edge of G is parallel and an antiparallel double trace if every edge of G is
antiparallel.
By replacing every edge of a graph with two new edges we can quickly prove that
every graph (resp. every Eulerian graph) admits an antiparallel (resp. parallel) double trace,
observation made by several authors, Klavžar and Rus in [8] among others. While graphs
admitting antiparallel d-stable traces were thoroughly studied in [10], the characterization
of parallel d-stable traces was only mentioned as a consequence in [3]:
Theorem 1.2 ([3, Theorem 5.4]). A graph G admits a parallel d-stable trace if and only if
G is Eulerian and δ(G) > d.
J. Rus: Parallelism of stable traces 3
In the present paper we will give an alternative proof of this result. Instead of graph
embeddings (heavily used in [3]), our approach to the problem will be purely combinato-
rial. Characterizing graphs that admit parallel d-stable traces also represents a new problem
related with forbidden transitions in Eulerian tours of Eulerian graphs (further related prob-
lems can be found, among others in [4, 5]).
We can note right away that parallel double traces do not contain 1-repetitions. Note
also that none of the operations that we will use on double traces (concatenations, contrac-
tions, deletions, inductive constructions, and reordering) will change the orientation of the
edges.
1.1 Biotechological background
In 2013 Gradišar et al. [6] presented a novel self-assembly strategy for polypeptide nanos-
tructure design. Their strategy relied on routing a single polypeptide chain consisting of 12
segments through 6 edges of the tetrahedron in such a way that every edge was traversed
exactly twice. The required mathematical support for the particular case of the tetrahedron
and the general case of a polyhedron was already given in [3, 6, 8], where the authors ex-
plained that polyhedron P that is composed from a single polymer chain can be naturally
represented by a graph G(P ) of the polyhedron. Circuits that traverse every edge of G(P )
precisely twice, called double traces of G(P ), play a key role in modeling the construction
process.
The stability of the constructed polyhedra depends on an additional property whether
in the double trace the neighborhoods of vertices can be split. The reader interested in the
biotehological procedures that motivated our research may also consult the references [7,
9], where the authors also exposed the use of parallel d-stable traces.
2 Graphs admitting parallel 2-stable traces
The first mathematical model for the biotechnological procedure from [6], introduced in [8],
stated that a polyhedral graph P can be realized by interlocking pairs of polypeptide chains
if its corresponding graph G(P ) contains a 2-stable trace. Two important deficiencies of
this model were later found in [3]:
(i) it does not account for vertices of degree ≤ 2, and
(ii) it does not successfully model vertices of degree ≥ 6 (because a polyhedron could
split into two parts in a vertex of degree≥ 6, as can be seen at Figure 1 and therefore
the structure would not be stable).
Since until now, a construction of a polyhedron whose graph would have such properties,
has not yet been attempted, we first study parallel 2-stable traces in this section.
To make the arguments in this section more transparent, we explain how the reader can
graphically imagine 1-repetitions and 2-repetitions in double traces. We say that a double
trace contains a 1-repetition if it has an immediate succession of an edge e by its antiparallel
copy. If v is a vertex of a graph G with a double trace W and u and w are two different
neighbors of v, then we can say that W contains a 2-repetition (through) v if the vertex
sequence u→ v → w appears twice in W in any direction (u→ v → w or w → v → u),
see Figure 1.
We will need the next lemma in the proof of Theorem 2.3.
4 Art Discrete Appl. Math. 2 (2019) #P1.07
Lemma 2.1. Let G be a graph and let T a subtree of G such that every vertex v ∈ V (G) \
V (T ) has at most one neighbor in T . Construct a graph G′ from G by contracting T into
a single vertex t. If G admits a 2-stable trace W then G′ admits a 2-stable trace W ′ that
traverses edges from E(G) ∩ E(G′) in the same direction as W .
Proof. Suppose that the graph G admits a 2-stable trace W . Construct a double trace
W ′ from W as follows. Start in an arbitrary vertex of V (G) \ V (T ) and follow W . Let
a = xy be an arc of W that we are currently traversing on our walk along W . If x, y ∈
V (G) \ V (T ), then we put xy into W ′ so that the order of arcs from W is preserved. If
x ∈ V (T ) and y /∈ V (T ) then we put ty in W ′ instead of a. Similarly, we replace arcs
where x /∈ V (T ) and y ∈ V (T ) with xt. Finally, the occurrences of the arcs from T are
ignored in W ′.
We claim that W ′ is a 2-stable trace of G′. Since every edge is traversed twice in W ,
every edge is traversed twice in W ′. Hence W ′ is a double trace. If W ′ is not a 2-stable
trace, there exists a vertex x ∈ V (G′) such that W ′ has a 1-repetition or a 2-repetition at
x. Denote the neighborhood of vertex t in G′ with N(t). We have to consider three cases.
Case 1: x /∈ N(t).
It is clear from the construction that if W ′ had a 1-repetition or a 2-repetition at x, then
W would have a 1-repetition or a 2-repetition at x, a contradiction.
Case 2: x ∈ N(t).
It is again clear from the construction that ifW ′ had a 1-repetition yxy or a 2-repetition
yxz, where y, z 6= t, then W would have a 1-repetition or a 2-repetition at x, a contradic-
tion.
Assume first that W ′ has a 1-repetition txt. It follows that W should contain hxg,
where h, g ∈ T . Since every vertex in V (G) \V (T ) has at most one neighbor in T , h = g.
Therefore W should contain a 1-repetition hxh, a contradiction.
Assume next that W ′ has a 2-repetition txy for some neighbor y of x. It follows that
W should contain hxy and gxy, where h, g ∈ T . Since every vertex in V (G) \ V (T )
has at most one neighbor in T , h = g. Therefore W should contain a 2-repetition hxy, a
contradiction.
Case 3: x = t.
Assume first that W ′ has a 1-repetition yty for some neighbor y of t. It follows that W
should contain yhAhy, where h is the unique neighbor of y in T and A is a circuit in T .
Since T is a tree, the only possibility that circuit appears in a part of a double trace W that
is completely included in T is with a 1-repetition, a contradiction.
Assume next that W ′ has a 2-repetition ytz for some neighbors y and z of t. It follows
that W should contain yhBgz and yhCgz, where h is a unique neighbor of y in T , g is
a unique neighbor of z in T , while B and C are hg-paths in T . Considering the fact that
in a tree any two vertices are connected with a unique path, we can argue that B = C and
therefore that then W should have a 2-repetition (1-repetition if h = g), a contradiction.
We have thus proved that W ′ is a 2-stable trace in G′. During the construction of W ′
we did not change the direction of any arc from W .
Note that Lemma 2.1 is, by repetition of the procedure described above, also true for
forests (any number of disjoint subtrees).
J. Rus: Parallelism of stable traces 5
The following was proven in [8], where it was also observed that a graph G admits a
parallel double trace if and only if G is Eulerian.
Proposition 2.2 ([8, Proposition 5.4]). A connected graph G admits a parallel 1-stable
trace if and only if G is Eulerian.
Proof. Parallelism of any stable trace of a graph G implies that all the vertices of G are of
even degree and traversing an arbitrary Eulerian circuit of G twice in the same direction
constructs a parallel 1-stable trace.
We next prove Theorem 2.3 about parallel 2-stable traces and then use it in Section 3 to
present an alternative proof of Theorem 1.2.
Theorem 2.3. A graph G admits a parallel 2-stable trace if and only if G is Eulerian and
δ(G) > 2.
Note that for Eulerian graphs the constraint on the minimal degree of a graph from
Theorem 2.3 is equivalent to δ(G) ≥ 4.
Proof. Suppose that a graph G admits a parallel 2-stable trace. By definition, every 2-
stable trace is a 1-stable trace. Thus by Proposition 2.2, G is Eulerian and hence by Propo-
sition 1.1 we infer that δ(G) ≥ 4.
For the converse assume that G fulfills the conditions of the theorem. We proceed by
induction on ∆ = ∆(G).
Let ∆ = 4. Then δ(G) = ∆(G) = 4. By Proposition 2.2, G admits a parallel 1-stable
trace W ′. If W ′ is not already a 2-stable trace, W ′ contains at least one 2-repetition. We
proceed with the second induction on the number k of vertices where W ′ has 2-repetitions.
Let k ≥ 1 and let v be one of the vertices where W ′ has a 2-repetition. If a 1-stable trace
W ′ has a 2-repetition through v, where v is a vertex with dG(v) = 4, then it is not difficult
to see that W ′ has two 2-repetitions through v. Let v1, 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 2-repetition through v in W ′. That means that
sequences A and B appear twice in W ′. Because W ′ is a parallel 1-stable trace, there are
only two possibilities how occurrences of A and B are arranged in W ′. These possibilities
are AABB (Figure 2, left) and ABAB (Figure 3, left). Note that we left out all the other
vertices in Figures 2 and 3.
In the first case we construct a double trace W from W ′ in G as follows. We start
in an arbitrary vertex of V (G) \ {v} and follow W ′. Let a = xy be an arc of W ′ that
we are currently traversing on our walk along W ′. If x, y ∈ V (G) \ {v, v1, v2, v3, v4},
then we put xy into W so that the order of arcs from W ′ is preserved. Put one occurrence
of v1 → v → v2 and one occurrence of v3 → v → v4 in W as well. Replace the
remaining occurrence of v1 → v → v2 with v1 → v → v4 and the remaining occurrence
of v3 → v → v4 with v3 → v → v2, so that W stays connected, see Figure 2, right.
We construct W analogously in the second case, see Figure 3, right.
We claim that in both cases W is a parallel 1-stable trace of G with at least one vertex
with 2-repetition less than W ′. Note first that any edge e = xy that appears in W (arcs
xy or yx appears in W ) has its unique corresponding edge e′ in W ′. Any edge e = xy in
W , where x 6= v and y 6= v, is traversed twice in the same direction in W because it is
traversed twice in the same direction inW ′. Four remaining edges (vv1, vv2, vv3, and vv4)
6 Art Discrete Appl. Math. 2 (2019) #P1.07
vv4
v2
v3
v1
=⇒ v
v4
v2
v3
v1
Figure 2: Removing 2-repetition through v (case AABB).
vv4 v2
v3
v1
=⇒ v
v4 v2
v3
v1
Figure 3: Removing 2-repetition through v (case ABAB).
J. Rus: Parallelism of stable traces 7
are traversed twice in the same direction by construction. Hence W is a parallel double
trace. It is also clear from the construction that W is a 1-stable trace. Finally we need to
verify that W has at least one vertex with 2-repetition less than W ′. Let x be an arbitrary
vertex of G in which W has a 2-repetition. We have to consider three cases.
Case 1: x /∈ {v, v1, v2, v3, v4}.
It is clear from the construction that if W has a 2-repetition through x, then also W ′
has a 2-repetition through x.
Case 2: x ∈ {v1, v2, v3, v4}.
It is again clear from the construction that if W has a 2-repetition yxz, where y, z 6= v,
then also W ′ has a 2-repetition through x.
Similarly, if W has a 2-repetition vxy for some neighbor y of x, then also W ′ has a
2-repetition through x since the order of arcs adjacent to {v1, v2, v3, v4} did not change
in W .
Case 3: x = v.
The 1-stable traceW ′ had a 2-repetition (two 2-repetitions to be more accurate) through
v but during the construction of W we manage to remove them both.
We have thus constructed a 1-stable trace W which have at least one vertex with 2-
repetition less thanW ′. Hence, it follows by induction assumption that any 4-regular graph
admits a parallel 2-stable trace.
Assume now that ∆ ≥ 6 and that any graph H with ∆(H) < ∆ that fulfills the
conditions of Theorem 2.3 admits a parallel 2-stable trace. We have to again consider two
cases.
Case 1: ∆ ≡ 2 (mod 4).
Construct the graph G′ from G as follows. For every vertex v of degree ∆ (temporary
denote its neighbors with v1, . . . , v∆) repeat the following procedure. Remove v from G.
Add two new vertices v′ and v′′, connect them by an edge, connect v′ with v1, . . . , v∆
2
, and
connect v′′ with the remaining neighbors of v, see Figure 4.
v
v1
. . .
v∆
(a) G
v′ v′′
v1
. . .
v∆
2
v∆
2 +1
. . .
v∆
(b) G′
Figure 4: Construction from the proof of Theorem 2.3 for the case ∆ ≡ 2 (mod 4).
Note that in G′ all except the newly added vertices are of the same degree as in G,
8 Art Discrete Appl. Math. 2 (2019) #P1.07
while dG′(v′) = ∆2 + 1 and dG′(v
′′) = ∆2 + 1 (the last two statements are true for all new
vertices). It follows that ∆(G′) < ∆. Since ∆ ≥ 6, we then also infer that δ(G′) ≥ 4.
Because ∆ ≡ 2 (mod 4), the degrees dG′(v′) = dG′(v′′) = ∆2 + 1 are even, hence G
is Eulerian and by the induction assumption on ∆, the graph G′ admits a parallel 2-stable
trace. If we use a path containing vertices v′ and v′′ as subtree T , it follows from a repeated
application of Lemma 2.1 that G admits a parallel 2-stable trace.
Case 2: ∆ ≡ 0 (mod 4).
Construct the graph G′ from G as follows. For every vertex v of degree ∆ (temporary
denote its neighbors with v1, . . . , v∆) repeat the following procedure. Remove v from G,
and add three new vertices v′, v′′, and v′′′. Connect v′′ with v′ and v′′′ by an edge, connect
v′ with v1, . . . , v∆
2 −1
, connect v′′ with v∆
2
and v∆
2 +1
, and connect v′′′ with the remaining
neighbors of v, see Figure 5.
v
v1
. . .
v∆
(a) G
v′
v′′
v′′′
v1
. . .
v∆
2 −1
v∆
2 +2
v∆
2
v∆
2 +1
. . .
v∆
(b) G′
Figure 5: Construction from the proof of Theorem 2.3 for the case ∆ ≡ 0 (mod 4).
Analogously as in the first case, note that in G′ all except the newly added vertices are
of the same degree as in G, while dG′(v′) = dG′(v′′′) = ∆2 and dG′(v
′′) = 4 (the last two
statements are true for all new vertices). It follows that ∆(G′) < ∆. Since ∆ ≥ 6, we then
also infer that δ(G′) ≥ 4. Because ∆ ≡ 0 (mod 4), the degrees dG′(v′) = dG′(v′′′) = ∆2
are even, hence G is Eulerian. By the induction assumption on ∆, the graph G′ admits a
parallel 2-stable trace. Similarly as in previous case, if we use a path containing vertices
v′, v′′ and v′′ as subtree T , it follows from repeated application Lemma 2.1 that G admits
a parallel 2-stable trace.
We have thus proved Theorem 2.3.
3 Alternative proof of Theorem 1.2
We now extend the results from previous section to present an alternative proof of Theo-
rem 1.2 (Theorem 5.4 from [3]).
Proof. Assume first that the graph G admits a parallel d-stable trace. From Proposition 1.1
it follows that δ(G) > d for every graph G that admits a d-stable trace. Assume that there
J. Rus: Parallelism of stable traces 9
exists an vertex v of odd degree in G. Since every edge of a parallel double trace is used
twice in the same direction, input and output degree of a parallel double traceW would not
match at v, which is absurd. Therefore it follows that G is Eulerian and δ(G) > d.
For the converse assume that graph G is Eulerian and δ(G) > d. Since G is Eulerian,
δ(G) is an even number. Furthermore, since for parallel 1-stable traces and 2-stable traces
the theorem follows from Proposition 2.2 and Theorem 2.3, respectively, we can assume
that d ≥ 3. Let G′ be a graph obtained from G by replacing every vertex v of degree
dG(v) > 4 with (dG(v) − 2)/2 new vertices, connected into a path Pv and additionally
connecting two endvertices of Pv with three different neighbors of v and each inner vertex
of Pv with two different remaining neighbors, so that each of the vertices from N(v) is
connected to exactly one vertex in Pv . It is not difficult to see that G′ is a 4-regular graph
and therefore by Theorem 2.3 admits a parallel 2-stable trace W ′. Construct a parallel
double trace W in G from W ′ as follows. We start in an arbitrary vertex of G′ and follow
W ′. Let a′ = xy be an arc of W ′ that we are currently traversing on our walk along W ′.
If for every v, dG(v) > 4, x, y /∈ V (Pv), then we put xy into W so that the order of arcs
from W ′ is preserved. If for some v, dG(v) > 4, x ∈ Pv or y ∈ Pv , we replace a′ with
vy or xv, respectively. Finally, occurrences of the arcs with both endvertices contained in
some Pv are ignored in W .
We claim that the parallel double trace W is a parallel d-stable trace of the graph G.
We assume conversely and denote an arbitrary vertex in which W has a repetition of order
≤ d with v. Denote the maximal order of (≤ d)-repetition at v with d′. Since we used
the same construction as in the proof of Theorem 2.3, it follows that W is a parallel 2-
stable trace (and d′ > 2). From the symmetry of repetitions it then also follows that
dG(v) > d
′+2, since otherwise W would have at least one 1-repetition or one 2-repetition
at v (therefore also dG(v) ≥ 8). It is then also not difficult to see that every repetition in a
parallel double trace is of even order. Let X be a subset of N(v) containing vertices from
a maximal repetition at v (note that |X| = d′). There exists a path Pv in G′ that during
the construction replaced v from G. To make the argument more transparent, we imagine
vertices from Pv arranged in a horizontal line with all the neighbors of v except for two,
lying directly above or below vertices of Pv . The remaining two neighbors of vertex v are
aligned at the beginning and at the end of the horizontal line containing vertices from Pv .
Figure 6(b) shows Pv with vertices from N(v) in G′ for dG(v) = 8 (v′, v′′, and v′′′ are the
vertices replacing v in G′). Next, we color vertices from N(v) with two colors—black and
white, so that vertices from X are colored black while vertices from N(v) \X are colored
white. Example of such a coloring can be seen at Figure 6.
Since the subsetN(v)\X is also a repetition, the arguments used hereinafter are true for
black and white vertices and we can, without loss of generality, assume that the neighbor of
N(v), lying farmost to the left in the above mentioned horizontal line is colored white. We
next move along this horizontal line and denote the first black vertex that we meet (below
or above the line) with b. Denote its neighbor in Pv with v′. Since there are at least four
black vertices, v′ is not the farmost right vertex from Pv . Therefore, we can also denote
the right neighbor of v′ from Pv with v′′ and consider two cases. In the first case b is the
only neighbor of v′ (/∈ Pv) colored black (Figure 7(a)), while in the second case also the
second neighbor of v′ (/∈ Pv) is colored black (Figure 7(b)). In both cases we can, without
loss of generality, assume that an edge bv′ is traversed twice in the direction toward v′ in
W ′ (that is, arc bv′ is traversed twice in W , while arc v′b does not appear in W ′). The
fact that W has an X-repetition implies that every time double trace W comes to v from a
10 Art Discrete Appl. Math. 2 (2019) #P1.07
v
(a) v and N(v) in G
v′ v′′ v′′′
(b) Pv and N(v) in G′
Figure 6: Structures of N(v) in G and Pv in G′. Vertices contained in X are colored black.
v′
b
v′′
(a) b is the only black neighbor of v′
w1
w3
w2
v′
b′
b
v′′
(b) Both neighbors of v′ from N(v) are black
Figure 7: Two cases of the structure of Pv (of v′ and b to be more precise). Vertices for
which the color is not determined are colored grey.
J. Rus: Parallelism of stable traces 11
vertex in X it also continues to a vertex in X and, consequently, that every time a double
trace W ′ comes to a vertex in Pv from a (black colored) vertex in X it also leaves to a
(black colored) vertex in X . Note that in between W ′ can traverse other vertices from Pv
and that this applies for all appearances of verb continue from now on until the end of this
section. Analogously is true for (white colored) vertices from N(v) \X . Therefore, in W ′
there exist two subsequences which start with bv′, continue on some other vertices from Pv
and end in two from b different vertices from X . In the first case, when b is the only black
colored neighbor of v′, the subsequence b → v′ → v′′ has to appear twice in W ′, since
otherwise W ′ can not continue (twice) from b to a black colored vertex without previously
traversing white vertex. This contradicts the fact that W ′ is a parallel 2-stable trace, since
bv′v′′ is a 2-repetition at v′. In the second case, we denote the set of white vertices that
appear to the left of b with W = {w1, . . . , wl}. (Note that l is an odd integer.) For an
example, see Figure 7(b), where those vertices are denoted with w1, w2, and w3. Next,
we denote the second black colored neighbor of v′ from N(v) with b′. The subsequence
b→ v′ → b′ can appear at most once inW ′ (otherwiseW ′ would have a 2-repetition at v′).
Assume next that for every w ∈ W , w continues to a vertex inW . Then vertices fromW
form an odd repetition in W ′, which can not appear in a parallel 2-stable trace. Therefore,
at least one vertex w fromW has to continue to a white colored vertex not included inW
(that is,w continues to a white colored vertex to the right of b). If subsequence b→ v′ → b′
does not appear inW ′ it follows that edge v′v′′ (arc v′v′′ and v′′v′) is used more than twice
in W ′: at least once to connect a vertex fromW to a white colored vertex not inW , twice
to connect b to a (black colored) vertex in X different from b′, and twice to connect b′ to a
(black colored) vertex in X different from b, which is absurd. If subsequence b→ v′ → b′
does appear in W ′ it (in addition to multiple appearances of v′v′′) follows that edge v′v′′
is not parallel in W ′. Since all the black colored vertices except b and b′ are to the right of
v′ both b→ v′ → v′′ and v′′ → v′ → b′ have to appear in W ′, which is also absurd.
Since v was an arbitrary vertex in G and d′ was an arbitrary integer, 2 < d′ ≤ d, it
follows that W is a parallel d-stable trace of G and therefore Theorem 1.2 is proved.
4 Concluding remarks
In this section we present two concepts which we assumed could be used for constructing
parallel 2-stable traces. Unfortunately, it has turned out, when proving Theorem 2.3, that
there exist graphs admitting only parallel 2-stable traces which can not be realized using
the here described constructions.
The first construction goes as follows. Let G be an Eulerian graph with n vertices
(denoted with v1, . . . , vn) fulfilling conditions of Theorem 2.3 and let W ′ be an Eulerian
circuit of G. W ′ induces a set of functions Π′ = {π′1, . . . , π′n}, where π′i : N(vi) −→
N(vi), π′i(v) = u if and only if v → vi → u or u → vi → v are sequences in W ′, for
1 ≤ i ≤ n. Note that u 6= v, becauseG is simple andW ′ traverses every edge exactly once.
Suppose that W ′′ is another Eulerian circuit in G such that W ′′ induces a set of functions
Π′′ = {π′′1 , . . . , π′′n} with above described characteristics. In addition demand that edges
are traversed in the same direction as in W ′, and that if π′i(v) = u then π
′′
i (v) 6= u and
π′′i (u) 6= v. Concatenate Eulerian circuitsW ′ andW ′′ into a double traceW in an arbitrary
vertex v. It is obvious from the construction that every edge is traversed twice in the same
direction inW and thatW is without 1-repetitions and 2-repetitions in any vertex other than
v. Hence, if a graph G admits two Eulerian circuits with above described characteristics,
12 Art Discrete Appl. Math. 2 (2019) #P1.07
then G admits parallel 2-stable trace as well.
It turns out that we cannot always construct a parallel 2-stable trace of G by concate-
nating two Eulerian circuits. For instance, the graphG from Figure 8 has a parallel 2-stable
trace:
v1 → v2 → v3 → v1 → v2 → v4 → v1 → v5 → v2 → v3 → v4 → v6 → v5 → v2 →
v4 → v6 → v7 → v9 → v8 → v6 → v7 → v10 → v8 → v11 → v7 → v9 → v10 →
v11 → v7 → v10 → v11 → v9 → v8 → v11 → v9 → v10 → v8 → v6 → v5 → v3 →
v1 → v5 → v3 → v4 → v1,
but because of the cut vertex v6, from any Eulerian circuit W of G we cannot construct
another Eulerian circuit with the described properties.
v3
v2
v1
v5
v4
v6
v8
v7
v11
v10
v9
Figure 8: Graph whose parallel 2-stable traces cannot be constructed by concatenating two
Eulerian circuits.
The main idea of the second construction is to find a parallel 2-stable trace in each
block of a graph G and then concatenate them into a parallel 2-stable trace of the graph G.
Let again G be an Eulerian graph fulfilling the conditions of Theorem 2.3. Denote blocks
of G with B1, . . . , Bk and cutvertices with v1, . . . , vl. Find first a parallel 2-stable trace
Wi in block Bi. Concatenate parallel 2-stable traces into a parallel 2-stable trace of G in
corresponding cutvertices. When concatenating, one has to be careful that no 1-repetitions
and 2-repetitions appear.
Similar as for the first construction, none of the parallel 2-stable traces of the graph G
from Figure 8 can not be constructed by concatenating parallel 2-stable traces in its blocks.
Vertex v6 is a unique cutvertex of the graph G and it is contained in both of its blocks.
Since v6 is of degree 2 in both blocks of the graph G, none of them admit parallel 2-stable
trace. Similar problem occurs if one or more blocks of G are bridges.
Next possible improvement could instead of parallel 2-stable traces in blocks demand
parallel 1-stable traces where 2-repetitions (or 1-repetitions if block is a bridge) would be
allowed at cutvertices but are then later removed during the concatenation into a parallel
2-stable trace of the whole graph.
An attempt to find efficient algorithms for constructing and counting stable traces of
graphs was made in [1]. It would be of interest to characterize graphs that do not have any
of the two above described properties of graphs from Figure 8 and then try to improve the
J. Rus: Parallelism of stable traces 13
algorithms from [1] by using the above described constructions for those special cases of
graphs.
References
[1] N. Bašić, D. Bokal, T. Boothby and J. Rus, An algebraic approach to enumerat-
ing non-equivalent double traces in graphs, MATCH Commun. Math. Comput. Chem.
78 (2017), 581–594, http://match.pmf.kg.ac.rs/electronic_versions/
Match78/n3/match78n3_581-594.pdf.
[2] R. B. Eggleton and D. K. Skilton, Double tracings of graphs, Ars Combin. 17 (1984), 307–323.
[3] G. Fijavž, T. Pisanski and J. Rus, Strong traces model of self-assembly polypeptide structures,
MATCH Commun. Math. Comput. Chem. 71 (2014), 199–212.
[4] H. Fleischner, Eulerian Graphs and Related Topics. Part 1, Volume 1, volume 45 of Annals of
Discrete Mathematics, North-Holland, Amsterdam, 1990.
[5] H. Fleischner, Eulerian Graphs and Related Topics. Part 1, Volume 2, volume 50 of Annals of
Discrete Mathematics, North-Holland, Amsterdam, 1991.
[6] H. Gradišar, S. Božič, T. Doles, D. Vengust, I. Hafner Bratkovič, A. Mertelj, B. Webb, A. Šali,
S. Klavžar and R. Jerala, Design of a single-chain polypeptide tetrahedron assembled from
coiled-coil segments, Nat. Chem. Biol. 9 (2013), 362–366, doi:10.1038/nchembio.1248.
[7] H. Gradišar and R. Jerala, De novo design of orthogonal peptide pairs forming parallel coiled-
coil heterodimers, J. Pept. Sci. 17 (2011), 100–106, doi:10.1002/psc.1331.
[8] S. Klavžar and J. Rus, Stable traces as a model for self-assembly of polypeptide
nanoscale polyhedrons, MATCH Commun. Math. Comput. Chem. 70 (2013), 317–
330, http://match.pmf.kg.ac.rs/electronic_versions/Match70/
n1/match70n1_317-330.pdf.
[9] V. Kočar, S. Božič Abram, T. Doles, N. Bašić, H. Gradišar, T. Pisanski and R. Jerala, TOPO-
FOLD, the designed modular biomolecular folds: polypeptide-based molecular origami nanos-
tructures following the footsteps of DNA, WIREs Nanomed. Nanobiotechnol. 7 (2015), 218–
237, doi:10.1002/wnan.1289.
[10] J. Rus, Antiparallel d-stable traces and a stronger version of Ore problem, J. Math. Biol. 75
(2017), 109–127, doi:10.1007/s00285-016-1077-2.
[11] G. Sabidussi, Tracing graphs without backtracking, in: R. Henn et al. (eds.), Methods of Oper-
ations Research XXV, Part 1, Anton Hain Verlag, Meisenheim, 1977 pp. 314–332, proceedings
of the First Symposium on Operations Research held at the Heidelberg University, September
1 – 3, 1976.
[12] D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996.