IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 52 (2014), 1198 ISSN 2232-2094 ANTIPARALLEL d-STABLE TRACES AND A STRONGER VERSION OF ORE PROBLEM Jernej Rus Ljubljana, March 24, 2014 ANTIPARALLEL d-STABLE TRACES AND A ^ STRONGER VERSION OF ORE PROBLEM Jernej Rus Faculty of Mathematics and Physics, University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia 00 jernej.rus@gmail.com March 23, 2014 CO CO CO CD 'H CD CO и a CD U Abstract Ö In 2013 a novel self-assembly strategy for polypeptide nanostructure design which could lead to significant developments in biotechnology was presented in [Design of a single-chain polypeptide tetrahedron assembled from coiled-coil segments, Nature Chem. Bio. 9 (2013) 362-366]. It was since observed that a polyhedron P can be realized by interlocking pairs of polypeptide chains if its corresponding graph G(P) admits a strong trace. In the present paper we characterize graphs which admit closed walk which traverses every edge exactly once in each direction and for every vertex v, there is no subset N of its neighbors, with 1 < |N| < d, such that every time the walk enters v from N, it also exits to a vertex in N. This extends C. Thomassen's characterization [Bidirectional retracting-free double tracings and upper embeddability of graphs, J. Combin. Theory Ser. B 50 (1990) 198-207] for the case d =1. Keywords: double trace; d-stable trace; strong trace; single face embedding; spanning tree; self-assembling; polypeptide nanostructure AMS Subject Classification (2010): 05C05, 05C10, 05C45 сч 1 Introduction Л О Recently Gradisar et al. [11] presented a novel polypeptide self-assembly strategy for nanostructure design relying on modularization and using orthogonal dimerizing segments. This could lead to significant developments in biotechnology since nanostruc-tures formed by self-assembly of biopolymers and especially polypeptides are known to be one of the most complex in nature. The main success of their research is a construction of a polypeptide self-assembling tetrahedron by concatenating 12 coiled-coil-forming segments separated by flexible peptide hinges in a prescribed order. To be more precise, a single polypeptide chain consisting of 12 segments was routed through 6 edges of the tetrahedron in such a way that every edge was traversed exactly twice. In this way 6 coiled-coil dimers were created and interlocked into a stable tetrahedral structure. This design also provides a foundation for all further investigations about 1 polypeptide folds based constructions using the set of orthogonal interacting polypep-tide segments. While the required mathematical support for the particular case of the tetrahedron was already given in [11], in [12] the first mathematical model for the investigations that could follow was presented. It was observed that a polyhedron P which is composed from a single polymer chain can be naturally represented with a graph G(P) of the polyhedron and since in the self-assembly process every edge of G(P) corresponds to a coiled-coil dimer, exactly two segments are associated with every edge of G(P). The authors have then shown that a polyhedral graph P can be realized by interlocking СЧ pairs of polypeptide chains if its corresponding graph G(P) contains a closed walk which traverses every edge exactly twice (double traces which will be more formally defined later). Beside that, no edge should immediately be succeeded by the same edge in the opposite direction and a vertex sequence u ^ v ^ w can appear at most once in any direction (u ^ v ^ w or w ^ v ^ u) in the double trace. Special types of such double traces where every edge is traversed twice in the same direction were studied in [24]. In [7] it was observed that the model presented in [12] is the appropriate mathematical description for graphs already constructed from coiled-coil-forming segments, yet it is deficient in modeling graphs with either very small (< 2) or large (> 6) degree vertices. Since the goal is to realize such graphs with coiled-coil-forming segments in the future, strong and d-stable traces (to be defined later) were presented as a natural extension of the model from [12] and graphs admitting them were characterized. One of the open problems left in [7] was a charecterization of graphs admitting antiparallel d-stable traces. An antiparallel d-stable trace is a closed walk which traverses every edge exactly once in each direction and for every vertex v, there is no subset N of its neighbors, with 1 < |N| < d, such that every time the walk enters v from N, it also exits to a vertex in N. Let T be a subtree of a graph G. Recall that an edge complement G — E (T) of a subtree of G is called a co-tree. Our main result, a characterization of graphs admitting 'Ja О Ö 00 CSI CSI antiparallel d-stable traces, can then be read as follows. Theorem 1.1 Let d > 1 be an integer. A graph G admits an antiparallel d-stable trace if and only if 6(G) > d and G has a spanning tree T such that each component of the co-tree G — E (T ) has an even number of edges or contains a vertex v of degree at least 2d + 2. Actually related topics were, motivated with embedding and single face embeddings of graphs in surfaces, studied a long time ago. In 1951, Ore [21] 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 [27] and [4], and completely solved almost 40 years later by Thomassen [26] as follows: i—I Theorem 1.2 [26, Theorem 3.3] A graph G 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 6(G) > 1 and G has a spanning tree T .such that each component of the co-tree G — E (T ) has an even number of edges or contains a vertex v of degree > 4. О CSI I Note that Theorem 1.2 is Theorem 1.1 for d = 1. Because polypeptides obtained from DNA tend to construct dimers which can be represented with antiparallel edges in a double trace, several generalizations of Theorem 1.2 motivated by biomolecular computing and assembling graphs from strands of СЧ DNA were already introduced in the past. Ellis-Monaghan observed in [5] how Theo-СЧ rem 1.2 characterizes graphs which may be constructed from a single strand of DNA. A generalization of Theorem 1.2 different from ours from [6] was used to characterize graphs which may be constructed from m strands of DNA. The paper is organized as follows. In the next section we first list basic concepts needed throughout the paper. Then we present double traces, d-repetitions, d-stable traces, strong traces, and some already known results about them. In Section 3 we prove some results about spanning trees for which also co-trees fulfill some additional requirements. Those results are later used in Section 4 where we prove Theorem 1.1. We conclude with some observations which follow from the theorem. Among others, an alternative visualization of graphs from Theorem 1.1 is observed — embedding graphs in pseudosurfaces, which in the past has received much less attention than embedding graphs in surfaces. 2 Double traces CO All graphs considered in this paper will be finite. We denote the degree of a vertex v by dc(v) or d(v) for short if graph G is clear from the context. The minimum and the maximum degree of G are denoted with 6(G) and A(G), respectively. If v is a vertex then N (v) denotes a set of vertices adjacent to v, and E (v) is the set of edges incident with v. A walk in G is an alternating sequence W = voeivi... (1) U Cti 00 so that for each i = 1,... , t, ei is an edge between vertices vi-1 and vj. We say that W passes through or traverses edges and vertices contained in the sequence (1). The length of a walk is the number of edges in the sequence, and we call v0 and vg the endvertices of W. A walk is closed if its endvertices coincide. An Euler tour in G is a closed walk which traverses every edge of G exactly once. G is an Eulerian graph if it admits an Euler tour. The fundamental Euler's theorem asserts that a (connected) graph G is Eulerian if and only if all of its vertices are of even degree. A double trace in G is a closed walk which traverses every edge of G exactly twice. By doubling every edge of graph, thus creating an Eulerian graph, and considering an Euler tour in this graph, Euler and later König [13, p. 23] observed that every connected graph G has a double trace. Let W be a double trace of length t in graph G, v an arbitrary vertex in G, and N С N (v). W has an N-repetition at v if the following implication holds: for every i G {0,..., t — 1}: if v = vi; then vi+1 G N if and only if vi-1 G N. (2) i In other words, a double trace W has an N-repetition at v if whenever W visits v coming from a vertex in N it also returns to a vertex in N. Note that v1 is the vertex immediately following vg, since we treat a double trace as a closed walk taking indices in (2) modulo t. An N-repetition (at v) is a d-repetition if |N| = d, and a d-repetition is sometimes also called a repetition of order d. An N-repetition at v is trivial if N = 0 or N = N(v). Clearly if W has an N-repetition at v, then it also has an (N(v) \ N)-repetition at v, a property also called a symmetry of repetitions. In [7] double traces without nontrivial repetitions of order < d were called d-stable traces while a strong trace was defined as a double trace without nontrivial repetitions. Here the same notations will be used. The next fact easily follows from the definitions of the d-stable trace, the strong trace and the symmetry of repetitions. For d = 2 it was already observed in [7]. 00 СЧ СЧ CO CD U a CD U Fact 2.1 In a graph G with 6(G) > d every strong trace is a d-stable trace. If also A(G) < 2d + 2, then every d-stable trace is also a strong trace. Graphs admitting strong and d-stable traces were characterized in [7] using a correspondence between strong traces and single face embeddings. Theorem 2.2 [7, Theorem 2.4] Every connected graph G admits a strong trace. л о Proposition 2.3 [7, Proposition 3.4] Let G be a connected graph. Then G admits a d-stable trace if and only if 6(G) > d. In an arbitrary double trace W of a graph G every edge is traversed twice. If W traverses an edge e = uv in the same direction twice (either both times from u to v or both times from v to u) then we call e a parallel edge, otherwise e is an antiparallel edge. 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. The next theorem from [7] characterizes graphs which admit antiparallel strong traces. It turns out that those are exactly the graphs which have a single face embedding in an orientable surface. 00 Theorem 2.4 [7, Theorem 4.1] A graph G admits an antiparallel strong trace if and only if G has a spanning tree T such that each component of the co-tree G — E (T) has an even number of edges. To make our proofs more transparent we conclude this section with the next concept similar to the detachment of graph presented by Nash-Williams in a series of papers [17], [18], [19], and [20]. Definition 2.5 Let G be a graph, v a vertex of degree > 2, and (N\,..., Nk) a partition of N(v). We obtain graph G' from graph G with splitting procedure in v using N\,... ,Nk as follows. Replace vertex v with k new nonadjacent vertices v\, ... ,vk in G'. Add edges between vi and the vertices from Ni for 1 < i < k. See also Fig. 7. CO For any other details about double traces, graph embeddings, or other terms and concepts from graph theory not defined here we refer to [8, 9], [15], and [30], respectively. £ 3 Spanning trees, co-trees and deficiency CO CO A tree T is a spanning tree if and only if G — E (T) is a minimum co-tree. The number of edges in any spanning tree of G is |V(G)| — 1, while the number of edges in any minimum co-tree of G is equal to |E(G)| — |V(G)| + 1 and is called a Betti number, ß(G). Note that a co-tree is not necessarily connected. A component C of a co-tree G — E (T ) is called an even component or an odd component if C has an even or an odd number of edges, respectively. The deficiency of a spanning tree T in G, denoted with {(G,T), is defined as the number of odd components of the co-tree G — E (T). The deficiency of a graph G, denoted with {(G), is defined as the minimum tree deficiency over all spanning trees T of G. Spanning trees that realize {(G) are called Xuong trees. In [31] and [32] spanning trees, co-trees, Betti number, and deficiency were used for new graph embeddings technique. Here we are interested in spanning trees of G such that each odd component of the co-tree contains a high degree vertex v (de(v) > d for some integer d). Therefore 'J- л we define d-deficiency of a graph G, denoted with £(G,d), as the minimum deficiency over all spanning trees T of G such that each odd component of the co-tree G — E (T) contains a vertex v with dG(d) > d. Note that for every graph G and any integer d, e(G) < e(G,d). For such a spanning tree T in G that each component of the co-tree G — E(T) is even or contains a vertex of degree at least d, we also define d-deficiency of spanning tree T in G, denoted with £(G, d, T), as the number of odd component in the co-tree G — E (T). Since any vertex v G V (G) is contained in at most one (odd) component of the co-tree G — E (T), the next definition makes sense: 00 Definition 3.1 Let G be a graph, T a spanning tree of G, C an odd component in the co-tree G — E (T ), and v an arbitrary vertex in C. Let v\,... ,vc be the neighbors of v in C. O(v, T) is the set of odd components that we obtain from C if we split v into c new vertices and pairwise adjacent them to v\,... ,vc. Analogously we denote the set of even components with E (v, T ). со CD Observe that because C is an odd component, the number of odd components in O(v,T) is also odd and therefore |O(v,T)| > 1. In the rest of this section we prove some observations about spanning trees of graphs. СЧ Lemma 3.2 Let G be a connected graph, U С V (G), v an arbitrary vertex of degree > 2 in G, and N\,...,Nk С N (v), k > 2, a partition of neighbors of v. Let graph CO G' be obtained from G with splitting procedure in v using Ni,...,Nk. Let v\,... ,vk be new vertices in G'. If G' has a spanning tree T' such that each component of the co-tree G' — E(T') is even or contains a vertex from U or at least one of new vertices vi,... ,vk, then there exists a spanning tree T in G such that each component of the co-tree G — E (T ) is even or contains a vertex from U or contains v. & Proof. Assume that G and G are two connected graphs such that G can be obtained from G' by identifying k > 2 vertices vi,... ,vk that have disjoint neighborhoods with an arbitrary vertex v of degree at least 2. In addition assume that G' has a spanning tree T' such that each component of the co-tree G' — E (T') is even or contains a vertex from U С V (G) \ {vi,..., vk} or contains at least one of vi,..., vk. We proceed by induction on k. Let k = 2 and let vi and v2 be two vertices that have disjoint neighborhoods N(vi) and N(v2) that we have to identify into v in order to obtain G from G'. Obtain subgraph T'' in G from T' as follows. Let e' = xy be an arbitrary edge in T'. If x, y G {vi, v2} we put e' into T''. If x = vi then replace e' with vy. Analogously we replace edge where x = v2, or y = vi, or y = v2 with vy, xv, and xv, respectively (if they appear in T'). Since T' is a spanning tree of G', there exists a unique vi ,v2-path P in T'. Let u be the neighbor of vi in P and e = uvi, see Fig. 1 (a). • и P P I CSI co со со CD m и а CD U СЧ сч л о и d (a) T' at vi and v2 in G' (b) T at v in G Figure 1: Construction of a spanning tree T in G from a spanning tree T' in G' from the proof of Lemma 3.2. Edges contained in trees T' and T are drawn thick. О Ö We claim that T = T'' — e is a spanning tree of G and each component of the co-tree G — E (T) is even or contains a vertex from U or contains v. If T is not a spanning subgraph of G then there exists a vertex x G G \ T. Since v is incident with at least one edge from T by construction, x = v. If x G V (G) \ {v} is not incident with any edge from T it follows that x is not incident with any edge from T' in G', a contradiction. Therefore T is a spanning subgraph in G. Let now x,y = v be two arbitrary vertices in G. Since T' is a spanning tree of G', there exists a unique x,y-path Q' in T'. If Q' does not contain an edge e then it is clear from the construction of T that Q' is also contained in T. Assume now that e G Q'. Without loss of generality we can write Q' = x — Q1 — vi — e — u — Q2 — y. Denote the part of the path P that goes from v2 to u with P'. Since u is an endvertex of Q2 and u is an endvertex of P', Q2 and P' are not disjoint. We can then find a x, y-path in x — Qi — v — P' — u — Q2 — y. Analogously if x = v or y = v. Therefore T is connected. Let now C be a cycle in T. If C does not contain the vertex v it follows from the construction of T that C is a cycle in T', which is absurd. Therefore C has to contain v. Let x be an arbitrary vertex in C different from v. Without loss of generality we can write C = v — C1 — x — C2 — v, where Ci and C2 are two vertex disjoint x,v-paths. If C1 and C2 are both disjoint v,v1-paths in T' or both disjoint x,v2-paths in T' we get a contradiction with the fact that T' is a spanning tree. Therefore without loss of generality we can assume that C1 is a x,v1-path in T' while C2 is a x,v2-paths in T'. Since T' is a spanning tree it follows that for any two vertices there exists a unique path between them in T'. Therefore P = v1 — C1 — x — C2 — v2 and C1 starts with e. Since T = T'' — e, C1 can not be contained in T. It follows that T is a spanning tree of G. Assume that O is an odd component of the co-tree G — E(T) which does not contain a vertex from U or v. It follows that O is an odd component of the co-tree G' — E (T ') which does not contain a vertex from U or any of the vertices v1 and v2 which is absurd. We have thus proved that if G is obtained from G' by identifying exactly two vertices into vertex v, then G has a spanning tree T such that each component of the co-tree G — E (T ) is even or contains a vertex from U or contains v. Let next k > 2, let induction hypothesis be true for any l < k, and let vi,... ,vk be vertices that have disjoint neighborhoods N(v1),...,N(vk), that we have to identify into v in order to obtain G from G'. Construct G'' from G' by identifying vertices v1,..., vk-1 into a new vertex v''. By induction G'' has a spanning tree T'' such that each component of the co-tree G'' — E (T'') is even or contains a vertex from U or contains v''. Identify vertices and v'' into a vertex v in G'' to obtain the graph G. Now by induction also G has a spanning tree T such that each component of the co-tree G — E (T ) is even or contains a vertex from U or contains v. □ i—l Note that in Lemma 3.2, U can be the empty set. Lemma 3.3 Let G be a connected graph, T a spanning tree of G, and v an arbitrary vertex in G such that v is contained in an odd component of the co-tree G — E (T). Let G be the family of all graphs obtained from G with splitting procedure in v using two subsets of N(v) of cardinality ^rp and ^vi . There exists a graph G' e G such that G' has a spanning tree T' and £(G',T') < {(G, T). СЧ Proof. Let G be a connected graph, T a spanning tree of G, and v an arbitrary vertex in G such that v is contained in an odd component of the co-tree G — E (T ). 00 Since T is a spanning tree of G there exists an edge ey = yv e E (T) and because v is contained in an odd component of the co-tree G — E(T), there also exists an edge ew = wv e E(G)\E(T). Clearly ey and ew are two different edges, therefore dG(v) > 2. Because T is a spanning tree of G, there exists a unique v,w-path in T. Denote the vertex adjacent to v in this path with u and the part of this path between u and w with P. Let N be a subset of N(v) with vertices such that u e N while w e N. Obtain a graph G' from G with the splitting procedure in v using N and N (v) \ N. Denote new vertices which are connected to vertices from N and N(v) \ N with v' and v'', respectively. Construct the subgraph T' in G' from T as follows. Let e = xy be an arbitrary edge in T. If x, y = v put e into T'. If x = v and y e N then replace e with v' y. Analogously we replace edges where x = v and y e N (v) \ N, or y = v and x e N, or y = v and x e N (v) \ N with v''y, xv', or xv'', respectively. Finally put ew into T'. See Fig. 2. Parallel as in the proof of Lemma 3.2 we can prove that T' is a spanning tree of G'. Because u and w were arbitrary neighbors of v in G, such that uv e E (T) and wv e E(G) \ E(T), every graph obtained from G with splitting procedure in v using u and w with above described properties has a spanning tree T' (obtained from T by adding edge wv) and is therefore connected. We claim that for at least one of those graphs G', T' is such a spanning tree that {(G',T') < {(G,T). л о и d оо p p W (a) T at v in G (b) T' at v' and v" in G' 0 Ö o СЧ 1 СЧ со СЧ СЧ г со со со CD 'H Jh CD СО а CD U Оч Figure 2: Construction of a spanning tree T" in G' from a spanning tree T in G from the proof of Lemma 3.3. Edges contained in trees T and T' are drawn thick. Let from now on C be the odd component of the co-tree G — E(T) which contains v. Note first that because v lies in exactly one component of the co-tree G — E (T ), every component C' in the co-tree G — E(T) different from C will also be in the co-tree G' — E(T '). Note next that components which will be formed from C in G' — E (T ') will be constructed from components in E (v, T ) and O (v,T ) from one of which one of the edges incident with v will be removed. Finally, it is clear from Definition 3.1 that every component O G O (v, T ) and E G E (v, T ) remains connected if we remove an edge incident with v from O. Note also that O and E can have more than one edge incident with v. We consider two cases: Case 1: |O(v,T)| < 2 Let e = vw G Ow for some Ow G O (v, T ) and f = vu G T be two edges incident with v in G. Use them as ew and eu in the at the beginning of the proof described construction of G', respectively. Since |O(v,T)| < d(v) 2 we can connect v'' to w and for every form Ow different component O G O (v, T ) to at least one vertex from O, when constructing G'. When ew is put in T', the odd component Ow becomes even. In O(v,T) therefore remains an even number (possibly 0) of odd components which are all incident with v'' in G', while components from E (v, T) remain even. Therefore C remains connected and becomes an even component of the co-tree G' — E (T') and T' is a spanning tree of G' such that £(G',T') < £(G,T). Case 2: |O(v,T)| > d(v) 2 1 Since |O(v,T)| > 1, |O(v,T)| is odd, and there also exists an edge in T incident with v, it follows that d(v) > 4. We will use uv to denote an edge incident with v from T. л о и d оо 0 ö о сч 1 сч со сч сч г со со со CD 'Н CD СО а CD Jh Оч We first describe how G' is obtained from G and T' from T such that each component of the co-tree G' — E (T') is even if at least one of the next conditions is fulfilled: (i) There exists an odd component O\ e O(v,T) with at least two edges incident with v. (ii) d(v) = 0 (mod 4). (iii) Spanning tree T and v have more than one incident edge. (iv) |E(v, T)| > 0. In (i) denote edges from Oi with e1 = vwi and e2 = vw2. Denote an edge incident with v e T with f = vu e T. Since |O(v,T)| > 1, there exists at least one more vertex w3 such that e3 = vw3 e O2 e O(v,T), where O1 = O2. Use e3 and f as ew and eu__ in t 2 Since ìe at tlie beginning of the proof described construction of G', respectively. , d(2v) > 2, we can connect v' to u and w1, and connect v'' to w3 and w2. When e3 is put in T', odd component O2 becomes an even component and since w1 is connected to v' and w2 is connected to v'', v' and v'' are in the same component of the co-tree G' — E(T') . In O(v,T) we now have an even number of odd components. Therefore T' is a spanning tree of G' such that each component of the co-tree G — E (T') is even. For (ii) — (iv) the parity of d(v), additional edge incident with v from T, or an edge incident with v from a component in E (v, T ) is used to achieve that v'' is adjacent to an odd number of different components from O(v,T), while v' is connected to u via edge replacing vu from T and the rest of the odd components (an even number of them). Note that because components from O(v,T) and E (v, T) can have more than one edge incident with v, v' and v'' can both be adjacent to the same component from O(v,T) or E(v,T). Note also that to achieve above described partition, we also allow that d(v') = while d(v'' ) = .Let O be one of those components which will be adjacent to v'' and e = vw an edge in it. Use e as ew in the at the beginning of the proof described construction. Therefore O will then become an even component and v' and v'' will be both connected with even number of odd components from O(v, T). Assume now that none of the above conditions is fulfilled. Then |O(v, T) | = dG(v) — 1 and we can without loss of generality assume that G looks at v as it is shown at Fig. 3, where O1, O2, and O3 at Fig. 3 are (together with edges incident with v) odd components from O(v,T). Note that there can be more than just 3 odd components. Note also that X which contains vertex u, can be an even (possibly empty) component of the co-tree G — E(T ) or an odd component disjoint with C in the co-tree G — E (T ). We consider two subcases. In the first subcase there exist such two odd components O1 and O2 in O(v, T), that there exists two disjoint paths P1 and P2 between them and vertex u. Connect O1 and O2 with v'' at vertices w and v2 in G', respectively. Denote л о и d оо о со CD 'Н CD Figure 3: Graph G and a spanning tree T at vertex v if none of the conditions from Case 2 in the proof of Lemma 3.3 is fulfilled. Note that because T is a spanning tree, there exist u, v-paths in T not shown in the figure, but there are no paths completely contained in G — E (T ) between different odd components. Edge contained in spanning tree T is drawn thick. another component from O(v,T) which is in G' connected to v' with O3 and a vertex from O3 adjacent to v with v3. Denote the vertex adjacent to u in Pi with p (note that p can be equal to w). Construct spanning tree T' from T as described in previous subcases. Then add edges v''v2 and v'v3 to T' and remove edges v'u and up. See Fig. 4. It is not difficult to see that T' is a spanning tree of G'. Component O2 and O3 are CSI now even and are disjoint with every other odd component of G' — E (T'). Vertex v'' is still adjacent to an even number of odd components from O(v,T). Vertex v' is still adjacent to an even number of odd components from O(v,T) that are different from O3. Also O1 is now even component of G' — E(T'), or is connected to X. The rest of the odd component C has now common vertex u with X. If X was some from C different odd component of G — E (T ), we connected C with some other odd component of G — E (T ) in T' and no matter if component containing X is odd or even it follows that {(G',T') < {(G, T). We have therefore connected two odd components into one odd component or join one even and one odd component into one even component (the parities are valid after we already consider removed edges). In the second subcase two odd components in O(v,T) which would be connected to u with two disjoint paths do not exists. Without loss of generality we can assume that T looks like is shown at Fig. 5 (a). It is not difficult to see that a spanning tree T2 at Fig. 5 (b) fulfills condition (ш) and that {(G,T2) < {(G,T). Analogously when yi = У2 or yi = w (and Yi = Y2 or Yi = Oi). We have thus constructed graph G' which has a spanning tree T' such that {(G', T') < {(G,T) and since {(G,T) was not in ahead prescribed, above described construction is • и л о и d оо (a) T at v in G (b) T' at v' and v" in G' 0 Ö о сч 1 сч со сч сч г со со со CD 'Н CD СО и а CD U 0ч Figure 4: First subcase in the proof of Lemma 3.3. There also exists a path in T containing v3 and only one of vertices u, w, or v2 not shown in the Figure. Edges contained in trees T and T' are drawn thick. Y2 (a) T at v in G (b) T2 at v in G Figure 5: Second subcase in the proof of Lemma 3.3. Edges contained in trees T and T2 are drawn thick. always possible. □ л о и d оо 0 ö о сч 1 сч со сч сч г со со Because vertex v from Lemma 3.3 is arbitrary and since during the constructing from the the proof of Lemma 3.3, G \ (v U N (v)) remains equivalent, next lemma easily follows if we assume that vertex v is of degree > d: Lemma 3.4 Let G be a connected graph, let T be such a spanning tree of G that each component of the co-tree G — E (T ) is even or contains a vertex of degree at least d, and v an arbitrary vertex of degree at least d in G which is contained in an odd component of the co-tree G — E (T ). Let G be the family of all graphs obtained from G with splitting 2 and d(v) 2 There exists procedure in v using two subsets of N(v) of cardinality a graph G' G G such that G' is connected and it has a spanning tree T' such that each component of the co-tree G' — E (T') is even or contains a vertex of degree at least d and £(G',d,T') < £(G,d,T). Note that it is not necessary that every graph G' G G constructed with splitting procedure as described in Lemma 3.4 has a spanning tree T' such that £(G',d,T') < £(G,d,T). See Fig. 6 where construction from Lemma 3.4 is used to obtain graphs G' and G'' from a graph G and spanning trees T' and T'' from a spanning tree T, while £(G, 4, T) = 2, £(G', 4, T') = 1, and £(G'', 4, T'') = 2. (a) G and T (b) G' and T' (c) G" and T'' Figure 6: G', G'' and T', T'' are obtained from G and T using construction from Lemma 3.4, respectively. Values of their d-deficiency are £(G, 4, T) = 2, £(G', 4, T') = 1, and £(G'', 4, T'') = 2. Edges contained in spanning trees are drawn thick. CO CD 'H CD CO и a CD U 4 Proof of Theorem 1.1 We now present the proof of Theorem 1.1. Proof. Suppose first that the graph G admits an antiparallel d-stable trace W. Proposition 2.3 implies that ö(G) > d. If A(G) < 2d + 2, then the Fact 2.1 implies that W is also an antiparallel strong trace of G. By Theorem 2.2 it then follows that G has a spanning tree T such that each component of the co-tree G — E (T ) is even. л о и d оо 0 ö о сч 1 сч со сч сч г со со со CD 'Н CD СО а CD Jh Оч Assume next that A (G) > 2 d + 2. Denote the number of vertices where W has a nontrivial repetitions with r(W). Note that W does not have any nontrivial repetition of order smaller or equal to d. We proceed with induction on r = r(W). If r = 0, it follows that W is an antiparallel strong trace of G and again, by Theorem 2.2 G has a spanning tree such that each component of the co-tree G — E(T ) is even. Let next r = 1 and let v, d(v) > 2d + 2, be a unique vertex of G where W has a nontrivial repetition (of order greater than d). To make the argument more transparent, assume first that W has exactly two nontrivial repetitions at v: N and N (v) \ N. Obtain graph G' from G with splitting procedure in v using N and N (v) \ N. Denote new vertices which are adjacent to vertices from N and N (v) \ N with v' and v'', respectively. See Fig. 7. Construct double trace W' in G' from W as follows. Let e = xy be an arbitrary (oriented) edge of W. If x = v and y = v we put e into W'. If x = v and y G N then we replace e with v'y. Analogously we replace edges where x = v and y G N (v) \ N, or y = v and x G N, or y = v and x G N (v) \ N with v''y, xv', or xv'', respectively. Note first that any edge e' that appears in G' has its unique corresponding edge e in G. Since e is traversed twice in the opposite direction in W, the edge e' is traversed twice in the opposite direction in W'. Hence W' is an antiparallel double trace. For any vertex u G V (G) \ {v', v''}, W' is without nontrivial repetition at u since otherwise already W would have a nontrivial repetition at u. W' is without nontrivial repetitions at v' and v'' by construction. Therefore W' is an antiparallel strong trace in G' and Theorem 2.4 the implies that G' has a spanning tree T' such that each component of G' — E (T') is even. It then follows by Lemma 3.2 that G has a spanning tree T such that each component of the co-tree G — E(T) is even or contains v, which is of degree > 2d + 2. (a) W at v in G (b) W' at v' and v" in G' Figure 7: Construction from the proof of Theorem 1.1. Note that because W is a double trace there exists a path between the neighbors of v in the upper and the lower part of figure, not shown here. Analogously for W'. л о и d If W has k > 2 nontrivial repetitions at v, and Ni,... ,Nk С N (v), U 1 2d + 2. We have thus proved that if G has an antiparallel d-stable trace with nontrivial repetitions appearing only at vertex v of degree > 2d + 2, then G has a spanning tree T such that each component of the co-tree G — E (T ) is even or contains a vertex of degree > 2d + 2. Assume now that r > 1 and let v be one of the vertices where W has nontrivial repetitions. We again use the above described construction to obtain graph G' from G by splitting v into k new vertices and finding antiparallel double trace W' in G'. It is clear that r(W') < r(W) and hence G' has a spanning tree T' such that each component of the co-tree G — E (T) is even or contains vertex of degree > 2d + 2, by induction on r. By Lemma 3.2 it then follows that also G has a spanning tree T such that each component of the co-tree G — E (T) is even or contains a vertex of degree > 2d + 2 or contains a vertex v, which is also of degree > 2d + 2. СЧ Conversely, let a graph G, 5(G) > d, has a spanning tree T such that each com-СЧ ponent of the co-tree G — E(T) has an even number of edges or contains a vertex v, dG(v) > 2d + 2. We proceed by induction on £ = £(G, 2d + 2). If £(G, 2d + 2) =0, then G has a spanning tree T such that each component of the co-tree G — E (T ) is even. Theorem 2.4 then implies that G admits an antiparallel strong trace W and since 5(G) > d it follows from the Fact 2.1 that W is also an antiparallel d-stable trace. Let £ = 1, T a spanning tree of G which realizes £, and v a vertex of degree at least 2d + 2 in a unique odd component of the co-tree G — E (T ). Let G be the family О Ö 00 CSI CSI m CD ■i—i и of all graphs obtained of N(v) of cardinality adjacent to exists a grap rom G with splitting procedure in v using two disjoint subsets 2 and d(v) 2 Denote new vertices adjacent to d(v) 2 and d(v) 2 neighbors of v with v' and v'', respectively. By Lemma 3.3 there h G' G G such that G' has a spanning tree T' for which each component of the co-tree G' — E (T') is even. Theorem 2.4 then implies that G' admits an antiparallel strong trace W'. Construct double trace W in G from W' as follows. Let e' = xy be an arbitrary (oriented) edge of W'. If x,y G {v', v''} we put e' into W. If x G {v', v''} then replace e' with vy. Analogously we replace edges where y G {v', v''} with xv. Note first that any edge e that appears in G has its unique corresponding edge e' in G'. Since e' is traversed twice in the opposite direction in W', the edge e is traversed twice in the opposite direction in W. Hence W is an antiparallel double trace. For any vertex и d оо о» u G V (G) \ (v', v"}, W is without nontrivial repetition at u because otherwise already W' would have a nontrivial repetition at u. W has exactly two nontrivial repetitions at v, Ng'(v')-repetition and NG'(v'')-repetition, by construction. Since 6(G) > d, \NG (v')| = M > d, and |NG' (v')| = ^ > d, W is an antiparallel d-stable trace in G. We have thus proved that if G has a spanning tree T such that each component of the co-tree G — E (T) is even or contains a vertex of degree at least 2d + 2 and £(G, 2d + 2) < 1, then G admits an antiparallel d-stable trace. Assume now that £ > 1, T is a spanning tree of G which realizes £, and vis an arbitrary vertex of degree at least 2d + 2 in an arbitrary odd component of the co-tree G — E (T). As in the case £ = 1, define the family of graphs Q. By Lemma 3.4 there exists a graph G' G Q such that G' has a spanning tree T' for which £(G', 2d + 2, T') < £(G,2d + 2,T). Since a spanning tree T realizes (2d + 2)-deficiency of G it follows that £(G', 2d + 2) < £(G, 2d + 2) and hence G' admits an antiparallel d-stable trace W' by induction. As above construct an antiparallel double trace W in G from W' by properly replacing v' and v'' with v. From construction of W it follows that if W has a repetition of order < d at some vertex u = v already W' has a repetition of order < d at vertex u, and that if W has a repetition of order < d at vertex v also W' has a repetition of order < d at v' or v'', which is absurd. Therefore G admits an antiparallel d-stable trace. This concludes the proof of Theorem 1.1. cn □ СЧ from [16] and [28] could also be used to show that in special case every 4-edge-connected graph G, 6(G) > d, with a vertex of degree at least 2d + 2 or an even Betti number has an antiparallel d-stable trace. CO CO Theorem 4.1 [14, Theorem 2] Every 4-edge-connected graph contains two edge-disjoint spanning trees. By Theorem 4.1 4-edge-connected graph G has a spanning tree T such that a co-tree G — E (T) has exactly one component. 5 Concluding remarks m 5.1 Characterization of graphs admitting double and related traces Theorem 1.1 also concludes the characterization of graphs admitting (parallel and antiparallel) double, stable, and strong traces, a problem which was first posed in [12]. Conditions required for graphs to admit double and related traces are collected in Table 1. Note again that all the graphs considered are finite and connected. For the sake Note that the next corollary of Tutte and Nash-Williams's tree-packing theorem сч л о и 00 of clarity of presentation, a spanning tree T of graph G such that each component of the co-tree G — E (T) is even is denoted with XT, while a spanning tree T' such that each odd component of the co-tree G — E (T') contains a vertex of degree at least d is denoted with XT(d). CONDITION none parallel antiparallel double VG Eulerian VG M [13] [29, Theorem 2] [25] C <1 Pi T d-stable 5(G) > d [7, Theorem 3.4] 5(G) > d Л Eulerian [7, Theorem 5.4] 5(G) > d Л 3XT(2d + 2) (Theorem 1.1) strong VG Eulerian 3XT [7, Theorem 2.4] [7, Theorem 5.3] [7, Theorem 4.1] 0 Ö о СЧ 1 СЧ CO СЧ СЧ £ CO со CO CD 'H CD CO и a CD U Table 1: Required conditions for graphs to admit presented double traces 5.2 Polynomial algorithm for d =1 In [10] a polynomial time algorithm which for an arbitrary graph G finds a spanning tree T such that that each component of the co-tree G — E (T) is even or determine that no such T exists was presented. It uses matroids parity (or matching). In [26] Thomassen modified the algorithm so it also works for a spanning tree T such that each component of the co-tree G — E(T) is even or contains a vertex of degree at least 4. It seems that the algorithm from [10] modified in a similar way as in [10] would also work for spanning trees, which satisfy conclusion from Theorem 1.1 for arbitrary d. 5.3 Pseudosurfaces We conclude with an alternative characterization which may help to visualize the graphs considered in Theorem 1.1. In [7] it was observed that graph G admits a strong trace if and only if G has a single face embedding in some surface, and that graph G admits an antiparallel strong trace if and only if G has a single face embedding in some orientable surface. Characterizations of graphs admitting single face embeddings from [3] and [2] were then used to characterize graphs which admit (antiparallel) strong traces. Here we can do the reverse and use the characterization of graphs admitting antiparallel d-stable trace to characterize graphs which have some other properties as well. A pinched open disk is defined in [22] as a topological space obtained from k copies of open disks by identifying their respective centers to a single vertex. Pseudosurfaces are then obtained with relaxation of the definition of surfaces by allowing the neighborhoods of points to be homeomorphic not only to open disks or half-disks but also to pinched open disks. A pseudosurface can be obtained from a single surface by identifying its points, from two or more surfaces by pairwise identifying some number of points on one sphere with points on the other surfaces, or by combination of previous two operations. A pseudosurface is an orientable pseudosurface if and only if all the surfaces used in its construction are orientable. Since single face embeddings can only be defined for the first of the three presented constructions of pseudosurfaces, we pose next observation only for those pseudosurfaces. Theorem 1.1 actually characterizes graphs which have a single face embedding in some orientable pseudosurface obtained from a single surface by identifying its points, such that for every vertex v and every neighborhood N of v homeomorphic to an open disk, v has at least d + 1 neighbors in N. Note that if v is a vertex where k copies of open disks were identified and form a pinched open disks, then v has k disjoint neighborhoods homeomorphic to an open disk. This alternative characterization is especially interesting since embeddings of graphs in pseudosurfaces have received much less attention than embeddings in surfaces, although the literature does contain some results, see [23] or [1] for example. О Acknowledgements The author is grateful to Gasper FijavZ, Luis Goddyn, and Sandi KlavZar for many helpful suggestions. О References СЧ 00 [1] L. Abrams, D. C. Slilaty, Algebraic characterizations of graph imbeddability in surfaces and pseudosurfaces, J. Knot Theory Ramifications 15 (2006) 681-694. CSI CSI [2] M. Behzad, G. Chartrand, L. Lesniak-Foster, Graphs and Digraphs, Prindle, Weber and Schmidt, Boston, 1979. CO CO [3] J. Edmonds, On the surface duality of linear graphs, J. Res. Natl. Bur. Stand. Sec. B: Math. & Math. Phys. 69B (1965) 121. [4] R. B. Eggleton, D. K. Skilton, Double tracings of graphs, Ars Combin. 17A (1984) 307-323. [5] J. Ellis-Monaghan, Transition polynomials, double covers, and biomolecular computing, Congr. Numer. 166 (2004) 181-192. m [6] H. Fan, X. Zhu, Oriented walk double covering and bidirectional double tracing, J. Graph Theory 29 (1998) 89-102. CD [7] G. FijavZ, T. Pisanski, J. Rus, Strong traces model of self-assembly polypeptide structure, MATCH Commun. Math. Comput. 71 (2014) 199-212. [8] H. Fleischner, Eulerian Graphs and Related Topics. Part 1. Vol. 1., North-Holland, Amsterdam, 1990. [9] H. Fleischner, Eulerian Graphs and Related Topics. Part 1. Vol. 2., North-Holland, Amsterdam, 1991. Л [10] M. L. Furst, J. L. Gross, L. A. McGeoh, Finding a maximum-genus graph imbedding, JACM 35 (1988) 523-534. [11] H. Gradisar, S. Božic, T. Doles, D. Vengust, I. Hafner Bratkovic, A. Mertelj, B. Webb, A. Sali, S. Klavžar, R. Jerala, Design of a single-chain polypeptide tetrahedron assembled from coiled-coil segments, Nature Chem. Bio. 9 (2013) 362366. i—l [12] 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. Ö [13] D. König, Theorie der endlichen und unedlichen Graphen, Chelsea Publ. Comp., New York, 1950 (first publ. by Akad. Verlagsges., Leipzig, 1936). [14] S. Kundu, Bounds on the number of disjoint spanning trees, J. Combin. Theory Ser. B 17 (1974) 199-203. i [15] B. Mohar, C. Thomassen Graphs on Surfaces, The Johns Hopkins University Press, 2001. СЧ [16] C. St. J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961) 445-450. [17] C. St. J. A. Nash-Williams, Acyclic detachments of graphs, Graph Theory and Combinatorics (1979), Pitman, San Francisco 87-97. нн [18] C. St. J. A. Nash-Williams, Detachments of graphs and generalized euler trails, Surveys in Combinatorics (1985), Cambridge Univ. Press, London 137-151. [19] C. St. J. A. Nash-Williams, Connected detachments of graphs and generalized euler trails, J . London Math. Soc. 31 (1985) 17-29. CO и CD [20] C. St. J. A. Nash-Williams, Amalgamations of almost regular edge-colourings of simple graphs, J. Combin. Theory Ser. B 43 (1987) 322-342. [21] O. Ore, A problem regarding the tracing of graphs, Elemente der Math. 6 (1951) 49-53. [22] T. Pisanski, P. Potocnik, Graphs on surfaces, in: J. L. Gross, J. Yellen (Eds. Handbook of Graph Theory (2003), CRC Press LLC 611-624. [23] W. S. Petroelje, Imbedding graphs in pseudosurfaces, Masters Thesis, Western Michigan University (1971). 00 [24] J. Rus, Parallelism of stable traces, submitted (2013). [25] G. Tarry, Le probleme des labyrinthes, Nouv. Ann. (3) XIV (1895) 187-190. О [26] C. Thomassen, Bidirectional retracting-free double tracings and upper embed-dability of graphs, J. Combin. Theory Ser. B 50 (1990) 198-207. [27] D. J. Troy, On traversing graphs, Amer. Math. Monthly 73 (1966) 497-499. [28] W. T. Tutte, On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961) 221-230. [29] P. D. Vestergaard, Doubly traversed euler circuits, Arch. Math. 26 (1975) 222-224. [30] D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 1996. [31] N. H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B 26 (1979) 217-225. О [32] N. H. Xuong, Upper-embeddable graphs and related topics, J. Combin. Theory Ser. B 26 (1979) 226-232. СЧ ( ) CO CD 'H CD CO a