Informatica 30 (2006) 281-288 281 Deterministic Soliton Graphs Miklčs Bartha Department of Computer Science Memorial University of Newfoundland St. John's, NL, Canada E-mail: bartha@cs.mun.ca Miklčs Krčsz Department of Computer Science JuMsz Gyula Teacher Training College University of Szeged, Hungary E-mail: kresz@jgytf.u-szeged.hu Keywords: soliton automata, matching theory Received: March 23, 2005 Soliton graphs are studied in the context of a reduction procedure that simplifies the structure of graphs without affecting the deterministic property of the corresponding automata. It is shown that an elementary soliton graph defines a deterministic automaton iff it reduces to a graph not containing even-length cycles. Based on this result, a general characterization is given for deterministic soliton graphs using chestnut graphs, generalized trees, and graphs having a unique perfect matching. Povzetek: Članek obravnava grafe brez lihih ciklov. 1 Introduction One of the most ambitious goals of research1 in modern bioelectronics is to develop a molecular computer. The introduction of the concept "soliton automaton" in [5] has been inspired by this research, with the intention to capture the phenomenon called soliton waves [4] through an appropriate graph model. Soliton graphs and automata have been systematically studied by the authors on the grounds of matching theory in a number of papers. Perhaps the most significant contribution among these is [2], where soliton graphs have been decomposed into elementary components, and these components have been grouped into pairwise disjoint families based on how they can be reached by alternating paths starting from external vertices. This paper can also serve as a source of further references on soliton automata for the interested reader. Since soliton automata are proposed as switching devices, deterministic automata are in the center of investigations. The results reported in this paper are aimed at providing a complete characterization of deterministic soliton automata. The two major aspects of this characterization are: 1. Describing elementary deterministic soliton graphs. 2. Recognizing that deterministic soliton graphs having an alternating cycle follow a simple hierarchical pattern called a chestnut. 1 Partially supported by Natural Science and Engineering Research Council of Canada, Discovery Grant #170493-03 An important tool in the study of both aspects is a reduction procedure, which might be of interest by itself. It allows elementary deterministic soliton graphs to be reduced to generalized trees, and it can also be used to reduce chestnut graphs to really straightforward ones, called baby chestnuts. 2 Soliton graphs and automata By a graph G = (V(G),E(G)) we mean an undirected graph with multiple edges and loops allowed. A vertex v e V(G) is called external if its degree is one, and internal if the degree of v is at least two. An internal vertex is base if it is adjacent to an external one. External edges are those of E(G) that are incident with at least one external vertex, and internal edges are those connecting two internal vertices. Graph G is called open if it has at least one external vertex. A walk in a graph is an alternating sequence of vertices and edges, which starts and ends with a vertex, and in which each edge is incident with the vertex immediately preceding it and the vertex immediately following it. The length of a walk is the number of occurrences of edges in it. A trail is a walk in which all edges are distinct and a path is a walk in which all vertices are distinct. A cycle is a trail which can be decomposed into a path and an edge connecting the endpoints of the path. If a = ve1... enw is a walk from v to w and 3 = wf1... fk z is a walk from w to z, then the concatenation of a and 3 is the walk a || 3 = vei... enwfi... fkz from v to z. A matching M of graph G is a subset of E(G) such that 282 Informatica 30 (2006) 281-288 M. Bartha et al. no vertex of G occurs more than once as an endpoint of some edge in M. It is understood by this definition that loops cannot participate in any matching. The endpoints of the edges contained in M are said to be covered by M. A perfect internal matching is a matching that covers all of the internal vertices. An edge e e E(G) is allowed (mandatory) if e is contained in some (respectively, all) perfect internal matching(s) of G. Forbidden edges are those that are not allowed. We shall also use the term constant edge to identify an edge that is either forbidden or mandatory. An open graph having a perfect internal matching is called a soliton graph. A soliton graph G is elementary if its allowed edges form a connected subgraph covering all the external vertices. Observe that if G is elementary, then it cannot contain a mandatory edge, unless G is a mandatory edge by itself with a number of loops incident with one of its endpoints. Let G be an elementary soliton graph, and define the relation ~ on Int(G) as follows: v1 ~ v2 if an extra edge e connecting v1 with v2 becomes forbidden in G + e. It is known, cf. [6, 2], that ~ is an equivalence relation, which determines the so called canonical partition of (the internal vertices of) G. The reader is referred to [6] for more information on canonical equivalence, and on matching theory in general. Let G be a graph and M be a matching of G. An edge e e E(G) is said to be M-positive (M-negative) if e e M (respectively, e e M). An M-alternating path (cycle) in G is a path (respectively, even-length cycle) stepping on M-positive and M-negative edges in an alternating fashion. An M-alternating loop is an odd-length cycle having the same alternating pattern of edges, except that exactly one vertex has two negative edges incident with it. Let us agree that, if the matching M is understood or irrelevant in a particular context, then it will not be explicitly indicated in these terms. An external alternating path is one that has an external endpoint. If both endpoints of the path are external, then it is called a crossing. An alternating path is positive if it is such at its internal endpoints, meaning that the edges incident with those endpoints are positive. Let G be a soliton graph, fixed for the rest of this section, and let M be a perfect internal matching of G. An M-alternating unit is either a crossing or an alternating cycle with respect to M. Switching on an alternating unit amounts to changing the sign of each edge along the unit. It is easy to see that the operation of switching on an M-alternating unit a creates a new perfect internal matching S(M, a) for G. Moreover, as it was proved in [1], every perfect internal matching M of G can be transformed into any other perfect internal matching M' by switching on a collection of pairwise disjoint alternating units. Consequently, an edge e of G is constant iff there is no alternating unit passing through e with respect to any perfect internal matching of G. A collection of pairwise disjoint M-alternating units will be called an M-alternating network, and the network transforming one perfect internal matching M into another M' will be denoted by N(M, M'). Clearly, a) c-trail A b) l-trail Figure 1: Soliton trails. N(M, M') is unique. Now we generalize the alternating property to trails and walks. An alternating trail is a trail a stepping on positive and negative edges in such a way that a is either a path, or it returns to itself only in the last step, traversing a negative edge. The trail a is a c-trail (l-trail) if it does return to itself, closing up an even-length (respectively, odd-length) cycle. That is, a = ai || a2, where ai is a path and a2 is a cycle. These two components of a are called the handle and circuit, in notation, h(a) and c(a). The joint vertex on h(a) and c(a) is called the center of a. An external alternating trail is one starting out from an external vertex, and a soliton trail is a proper external alternating trail, that is, either a c-trail or an l-trail. See Fig. 1. The collection of external alternating walks in G with respect to some perfect internal matching M, and the concept of switching on such walks are defined recursively as follows. (i) The walk a = v0ev1, where e = (vo, v1) with v0 being external, is an external M-alternating walk, and switching on a results in the set S(M, a) = MA{e}. (The operation A is symmetric difference of sets.) (ii) If a = v0e1... envn is an external M-alternating walk ending at an internal vertex vn, and en+1 = (vn,vn+1) is such that en+1 e S(M,a) iff en e S(M,a), then a' = aen+1vn+1 is an external M-alternating walk and S(M, a') = S(M, a)A{en+1}. It is required, however, that en+1 = en, unless en e S(M, a) is a loop. It is clear by the above definition that S(M, a) is a perfect internal matching iff the endpoint vn of a is external, too. In this case we say that a is a soliton walk. Example Consider the graph G of Fig. 2, and let M = {e, h1y h2}. A possible soliton walk from u to v with respect to M is a = uewgz1h1z2l2z3h2z4l1z1 gwfv. Switching on a then results in S(M, a) = {f, l1,l2}. Graph G gives rise to a soliton automaton AG, the states of which are the perfect internal matchings of G. The input alphabet for AG is the set of all (ordered) pairs of external vertices in G, and the state transition function S is defined DETERMINISTIC SOLITON GRAPHS Informatica 30 (2006) 281-288 283 Figure 2: Example soliton graph G by S(M, (v, w)) = {S(M, a) | a is a soliton walk, v to w}. Graph G is called deterministic if AG is such in the usual sense, that is, if for every state M and input (v, w), I6(M, (v, w))I < 1. Example (Continued) Observe that the soliton automaton defined by the graph of Fig. 2 is non-deterministic, as a' = uewfv is also a soliton walk from u to v with respect to state M such that S(M, a) = S(M, a'). Let a be a soliton c-trail with respect to M. It is easy to see that the walk s(a) = h(a) || c(a) || h(a)R is a soliton walk, and the effect of switching on s(a) is the same as switching on the cycle c(a) alone. (For any walk /3, /R denotes the reverse of /.) If a is a soliton l-trail, then s(a) is defined as the soliton walk s(a) = h(a) || c(a) || c(a) || h(a)R. Clearly, this walk induces a self-transition of AG, that is, no state change is observed. In the sequel, all perfect internal matchings of G will simply be called states for obvious reasons. Recall from [5] that an edge e of G is impervious if there is no soliton walk passing through e in any state of G. Edge e is viable if it is not impervious. See Fig. 2, edge h for an example of an impervious edge. We are going to give a simpler characterization of impervious edges in terms of alternating paths, rather than walks. To this end, we need the following lemma. Lemma 2.1. If a is an external M-alternating walk from v to u, then there exists an M-alternating network T and an external M-alternating trail 3 from v to u such that 1. r consists of cycles only, and it is disjoint from /3; 2. S(M, a) = S(S(M, T),/). Proof. Easy induction on the length of a, left to the reader. □ An internal vertex v e V(G) is called accessible with respect to state M if there exists a positive external M-alternating path leading to v. It is easy to see, cf. [2], that vertex v is accessible with respect to some state M iff v is accessible with respect to all states of G. Proposition 2.2. For every edge e e E(G), e is impervious iff both endpoints of e are inaccessible. Proof. If either endpoint of e is accessible, then e is clearly viable. Assume therefore that both endpoints ui and u2 of e are inaccessible, and let a be an arbitrary external M-alternating walk from v e Ext(G) to either u1 or u2, say u1. By Lemma 2.1, there exists a suitable external M-alternating trail 3 from v to ui . Each internal edge lying on 3 has an accessible endpoint, so that e is not among them. Moreover, the edge of h(/3) incident with u1 must be positive with respect to S(M, a), otherwise h(/3) would be a positive external alternating path with respect to state S(M, r). (Recall that h(/3) is the handle of /3, and take h(/3) = /3 if /3 is just a path.) But then e must be negative with respect to S(M, a), or else h(/)eu2 would be a positive external alternating path leading to u2 (with respect to S(M, r), or even M, since r is disjoint from /). We conclude that the walk a cannot continue on e, because it must take the two positive edges incident with u1 before and after hitting that vertex. Thus, every time an external alternating walk reaches either endpoint of e, it will miss e as a possible continuation. In other words, e is impervious. □ 3 Elementary decomposition of soliton graphs Again, let us fix a soliton graph G for the entire section. In general, the subgraph of G determined by its allowed edges has several connected components, which are called the elementary components of G. Notice that an elementary component can be as small as a single external vertex of G. Such elementary components are called degenerate, and they are the only exception from the general rule that each elementary component is an elementary graph. A mandatory elementary component is a single mandatory edge e e E(G), which might have a loop around one or both of its endpoints. The structure of elementary components in a soliton graph G has been analysed in [2]. To summarize the main results of this analysis, we first need to review some of the key concepts introduced in that paper. Elementary components are classified as external or internal, depending on whether or not they contain an external vertex. An elementary component of G is viable if it does not contain impervious allowed edges. A viable internal elementary component C is one-way if all external alternating paths (with respect to any state M) enter C in vertices belonging to the same canonical class of C. This unique class, as well as the vertices belonging to this class, are called principal. Furthermore, every external elementary component is considered a priori one-way (with no principal canonical class, 284 Informatica 30 (2006) 281-288 M. Bartha et al. Figure 3: Elementary components in a soliton graph of course). A viable elementary component is two-way if it is not one-way. An impervious elementary component is one that is not viable. Example The graph of Fig. 3 has five elementary components, among which C\ and D are external, while C2, C3 and C4 are internal. Component C3 is one-way with the canonical class {u, v} being principal, while C2 is two-way and C4 is impervious. Let C be an elementary component of G, and M be a state. An M-alternating C-ear is a negative M-alternating path or loop having its two endpoints, but no other vertices, in C. The endpoints of the ear will necessarily be in the same canonical class of C. We say that elementary component C' is two-way accessible from component C with respect to any (or all) state(s) M, in notation CpC', if C' is covered by an M-alternating C-ear. It is required, though, that if C is one-way and internal, then the endpoints of this ear not be in the principal canonical class of C. As it was shown in [2], the two-way accessible relationship is matching invariant. A family of elementary components in G is a block of the partition induced by the smallest equivalence relation containing p. A family F is called external if it contains an external elementary component, otherwise F is internal. A degenerate family is one that consists of a single degenerate external elementary component. Family F is viable if every elementary component in F is such, and F is impervious if it is not viable. As it turns out easily, the elementary components of an impervious family are all impervious. Soliton graph G is viable if all of its families are such. Example (Continued) Our example graph in Fig. 3 has four families: F\ = {C\1C2}1 F2 = {D}, F3 = {C3}, F4 = {C4}. Family F\ is external, F2 is degenerate, and F3 is internal. These families are all viable, whereas family F4 is impervious. The first group of results obtained in [2] on the structure of elementary components of G can now be stated as follows. Theorem 3.1. Each viable family of G contains a unique one-way elementary component, called the root of the family. Each vertex in every member of the family, except for the principal vertices of the root, is accessible. The principal vertices themselves are inaccessible, but all other vertices are only accessible through them. A family F is called near-external if each forbidden viable edge incident with any principal vertex of its root is external. For two distinct viable families F1 and F2, F2 is said to follow F1, in notation F1 — F2, if there exists an edge in G connecting any non-principal vertex in F1 with a principal vertex of the root of F2. The reflexive and transitive closure of — is denoted by —. The second group of results in [2] characterizes the edge connections between members inside one viable family, and those between two different families. Theorem 3.2. The following four statements hold for the families of G. 1. An edge e inside a viable family F is impervious iff both endpoints of e are in the principal canonical class of the root. Every forbidden edge e connecting two different elementary components in F is part of an ear to some member C e F. 2. For every edge e connecting a viable family F1 to any other family (viable or not) F2, at least one endpoint of e is principal in F1 or F2. If the endpoint of e in F1 is not principal, then F2 is viable and it follows Fi. 3 The relation — is a partial order between viable families, by which the external families are minimal elements. 4 If F and G are families such that F — G, then each non-principal vertex u of G is accessible from F, meaning that for every state M there exists a positive M-alternating path to u either from a suitable external vertex of F, if F is external, or from an arbitrary principal vertex of F, if F is internal. The path a runs entirely in the families between F and G according to * ——k For convenience, the inverse of the partial order — will be referred to as 1, where y is a cycle of even length and each a (i e [k]) is a tree subject to the following conditions: DETERMINISTIC SOLITON GRAPHS Informatica 30 (2006) 281-288 285 Figure 4: A chestnut. (i) V(ai) n V(aj) = 0 for 1 < i = j < k; (ii) V(ai) n V (7) consists of a unique vertex - denoted by vi - for each i e [k]; (iii) vi and Vj are at even distance on 7 for any distinct i,j e [k]; (iv) any vertex wi e V(ai) with d(wi) > 2 is at even distance from vi in ai for each i e [k]. See Fig. 4 for an example chestnut. Our first observation regarding chestnuts is that they are bipartite graphs. Let us call a vertex of a chestnut G outer if its distance from any of the vi's is even, and inner if this distance is odd. Then the inner and outer vertices indeed define a bipartition of G. Moreover, the degree of each inner vertex is at most 2. It is easy to come up with a perfect internal matching for G: just mark the cycle 7 in an alternating fashion, then the continuation is uniquely determined by the structure of the trees ai. Thus, G has exactly two states. It is also easy to see that the inner internal vertices are accessible, while the outer ones are inaccessible. Thus, the cycle 7 forms an internal elementary component with its outer vertices constituting the principal canonical class of this component. Moreover, 7 forms a stand-alone internal family in G. The rest of G's families are all single mandatory edges along the trees ai, or they are degenerate ones consisting of a single inner external vertex. Their rank in the partial order