THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Technical Report HOMOMORPHISMS OF GRAPHS Stephen Hedetniemi ORA Projects 03105 and 07363 supported by: U.S. ARMY RESEARCH OFFICE (DURHAM) GRANT NO. DA-ARO(D)-31-124-G665 DURHAM, NORTH CAROLINA and DEPARTMENT OF TH, NAVY QFFICE OF NAVAL. RBSEARCH CONUFACT NO..Nnr:.,124, (21) W:ASHINGTGON D. C. admin'imtere'd athIough: OFFICE OF RESEARCHi,.kiI3ST3RATION ANN ARBOR December 1965

RESEARCH PROGRESS REPORT Title: "Homomorphisms of Graphs," S. Hedetniemi, University of Michigan Technical Report Background: The Logic of Computers Group of the Communication Sciences Program of The University of Michigan is investigating the application of logic and mathematics to the design of computing automata. The use of graphtheoretical techniques in the study of automata forms a part of this investigation. Condensed Report Contents: The works of Hartmanis and Stearns, Krohn and Rhodes, Yoeli and Ginzburg, and Zeiger amply demonstrate the usefulness of homomorphisms in studying decompositions of finite automata. Yoeli and Ginzburg's approach is slightly different from the others in that it is more concerned with aspects of the state transition graphs of finite automata. In their paper, "On Homomorphic Images of Transition Graphs," they give a complete characterization,of the class of homomorphisms of the graphs which correspond to input-free automata. This paper was motivated by an interest in extending these results of Yoeli and Ginzburg in the direction of a characterization of the class of homomorphisms of graphs which correspond to arbitrary finite automata. It is a review and a classification of most of the published definitions and results on mappings of graphs which have been called homomorphisms. The paper contains, in addition, several new results and several new definitions of homomorphisms of graphs. For Further Information: The complete report is available in the major Navy technical libraries and can be obtained from the Defense Documentation Center. A few copies are available for distribution by the author.

PREFACE The works of Hlartmanis and Steams [10], Krohn and Rhodes [12], Yoeli and Ginzburg [22], and Zeiger [24] amply demonstrate the usefulness of homomorphisms in studying decompositions of finite automata. Yoeli and Ginzburg's approach is slightly different from the others in that it is more concerned with aspects of the state transition graphs of finite automata. In their paper, "On Homomorphic Images of Transition Graphs" [22], they give a complete characterization of the class of homomorphisms of the graphs which correspond to input-free automata. This paper was motivated by an interest in extending these results of Yoeli and Ginzburg in the direction of a characterization of the class of homomorphisms of graphs which correspond to arbitrary finite automata. It is a review and a classification of most of the published definitions and results on mappings of graphs which have been called homomorphisms. The paper contains, in addition, several new results and several new definitions of homomorphisms of graphs, which are found primarily in Sections 1.3 - 1.6, 1.8, and 1.9. v

The mappings of graphs which are defined in this paper are divided into three classes; Homomorphisms, Contractions, and Relational Homomorphisms. The distinction between the first two classes, while not very important, is a very natural one to make, and can best be understood after the class of Homomorphisms has been defined and studied in Section 1. It is for this reason that the discussion of this distinction is postponed until Section 2, where Contractions are defined and examined. It is likely that there are definitions and results on mappings of graphs which have recently been published but which are not referenced here. The author would welcome any information concerning such omissions. For the reader not well versed in the terminology of graph theory, terms which are undefined in the text are defined in the Appendix. Proofs of statements which are quite easily constructed have, in many instances, been omitted, it is hoped without any loss of content or continuity. The author is especially indebted to Professor Frank Harary, of the Mathematics Department, and to Yehoshafat Give'on, of the Logic of vi

Computers Group, for their many critical comments, suggestions, and sharp reading of the manuscript, which greatly improved the organization and presentation of definitions, results, and proofs. vii

TABLE OF CONTENTS PREFACE v NOTATION xi 1. HOMOMORPHISMS 1.1 General Definitions. *.*.*.*..*.**... 1 1.2 Properties Preserved Under Homomorphisms...... 3 1.3 Complete Homomorphisms............... 4 1.4 Type-n Homomorphisms............ 13 1.5 Two Invariants of a Graph......... 15 1.6 Endomorphism-free Graphs.............. 24 1.7 Homomorphisms for Functional Digraphs....... 25 1.8 Pathwise Homomorphisms........... 28 1.9 Strong Homomorphisms. 31 2. CONTRACTIONS 2.1 General Definition................ 38 2.2 Connected and Indenendent Contractions.... 40 2.3 Simplicial Mappings................ 41 2.4 Homeomorphisms................ 43 2.5 Strong Contractions........ 45 3. RELATIONAL HOMOMORPHISMS 3.1 General Definition........... 47 3.2 Weak Homomorphisms.............. 48 3.3 Weak Isomorphisms.................. 51 SUMMARY AND SUGGESTED PROBLEMS.................. 60 APPENDIX OF DEFINITIONS.................. 68 BIBLIOGRAPHY..,,,......,,,,,,.,, a. 71 ix

NOTATION Of a graph G = <V,p>: V or V(G) denotes the set of points of G; p denotes the adjacency relation of G, p-c VxV; p(a,b) or (a,b) means there is a line from point a to point b in G; p(a,b) means there is no line from point a to point b in G; p(a) = {b: (a,b)cp}; p (b) = {a: (a,b)ep}; n(a) = p(aJp l(a); X(G) denotes the chromatic number of G. K denotes the complete graph on the n points, k, k..., k. P denotes a cycle; Pn, a cycle of length n with points p1, P2,..., Pn C denotes a chain; Cn, a chain of length n with points cl, c2,..., cn+l. xi

1. HOMOMIORPHISMS 1.1. General Definitions. A graph G = <V,p> is a relational system whose set is the finite set V of points of G and whose set of relations consists of one binary relation pcVxV, the adjacency relation. A graph G' = <V',p is a subgraph of G, written G' c G, iff V' C V and p' c p; G' is a full subgraph of G iff for every a,bEV', (a,b)p (a,b)ep'.1 Let o be a function from V into V', and define the extension c: VxV -- V'xV', by (a,b)4 = (ab,bo). If 4 satisfies the condition (1) p4 c p', or equivalently, (a,b)ep - a= (a(,bb)ep', then ( is a homomorphism of G into G'. If ~ also satisfies the condition (2) (a4,b)~cp' c= (3c)(-d)[c4 = a/ A do = b/'n (c,d)ep], then 4 is a full homomorphism of G into G'. From the definition of homomorphism it follows that the product of homomorphisms is itself a homomorphism, i.e., if G, G', and are raphs and G are gras and 1Subgraphs and full subgraphs correspond in Ore's terminology to subpraphs and section graphs, and in Berge's terminology to partial subgraphs and subgraphs, respectively. -1

: G' --- G" are homomorphisms, then the product mapping #, for which a# = (ao)* and (a,b)4 = ((a,b)O)i = (ao,b)ip = ((a*)),(b9)') = (a<,b(), is a homomorphism of G into G". It follows also from (1) that if Go = <V,Po)> is the image of G under the homomorphism 0 then Go is a subgraph of G', and if * is a full homomorphism then Go is a full subgraph of G'. If, in addition, < maps V onto V' then 0 is said to be a (full) homomorphism of G onto G'. Note that if - is a full homomorphism of G onto G' then po = p'. In the case G' c G and 4 is a (full) homomorphism of G into G', * is said to be a (full) endomorphism of G; when Go = G' = G, * is an automorphism of G. A full homomorphism * of a graph C onto a graph G' is an isomorphism when O is 1-1 from V onto V', in which case G and G' are said to be isomorphic, written G C G'. Figure 1 illustrates some of these definitions. The homomorphisms <1 and 03 are full endomorphisms of G onto the full subgraphs G1 and G3, respectively. The endomorphism *2 is not full, since G2 is not a full subgraph of G. Note that G2 and G3 are isomorphic. Note also that -2

c.. e a o e c e d f bo f d ~ d *1 G2 G G G.....2 — 2 $3 G3 ao c b o d *!: add d 2 a- d a: ada b,c - c b -- c b - b c- e c,e - e c,e -- c f -- f d,f -- f d,f -- d FIG. 1. GOi11 = GO1 and Go3<3 = GO3, but G<2<2 # G2'. 1,2. Properties Preserved under Homomorphisms. H. J. Keisler has written a paper [11] which is concerned essentially with a logical formulation of the properties of a relational system which are preserved under two classes of homomorphisms, which he -3

calls "strong homomorphisms" and "retracts". Using our terminology for graphs, these "strong homomorphisms" are full homomorphisms for which the function is onto, and "retracts" are endomorphisms which act as the identity mapping on the image, i.e., Go = G' is a subgraph of G and b4 = b for every beV'. It follows from this definition that "retracts" are those endomorphisms which are idempotent, i.e., for which G~2 = GO. Two theorems are stated in the paper, one for each class of mappings, to the effect that a property of a relational system is preserved if and only if it is logically equivalent to a sentence of a particular form in the first order predicate calculus with identity. Although these results obviously can be applied to homomorphisms of graphs, they have not been as yet. 1.3. Complete Homomorphisms. An ordinary graph is a graph whose adjacency relation is symmetric and irreflexive; stated in other words, a graph is ordinary if it is undirected and has no loops or multi-lines. In this section, and in Sections 1.4, 1.5, 1Later in the paper, Section 1.9, we will define a different class of mappings and call them strong homomorphisms. -4

and 1.6, we will consider only full homomorphisms of ordinary graphs onto ordinary graphs; these mappings 4 must satisfy the condition (3) a) = b => (a,b)ip, and we will call them ordinary homomorphisms. We will, however, omit the word "ordinary" when referring to graphs and homomorphisms in these four sections. A homomorphism of a graph G onto a graph G' is called complete iff G' = Kn, for some n, A complete homomorphism of a graph G onto K is said to be of order n. A coloring of a graph G is an assignment of colors to the points of G such that no two adjacent points are assigned the same color. More formally, an n-coloring of a graph G = <V,p> is a function n from V onto N, where N is the set of natural numbers (colors) {1, 2,..., n}, satisfying the condition that (a,b)ep -= an # bn. An n-coloring n is complete iff for every i,j, i j, (3a) (-b)[an = i / bn = j / (a,b) p]. The chromatic number of a graph G is the smallest number n such that G has an n-coloring. 1Full homomorphisms satisfying this condition are called independent by Ore, cf. Section 2.2. -5

Theorem 1.3.1. If n: V — N is a (complete) n-coloring of graph G = <Vp>, then n determines a (complete) homomorphism 4n of G onto Kn, and conversely. Proof. If an = i, let an = ki * The next eight corollaries follow more or less directly from this theorem; the proofs of these corollaries are quite simple and are omitted. Corollary 1.3.2. (Ore) If the chromatic number of a graph G is n, then G has a complete homomorphism of order n. While this corollary defines the order of a particular complete homomorphism that every graph must have, a given graph may have several other complete homomorphisms of different orders. Figure 2 illustrates this possibility; the graph G has complete homomorphisms of orders 2, 3, and 4. Corollary 1.3.3. (Prins) The smallest number s for which a given graph G has a complete homomorphism of order s is the chromatic number of G. Corollary 1.3.4. If i is a homomorphism of a graph G, then X(G)' X(GO). 1In a manuscript, "Complete Contractions of Graphs," dated February 1963, Prins refers to these mappings as complete contractions. -6

b k 1 —- k2 a o — 1C k4 d - o e k k3 22 4 fi av ac ka,.eK 2k2 2 K b,e,f —— 4k2 2 3 /" \ k~ k of points of G, then X(G) < 1 + X(G-S). Corollary 1.3.6. (Dirac) If G is a critical graph and S is c.f. Dirac [4]. -7

any independent set of points of G, then x(G) = 1 + x(G-S). Corollary 1.3.7. If G is any graph having n points and point independence number ao, then x(G) < 1 + n - aO. It is interesting to note in passing the relationship of this result to the result stated in Berge [2, p. 37] and Ore [16, p. 225] which asserts that n/a0 S X(G). A graph G is simple iff every homomorphic image of G is isomorphic to G. Corollary 1.3.8. A graph G is simple iff G = K, for some n. A homomorphism e of a graph G is elementary iff for two points a,beV(G), ae = be and e is 1-1 on V(G) - {a,b}. Lemma 1.3.9. Every ordinary homomorphism of a graph G onto a graph G' can be expressed as a product of elementary homomorphisms. As an immediate consequence of Corollary 1.3.5. we have Corollary 1.3.10. The chromatic number of an elementary homo1Simple with respect to ordinary homomorphisms. -8

morphic image of G is at most one greater than the chromatic number of G. And because of Corollary 1.3.6 we have Corollary 1.3.11. Every elementary homomorphic image of a critical graph G has the same chromatic number as G. Theorem 1.3.12. (Prins) If the chromatic number of a graph G is s, and G has a complete homomorphism of order t, then for all n, a X n < t, G has a complete homomorphism of order n. Proof. The theorem follows directly from Lemma 1.3.9 and Corollary 1.3.10. Consider any homomorphism ( which maps G onto Kt. By Lemma 1.3.9, can be expressed as a product cec2.. em of elementary homomorphisms. Let G1 = G1,, G2 = G1~2' *** G G m m =m- Kt By Corollary 1.3.10 we know that the chromatic number of Gi is at most one greater than the chromatic number of Gi _1 It follows therefore that if X(G) = s and s 4 n < t, then there exists at least one G. whose chromatic number is n. By Corollary 1.3.2, this G. has a complete homomorphism ci onto K. Hence G has a complete homomorphism ce2.' e.i. c onto K.H! n 12 11 n Prins, in considering complete homomorphisms, made an interesting -9

distinction between two types. Type complete homomorphisms of a graph G are obtained in the following manner. Take any maximal independent set of points V1 in V(G). Remove the points in V1 from G and take a second maximal independent set of points V2 in V(G-V1). Iterate this process until V(C) has been completely depleted, and has been partitioned into sets V1, V2,..., Vm. This partition defines a complete homomorphism ~ of G onto K; ao = k. iff acV.. If a complete homomorphism is not of type-l it is said to be of type-2. Prins has shown that the homomorphisms stated in Corollary 1.3.2 and Theorem 1.3.12 can be required to be of type-1, i.e., if the chromatic number of G is s and if G has a type-1 complete homomorphism of order t, then for every n, s < n < t, G has a type-1 complete homomorphism of order n. Prins has attempted to characterize the type-2 complete homomorphisms, but has not yet succeeded. While Corollary 1.3.3 establishes the minimum order s, it remains an open question to determine a decent description of the maximum order t of all complete homomorphisms of a given graph G. The following result, which -10

extends Corollary 2.3.?, establishes a bound for this number t. Theorem 1.3.1.3 Let G be a graph having n points and point independence number ao' and let t be the largest order of all complete homomorphisms of G. Then x(G) < t < n + 1 - a0. Proof. Let ) be a complete homomorphism of G onto Kt, where t is maximum, and consider the partition of V(G) determined by the sets (ki), i = 1, 2,..., t. Let V1 be any maximal independent set of G containing ao points, and consider where among the sets 4 (k.) the points in V1 lie. Three possibilities exists; 4) (ki) contains no points of V, vl (ki) contains some points of V1 and some points of V-V1, or 4 (ki) contains only points of V1. Note, however, that at most one set 4 (ki) can contain only members of V1. It follows therefore that we can pick representatives from at least t-l of these sets which are not members of Vi and therefore the total number of points in G minus these t-l representatives leaves at least the a points of V1 remaining. Thus n - (t-l) > ac n + 1 - a > t. -11

Corollary 1.3.14. t < Bo(G) + 1, where Bo(G) is the point cover number of G. Proof. This follows since n = a0(G) + Bo(G). I Perhaps the most natural bound for the largest order t of all complete homomorphisms of a given graph G, having q lines, is the largest integer r such that 2 q' As one might expect, however, there are cases in which each of the two bounds, r and n+l-ao, gives a better estimate than the other, as the examples in Figure 3 illustrate. G1: o —-- G2: --- 0 0 - FIG. 3. In G1, n = 9, q = 8, and ao = 8, hence r = 4, n+l-ao = 2, while t = 2. cf. Gallai [7]. -12

If G2, n = 10, q = 9, and ao = 5, hence r = 4, n+l-aO = 6, while t = 4. 1.4. Type-n Homomorphisms. An n-basis of a graph G = <V,p> is a subset of points, Vn C V, satisfying (i) a,beVn - - d(a,b) > n; (ii) cVn - d(c,Vn) < n. A Prins' type-1 complete homomorphism (cf. Section 1.3) can be described in terms of an iterated subtraction from a graph of maximal independent sets of points. Since from the definition of an n-basis it follows that maximal independent sets of points are 1-bases, the suggestion naturally arises of considering complete homomorphisms of type-n mappings which can be described in terms of an iterated subtraction from a graph of n-bases. Even though the process of obtaining a series of n-bases from a given graph does not always define a complete homomorphism, the fact that some complete homomorphisms which are not of Prins' type-l can be expressed -13

as complete homomorphisms of type-n seems to justify the following definition. A full homomorphism ( of a graph G = <V,p> onto a graph G' =<',p is of type-n iff there exists an ordering of the sets % (a'), for a'EV', say V1, V2, *.., Vk' such that (i) V1 is an n-basis of C, and i-l (ii) for i > 2, Vi is an n-basis of G - U Vj, ~~~~1 ~j=l and for no m, 0 < m < n, is % of type-m. Note that not every complete homomorphism is of type-n, for some n. An example of this is the complete homomorphism given in Figure 4; neither of the sets {a,d}, {c,e} or {b,f} is an n-basis of G, for any n. c kl: a,d -- k j~d b b,f — k ce - k2 -0 ~ kc2 k3 a b e f G 3- K3 FIG. 4. -14

If a complete homomorphism is not of type-n for any n, it is said to be of type-e. An example of a type-4 complete homomorphism is given in Figure 5; the subset {e,j} is a 4-basis of G; {c,i,l} is a 4-basis of G - {e,j}; {b,d,g} is a 4-basis of G - {e,j} - {c,i,-l}; and what remains in G - {e,j} - {c,il} - {b,dg} are the three isolated points a, f, and h.: a,f,h k g i b,d,g -k2 h c,i,l - k3 f od d k4 ej -- k4 o o — k2 k k3 2 3 a b c G K FIG. 5. 1.5. Two Invariants of a Graph. Two interesting invariants of a graph arise out of considerations of the following question: Given a graph G, for what graphs H do there exist -15

homomorphisms * such that H( = G? A partial answer to this question is given by the following three propositions. Proposition 1.5.1. For every connected graph G there exists a tree T and a homomorphism * such that To = G. Proposition 1.5.2. For every connected graph G there exists a chain C and a homomorphism * such that C- = G. Proposition 1.5.3. For every connected graph G there exists a cycle P and a homomorphism * such that Po = G. It is natural in view of these last two propositions to make the following definitions. The chain length of a connected graph G, ch(G), is the smallest number k for which there exists a chain C of length k and a homomorphism 0 such that Co = G. Alternatively, ch(G) is the length of the shortest path which contains all the lines of G.' The cycle length of a connected graph G, cy(G), is the smallest number k for which there exists a cycle P of length k and a homomorphism * such that P( = G. -16

Proposition 1.5.4. For every connected graph G, ch(G) < cy(G) < 2ch(G). Proof. Clearly ch(G) < cy(C), for if al, a2,..., ak, al is any cycle P of length k which maps onto G under a homomorphism <, then a chain a', a.., a b can be defined of the same length k which maps onto G under the homomorphism (' for which a!i' = ai. and bp' = al. To show that y(G) < 2ch(G), let Ck with points cl, c2,..., k, ck+l, be the shortest chain which maps under a homomorphism t onto G. Then a cycle c2, c+,..., +1' dk - dk2'', c of length 2k can be defined which maps under the homomorphism P' onto G, where c!'' = c.i and d.i' = c.i. I The bounds given in Proposition 1.5.4 are achieved in the following two cases; ch(Pn) = cy(Pn) = n, and cy(Cn) = 2ch(C ) = 2n. Proposition 1.5.5. For every connected graph G with q tines, (i) q < ch(G) < 2q-1. (ii) q < cy(G) < 2q. Proof. (i) It is obvious that q < ch(G), since the shortest chain which maps onto G must have at least as many lines as C. -17

That ch(G) l 2q is an immediate consequence of the following theorem, quoted from Ore [16, p. 41]: "Theorem 3.1.4. In a finite connected graph it is always possible to construct a cyclic directed path passing through each edge once and only once in each direction." (ii) The same arguments hold for cy(G). Proposition 1.5.6. If G is a connected graph having q lines and in which every point has even degree, then ch(G) = cy(G) = q. Proof. G is an Euler graph, i.e., a graph in which it is possible to find a cyclic path of lines such that each line in the graph appears once and only once. Theorem 1.5.7. If G is a connected graph having q lines and exactly two points a,b of odd degree, then (i) ch(G) = q; (ii) cy(G) = q + d(a,b). Proof. (i) See Ore [16, p. 40]. Such a graph has at least one path which passes through all the lines of G once and only once, which begins -18

with point b and ends with point a. Hence, ch(G) = q. (ii) Clearly, cy(G) I q + d(a,b). A path corresponding to the one referred to in (i) above can obviously be extended to a cycle by an additional path, of length d(a,b), from point a back to point b. In order to show that cy(G) ~ q + d(a,b), let Pk with points pl, P2, ***, Pk be the smallest cycle which maps onto G under the homomorphism Ok, and let Pn be a cycle of length n = q + d(a,b) which maps onto G under the homomorphism.On Obviously, k < n. Consider the multi-graph Gk generated by Pk and the homomorphism k', i.e., V(Gk) = V(G), and there are as many lines between two points c,d in Gk as there are pairs of adjacent points Pi, pi in Pk such that either Pi.k = c and Pj.k = d, or Pi k = d and Pjok = c. It follows that Gk has k lines. The degree of a point c in Gk equals the sum of the degrees of the points Pi for which Pi.k = c. Since every point Pi has even degree in Pk' every point c has even degree in Gk. Consider also the multi-graph Gn generated by P and the homomorphism Gn; Gn has n lines. Clearly for every line (c,d) in G there is a line (c,d) in Gk and a line (c,d) in Gn. Hence, let us remove for each of the q lines -19

in G a corresponding line in both Gk and Gn. Denote the resulting graphs by Gk-G and Gn-G, which have k-q and n-q = d(a,b) lines, respectively, where k-q s d(a,b). Since the points a,b have even degree in Gk and odd degree in G, they have odd degree in Gk-G. And since they are the only two points of odd degree in G, they are the only two points of odd degree in Gk-G. It follows, therefore, by Theorem 2.2.2, Ore [16, p. 24], that since a,b are the only points of odd degree in Gk-G, a and b are connected in Gk-G. Hence Gk-G has at least d(a,b) lines, i.e., k-q > d(a,b). Hence k-q = d(a,b), i.e., k = q + d(a,b). Theorem 1.5.8. If G is a connected graph having q lines and 2n points of odd degree, n > 2, and diameter 6, then (i) q + n-1 < ch(G) < q + (n-1)6; (ii) q + n - cy(G) < q + n6. Proof. (i) That ch(G) < q + (n-l)6 follows by virtue of Theorem 3.1.2, Ore [16, p. 40]. Such a graph G has a set of n line disjoint paths which contain all the lines of G once and only once. Let W1, W2,..., Wn represent these n paths. A path which starts with the first -20

point of W1, which ends with the last point of Wn, and which connects the last point of Wi with the first point of Wi+l by a path of the length less than or equal to the diameter 6 can always be constructed in G. Such a path clearly has length less than or equal to q + (n-l)6. It is a simple matter to construct a chain of the same length which maps onto this path. In order to demonstrate that q + n-l < ch(G), let ch(G) = k, let Ck with points ci, c2, **., Ck+1 be a chain of length k, and let k be a homomorphism which maps Ck onto G. Let Gk be the multigraph generated by Ck and the homomorphism k' as in the proof of Theorem 1.5.7. Since only points cl and ck+l have odd degrees in Ck, at most two points have odd degrees in Gk. Obviously, Gk can be obtained from G by inserting additional lines between various pairs of adjacent points in V(G). The fewest number of additional lines which could possibly convert G, with 2n points of odd degree, into the multi-graph Gk, with at most two points of odd degree, is (2n-2)/2 = n - 1. This can be accomplished (if possible) by leaving two points of odd degree in G untouched by the addition of new lines, and by pairing-off the remaining 2n-2 points of odd degree into adjacent pairs -21

and adding a new line between each pair, i.e., by adding n-l new lines. (ii) The proof for cy(G) is very similar to that for ch(G) and is omitted. | It is interesting to compare the upper bounds given in Proposition 1.5.5, ch(G) < 2q - 1, and in Theorem 1.5.8, ch(G) < q + (n-l)6. There are cases in which each of the two bounds gives a better estimate than the other, as the examples in Figure 6 illustrate. LJ <1:~ G2:. FIG. 6. In G1, q = 5, 6 = 3, and n = 3, i.e., G1 has 2n = 6 points of odd degree; hence 2q - 1 = 9, while q + (n-l)6 = 11. Note that ch(G1) = 7. In G2, q = 7, 6 = 2, and n = 2; hence 2q - 1 = 13, while q + (n-l)6 = 9. Note that ch(G2) " 8. The examples in Figure 7 illustrate that the bounds given in Theorem 1.5.8 can be achieved. 22

I G3: o, o G: o: FIG. 7. In G3, q = 3, 6 = 2, and n = 2; hence q + n-l = 4 = ch(G3). In G4, q = 4, 5 = 2, and n = 2; hence q + (n-l)6 = 6 = ch(G4), and q + n6 = 8 = cy(G4). In G5. q = 6, 6 = 3, and n = 3; hence q + n = 9 = cy(G5). Corollary 1.5.9. (i) ch(K2 = + n-1;'Jn 2 (ii) ch(K2n+1 =y 2(K2+); (iii) cy(iK2n) = + n, Proof. (i) and (iii) follow at once from Theorem 1.5.8 and the observation that 6(Kn) = 1, for all n > 2. (ii) follows from Proposition 1.5.6 since every K2n+l is an Euler graph. Lemma 1.5.10. Let ~ be a homomorphism of a connected graph G onto a graph G'. Then (i) ch(G) > ch(G'); (ii) cy(G) > cy (G'). -23

Proof. (i) Let ch(G) = k, and k be a homomorphism which maps Ck onto G. Obviously, the product mapping *k, is a mapping of Ck onto G': Ok 0 Ck -- >G --- G'. Hence ch(G') < k = ch(G). (ii) A similar argument also holds for cy(G). 1.6. Endomorphism-free Graphs. A graph G is endomorphism-free iff every endomorphic image of G is isomorphic to G. Theorem 1.6.1. If k is an endomorphism of a graph G, then the chromatic number of GO equals the chromatic number of G. Proof. Obviously, x(GO) < X(G). But by Corollary 1.3.4, X(G) < x(G)). Corollary 1.6.2. Every critical graph is endomorphism-free. Inspection of all the graphs with six or fewer points shows that the converse to this corollary is true for these graphs. Proposition 1.6.3. If a graph has at most six points and is endomorphism-free, then it is critical. The graph in Figure 8, which is endomorphism-free and not critical, -24

shows that the converse does not hold for all graphs. But Figure 8 has eight points, leaving the problem of whether there exists a seven point counter-example. FIG. 8. 1.7. Homomorphisms for Functional Digraphs. A functional digraph G = <V,p> is a graph whose adjacency relation p is a function from V into V; in other words, the adjacency relation is not necessarily symmetric and the out degree of every point equals one. In this section we will consider only full homomorphisms of functional digraphs onto functional digraphs; these mappings $ must satisfy the condition (4) aS = b => p(a)4 = p(b)$. A homomorphism 4 is prime iff in every expression of < as a product $1)2, either $1 or $2 is an isomorphism. -25

Yoeli and Ginzburg [22] have given a complete characterization of this class of homomorphisms, which states that every such homomorphism (other than an isomorphism) can be expressed as a product over the following three types of prime homomorphisms: (i) W a is a homomorphism which maps a cycle P of length k onto a cycle P' of length k/p, where p is a prime divisor of k; for acV(P), (p (a))a = ( (a))a iff i - j (mod k/p); (ii) <$ is a homomorphism which identifies exactly two points ab, aSt = big, for which p(a) = p(b); (iii) Al is a homomorphism which identifies two cycles P and P' Y of the same length k, where for arbitrary acP, a'eP', (p (a)) n = (0 ))y n, 1, 2,..., k-1. Figures 9 - 11, with mappings marked pa, c6' and $y, illustrate respectively the three types of prime homomorphisms. It is interesting to note that Yoeli and Ginzburg have incorporated the two conditions (1) and (2),for a full homomorphism,into the one condition (5) p' =$ p0. Conditions (1) and (2) and condition (5) are clearly equivalent. 2yoeli and Ginzburg call these elementary homomorphisms. -26

a2 ^__^ a^ b2 a a 4a1 2a a625 a a1 ^ v a4 bl b a2 a5 a b2 -1 3 _.7 a3',a6 3 a6 a5 P - a > p1 FIG. 9. Figure 9 illustrates as well that Lemma 1.3.9 does not hold for homomorphisms of functional digraphs; i.e., the homomorphism q in Figure 9 cannot be represented as a product of elementary homomorphisms. a1 _ al'dl -a 2 /o 1b ~ b,b I a 2 b2 b2 1 2 d, c 1- c2 G! f —- G2 FIG. 10. a2 b2 C2 \y al\bl1 -- c1 a2,b2 -* c2 a1 3 3 1 a3'b3 1 C3 ~~~~~G c 1 G2 FIG. 11. -27

Yoeli and Ginzburg also show that provided G is a connected functional digraph, every series of prime homomorphisms of G onto G' has the same length. 1.8..Pathwise Homomorphisms, An ordinary homomorphism * of a graph G = <V,p> onto a graph Gt <V'p'> is a pathwise homomorphism iff it satisfies the following condition (6) for every path a! a', a! in G' there exists a path 1 2 n 1 2 n Note the similarity of condition (6) to condition (2), when the latter is rephrased as follows: (2') for every path a',b' of length one in G' there exists a path a,b in G such that aO a a' and b% = b'. Pathwise homomorphisms were first defined by Robert McNaughton [14] for state transition graphs. The only result he obtained about these mappings was that the "order" of a pathwise homomorphic image G' of a state transition graph G cannot be greater than the "order" of G. The "order" of a state -28

transition graph G will not be defined here; suffice it to say that it is a measure of the cyclic complexity of G. A notion similar to "order", which is frequently mentioned in graph theory, is what Ore [16, p. 67] calls circuit rank, y(G), the number of independent cycles. For any graph G with p points, q lines, and k connected components, y(G) = q - p + k. It is natural therefore to state the following Theorem 1.8.1. If is a pathwise homomorphism of a graph = (V <Vp> onto a graph G' = <V',p'>, then y(G) > y(G'). Proof. We proceed by induction on the circuit rank of G. Lemma 1.8.2. If 4 is a pathwise homomorphism of a graph G =<Vp> onto a graph G' = <V',p'> and y(G) = 0, then y(G') = 0 also. Proof. Suppose y(G') > 1, i.e., G' contains at least one cycle Pk of length k > 3. Suppose G has p points. Certainly there exists a path a! a!, * a, a! (perhaps several times) around Pk of length p, with 1 12 p+l k p+l points. Since * is a pathwise homomorphism there must exist a path a.i ai.,.., ai. in G such that a. a = a. Any such path in G has 11 12'pl p+l points and therefore must contain at least one point which occurs twice. -29

Such a path therefore must have a sub-path of the form w = a, ai,..., ai, a. 1] "k But since y(G) = 0, G has no cycles and every path in G of the form w must be such that a. = a., and similarly a. = a., etc., until finally 1. 1 1 1k k j+1 k-1 the sub-path of the form X must contain a sub-path either of the form a.ia or a.a.a.. But it cannot contain a sub-path of the form aiai since every two consecutive points of the corresponding path in G, are distinct. Also, it cannot contain a sub-path of the form a.a.a. since every three consecutive points of the corresponding path in C' are mutually distinct. Hence no path can exist in G which maps onto the path of length p in G' around the cycle Pk, Hence' cannot be a pathwise homomorphism, contrary to hypothesis. The graph G' must therefore contain no cycles, hence y(G') = 0. Continuing with the proof of Theorem 1.8.1, assume it is true for all G, with y(G) = n. We will show that it is also true for G with y(G) = n + 1. Consider the sets of lines of G defined by' ((a',b')), for all (a',b')ep'. Since y(G) = n + 1 > 1, there must be a set' ((a',b')) such that y(G -' ((a',b'))) < y(G). It can be shown then that' is a pathwise homomorphism of G -'P ((a',b')) -30

onto G' - (a',b'), and hence, by hypothesis y(G - ) ((a',b'))) > y(G' - (a',b')). But since y(G) > y(G - 4 ((a',b')) +1 and y(G' - (a',b')) + 1 2 y(G'), it follows that y(G) > y(G'). || It is interesting to note that no analog of Corollary 1.3.2 holds for pathwise homomorphisms. For example, the pentagon P5, has no nontrivial pathwise homomorphisms; X(P5) = 3, yet P5 does not map under any pathwise homomorphism onto K., It remains an open question to determine those graphs which are simple with respect to pathwise homomorphisms. One might also note in passing that Lemma 1.3.9 does not hold for pathwise homomorphisms. The mapping, in Figure 8, is a pathwise homomorphism which cannot be expressed as a product of elementary pathwise homomorphisms. 1.9. Strong Homomorphisms. Let g be the characteristic function of the adjacency relation of a graph G = <V,p>, i.e., g(a,b) = 1 iff (a,b)ep and g(a,b) = 0 iff (a,b)ip. -31

A full homomorphism 4 of a graph G onto a graph G' is a strong homomorphism iff 4 satisfies the condition (7) g(a,b) = g'(ao,bo). Condition (7) can also be expressed as.(7') (a,b)ep == (aO,bO)cp' (a,b) ip (ao,b)fpl'. In words, condition (7) requires not only that two adjacent points in G map to two adjacent points in G', but also that two non-adjacent points in G map to two non-adjacent points in G'. Theorem 1.9.1. If, is a strong homomorphism of a graph G = <Vp onto a graph G' = <V', then there exists a subgraph H of G such that H = G'. Proof. Consider the inverse-image sets 4 (a'), for a'cV'. Pick, arbitrarily, a set of representatives, VH, one point from each of these sets, and consider the full subgraph H = <VHH> of G generated by this set of representatives. The strong homomorphism 4 when restricted to H is an isomorphism of H onto G'. -32 -

Corollary 1.9.2. If < is a strong ordinary homomorphism of a graph G onto a graph G', then the chromatic number of G equals the chromatic number of G'. Strong homomorphisms were first studied by Culik [3], who gave the following characterization of those graphs which have no non-trivial strong homomorphisms. Theorem 1.9.3. (Culik) A graph G is simple with respect to strong homomorphisms iff for every two distinct points a,beV(G) there exists a point ceV(G) such that g(ac) P g(b,c) or g(c,a) # g(cb). Consider the equivalence relation = defined on V(G) by a = b iff (Vc)[g(a,c) = g(b,c) ^ g(c,a) = g(c,b)], or alternatively, a = b iff [p(a) = p(b) and p (a) = p (b)]. Lemma 1.9.4. If 0 is a strong homomorphism of a graph G onto a graph G', then a+ = bo * a = b. Lemma 1.9.5. Given a graph G = Kip> and two points abeV for which a - b, a mapping * which identifies a and b (a0 = b~) and which is -33

1-1 on V - {a,b} determines an elementary strong homomorphism of G. Theorem 1.9.6. Every strong homomorphism of a graph G onto a graph G' can be expressed as a product of elementary strong homomorphisms. Proof. This is a consequence of Lemmas 1.9.4 and 1.9.5. Theorem 1.9.7. (Culik) Any given graph G has exactly one strong homomorphism ps onto a graph G, such that G is simple. Proof. From Theorem 1.9.3, and Lemmas 1.9.4 and 1.9.5, a graph G is simple iff the equivalence relation - on V(G) is the identity relation. The strong homomorphism s is that mapping for which ap = b4 iff a - b. Corollary 1.9.9. (Sabidussi) Either G e Gs or G contains a subgraph H such that H ^ G. Lemma 1.9.4 and the definition of the equivalence relation = suggest that one define the following two, slightly broader classes of homomorphisms. A full homomorphism 4 of a graph G onto a graph G' is a right homomorphism iff > satisfies the condition (8) aO = b - o p(a) = p(b), 1Simple with respect to strong homomorphisms. 2Theorem 1.9.1 was suggested by this result of Sabidussi [18, 19]. -34

A full homomorphism 0 of a graph G onto a graph G' is a left homomorphism iff * satisfies the condition (9) ao = b => p (a) = p (b). Right homomorphisms appear to be of special interest in view of their relation to homomorphisms of finite automata, where for a given automaton two states a and b are said to be equivalent iff they satisfy a condition exactly parallel to condition (8).1 Note that conditions (8) and (9) become identical when the graphs are assumed to be ordinary graphs; hence left, right and strong homomorphisms are all the same when defined for ordinary graphs. One might also note in passing the similarity between right homomorphisms and the prime homomorphisms of type Ba in Section 1.7. Lemma 1.9.4 and the definition of the equivalence relation = also suggest that one define an even broader class of homomorphisms. A full homomorphism, of a graph G onto a graph G' is semi-strong2 iff * satssfies the condition (10) ao = b.= n(a) c n(b) v n(b) c n(a). cf. [14], [15]. 2Strong homomorphisms satisfy the stronger condition that a< = b( =~ n(a) - n(b). -35

Theorem 1.9.9. If 4 is a semi-strong homomorphism of a graph G onto a graph G', then there exists a subgraph H of G such that H X G'. Proof. From each of the sets 4 (a'), a'cV', pick one point which has maximum degree. The subgraph H generated by this set of representatives is isomorphic to G'. Obviously, (a,b)p ==t (a',b')cp', where a4 = a', b4 = b', and a and b are the representatives chosen from. (a') and *- (b'), respectively. Also, (a',b')ep' (a,b)cp, for if (a',b')Ep', there must exist (a",b")ep such that a"' = a' and b"0 = b', Since n(a") c n(a) and b"en(a"), it follows that b"En(a). By the symmetry of the neighborhood relation, acn(b"). Since n(b") c n(b) it follows that aen(b). Hence (a,b)ep. One can show without much difficulty that the results previously stated for strong homomorphisms can be stated in a very similar way for semi-strong homomorphisms. In particular, CoroZZary 1.9.3, Theorem 1.9.6, Theorem 1.9.7, and CorollZZary 1.9.8 all hold when semi-strong is substituted for stong. In addition, Theorem 1.9.3 can be restated as: -36

Theorem 1.9.10. A graph G is simple with respect to semi-strong homomorphisms iff for every two distinct points a,beV(G), n(a) f n(b) and n(b) t n(a). It is natural in view of Theorem 1.9.9, to ask if for a full homomorphism * of a graph G onto a graph G' there exists a subgraph 1I of G such that H- G', is * necessarily a semi-strong homomorphism? The answer is no; as shown by Figure 12, e If o- -- b CIO: cf - f f' e' e.- e' d -' d' dill llI a~b c' a o G > G FIG. 12. In Figure 12, a< = b<, yet neither n(a) c n(b) nor n(b) C n(a) holds. -37

2. CONTRACTIONS 2.1. General Definition. A question arises in the literature on homomorphisms of graphs as to the interpretation of the homomorphic image of a pair of adjacent points a,beV(G) which map to the same point c'cV(G'). The definition of homomorphism given in Section 1.1, condition (1) in particular, specifies that the image is the point c' with a loop attached to it. However, Ore, Dirac, and several others choose to define homomorphisms for graphs for which the image of two adjacent points can be one point without a loop. These types of homomorphisms, which do not necessarily satisfy condition (1), can be defined as mappings < which satisfy the following modification of condition (1): (lm) (a,b)ep = (a0,b0)ep' V [ao = by /\ (ao,bo))p']. Following the terminology suggested by Dirac, Harary, and others, we will call a mapping, of a graph G =<V,p> into a graph G' = V',p'> which is a function from V into V' satisfying condition (lm) a contraction. It is this distinction which is the basis for placing homomorphisms, mappings which satisfy condition (1), in one class, and contractions, mappings -38

which do not necessarily satisfy condition (1) but which do satisfy condition (1m), in another class. However, when considering homomorphisms of reflexive graphs, i.e., graphs whose adjacency relation is reflexive, the distinction we have made between homomorphisms and contractions disappears. For in considering reflexive graphs, a point is always considered to be adjacent with itself, and thus what distinguishes one graph from another is no longer its set of points and lines but rather the underlying graph, i.e., its set of points and lines minus its loops. In diagramming reflexive graphs it would seem therefore uncecessary to include all the loops. Hence, in Figure 13 for example, the homomorphism j of G onto G2 could as well be represented by the homomorphism' of G' onto G'. QQ Q ___o o al bl a2 a b1 a2 G1 I G2 1 2 G2 FIG. 13. -.39 -

Forgetting, for a moment, that the points in G' and G' are assumed to be 1 2 adjacent with themselves, it would seem that * is a homomorphism, while o' is a contraction, since it fails to satisfy condition (1). But 0' does satisfy condition (1) if we assume that the points are adjacent with themselves, and hence the distinction between the two mappings disappears. 2.2. Connected and Independent Contractions. Ore [16] makes an interesting distinction between two types of contractions. A contraction $ is connected iff the subgraphs of G generated by the sets of points 4 (a'), for a'cV', are connected. A contraction * is independent iff the subgraphs of G generated by the sets of points ~-l(a'), for a'eV', are totally disconnected. Ore's independent contractions coincide exactly with the ordinary homomorphisms when defined over the class of ordinary graphs. Theorem 2.2.1. (Ore) Any contraction is the product of a connected and an independent contraction. Ore calls these mappings homomorphisms. -40

The leaf composition graph of a graph G is the graph whose points are the leaves of G; two points are adjacent iff the corresponding leaves are adjacent. Two points a,b belong to the same leaf iff there exists a sequence of cycles pl, p2,.., k, acV(Pl), bV(Pk), and v(pi) n v(Pi ) f 0. Theorem 2.2.2. (Ore) Any graph G has a contraction onto its leaf composition graph G1 such that the inverse image sets are the leaves of G. The graph G1 is circuit free. Theorem 2.2.2 implies, among other things, that every graph has at least one non-trivial tree as a contraction image. It follows also that since any two adjacent points can map to a single point, without a loop, every graph has K1 as a contraction image. Dirac [5] gives the following definition of a contraction: a graph G = <V,P> can be contracted onto the graph G' = KV',p'> if there exists a function 4 of V onto V' such that (i) (Va')[a'eV' = G - (G - % (a')) is connected], and (ii) (a') (Vb') [a',b'~V'^ (a',b')ep' e = G contains at least one line joining a point of 4~ (a') to -41

a point of )1 (b')]. In words, G = G' or G' can be obtained from G by shrinking each of a set of connected subgraphs of G into a single point. It is clear from the definition that the contractions that Dirac considers are all connected. Several of the papers written about connected contractions, by Dirac [5], Wagner [21], and Halin [9], are attempts to clarify the following Conjecture of H. Hadwiger: If the chromatic number of a graph G in n, then G has a connected contraction onto K. n The conjecture is known to be true for values of n < 4; it has been shown that a proof for n = 5 would be equivalent to a proof of the famous Four Color Conjecture. A typical result directed towards this conjecture is the following: every ordinary graph with n > 6 points and at least 3n-5 lines has a connected contraction onto K5 [6]. One property which is preserved under connected contractions but not under homomorphisms is planarity, i.e., if G is planar and c is a connected contraction of G then Go is also planar. The same cannot be said for ordinary homomorphisms. This is equivalent to condition (2) of Section 1.1. Note the similarity of this Conjecture to Corollary 1.3.2. -42 -

2.3. Simplicial Mappings. In combinatorial topology, see Pontryagin [17] for example, a class of mappings known as simplicial mappings are defined for complexes and are shown to be approximations of continuous mappings of polyhedra. When interpreted for graphs simplicial mappings become, in one sense, approximations of contractions. Let a point be a O-simplex, and let two points a,b and a line (a,b) between them be a 1-simplex. A mapping ~ of a graph G = KV,p> into a graph G' = <V',p> is simplicial iff (i) | is a function from V into V'; (ii) the image of a simplex in G is a simplex in G'. It can be seen without much difficulty that condition (ii) is equivalent to condition (lm). If one were to extend this definition to get onto simplicial mappings, perhaps the most natural way would be to require that * map the simplexes of G onto the simplexes of C'. The definition of a contraction is exactly this extension. 2.4. Homeomorphisms. A class of mappings of graphs which closely resembles, but which -43

in fact overlaps, the class of contractions are the homeomorphisms. Two ordinary graphs G and G' are said to be homeomorphic iff one can be obtained from the other by successive applications of the following two operations: (i) replace a line (a,b)cp by two lines (a,c) and (c,b), c being a new point; (ii) replace two lines (a,c), (c,b)cp, where (a,b)/p and the point c has degree two, by a new line (a,b). The pairs of graphs in Figure 14 are homeomorphic and serve to illustrate the difference between homeomorphisms and contractions. G: o P5: H: o G': X- - P: L — c H': o — FIG. 14 -44

In Figure 14, P5 can be contracted onto P4, yet no contraction maps H onto H', or H' onto H, and since K3 can be contracted onto K1 but K3 and K1 are not homeomorphic, it is clear that these two classes of mappings are distinct. The most notable result concerning homeomorphisms is the now classical Theorem of Kuratowski [13]: A graph G is planar iff G does not contain a subgraph homeomorphic to K5 or K33 2.5. Strong Contractions. Adam, Culik, and Pollak [1] have defined a class of mappings of graphs which very closely resembles the strong homomorphisms of Section 1.9; the definition of this class however contains an added condition which places the class in the class of contractions. A mapping ( is a strong contraction of an ordinary digraph G = <V,p> onto an ordinary digraph G' = V',p'> iff (i) ( is a function from V onto V'; 1Adam, Culik, and Pollak refer to such a mapping as "ein starker homomorphismus". 2An ordinary digraph like an ordinary graph, has no loops or multilines. -45

(ii) (a,b)ep'^ (b,a) ep == = a = b ^ (a4,b4)jp'; (iii) (a,b)ep ^ (b,a) p == (aO,b) cp1 ^ (bo,ao)4p'; (iv) (a,b)4p ^ (b,a)4p - (ao,b4)4p' /\ (b4,a4)p'. It is assumed that points a and b in conditions (ii), (iii), and (iv) are distinct. The authors show that an ordinary digraph has at most one strong contraction, and in the following theorem give a necessary and sufficient condition for a non-trivial strong contraction to exist. Theorem 2.5.1. An ordinary digraph G = <Vo> has a strong contraction iff for every triple a,b,c of distinct points (i) (a,b), (b,a), and (a,c)e ep (b,c)ep; (ii) (a,b), (b,a), and (c,a)ep -- (c,b)ep. Corollary 2.5.2. If ~ is a strong contraction of an ordinary digraph G onto an ordinary digraph G', then there exists a subgraph H of G such that He G'. A proof of this corollary can be constructed that is essentially the same as the proof of Theorem 1.9.1, which is the corresponding statement for strong homomorphisms. -46

3. RELATIONAL HOMOMORPHISMS 3.1. General Definition, The concept of a homomorphism (and a contraction), of a graph G = <V,p> into a graph G' = <V',p'>, generally speaking, consists of a function * from V(G) into V(G') which satisfies certain conditions. These conditions are usually imposed so that certain properties of the graph G will be preserved in G' by the function X, A natural generalization of this concept is that of a "relational homomorphism," between two graphs G and G', in which a binar relation is defined, C VxV', which satisfies certain conditions. The idea of considering relations as homomorphisms between algebraic systems has occurred to at least two authors, some of whose definitions and results along this line are summarized in this section. We will refer, in general, to the mappings defined in this section as relational homomorphisms. -47

3.2. Weak Homomorphisms. Yoeli and Ginzburg [8] and Yoeli [23] have defined a weak homomorphism for partial and complete algebras which can, in a natural way, be rephrased for directed graphs. Once this is done, a development exactly analogous to that in [23] can be carried out which illustrates the definition of weak homomorphism and some of its properties for directed graphs. The remainder of this section is just such a development; it contains nothing original and is simply a translation of the first part of [23] into graph theoretical terminology. Every directed graph G = <V,p>, including those with loops and multi-lines, can be expressed, generally in many ways, as a union of graphs of the form Gi = <V,pi>, where Upi = p. Alternatively, every directed graph can be put in the form G = <V,{pi}>, where lpi = p. In particular, each pi can be required to be a many-one relation, i.e., a partial function from V to V. A digraph is out-regular of degree k iff it can be put in the form G = <V,{plp2,... pk}>, where each pi is a function from V into V. Equivalently, a digraph G is out-regular of degree k iff the out-degree -48

of every point of G equals k. A binary relation * c VxV' is a weak homomorphism of a digraph G = <V,{pi}> into a digraph G' =<V',{p}>, i = 1, 2,..., m iff, satisfies the following two conditions (11) (V') = V, and (12) 4 Pi. Pi,, for every i = 1, 2,..., m; in words, if 1-1 aepi (V) and a4a', then a'ep'C and p.(a)p!'(a'). _, ~0'i and Pi~a)~Pi 1 If in addition the binary relation * is a function from V onto V' satisfying the condition (13) sp! = pi+, for all i, 1i i then * is a full homomorphism of G onto G'. The following three lemmas correspond exactly to Lermmas 1, 2, and 3 of Yoeli [23]. Lenmma 3.2.1. If 4 is a weak homomorphism of a digraph G into (- digraph G', and 4' is a weak homomorphism of G' into a digraph G", then Note that the definition requires that a 1-1 correspondence exist between {p.} and {p!}. Yoeli calls 4i, in this case, a strong homomorphism. It can be seen however that condition (13) requires that the mapping be a full homomorphism, as defined in Section 1.1, of the digraph G onto the digraph G'. -49

'' is a weak homomorphism of G into G". Lemma 3.2.2. A mapping' of a digraph G onto a digraph G' is a full homomorphism iff both I and *'1 are weak homomorphisms. Lemma 3.2,3. If' is a weak homomorphism of an out-regular digraph G onto a digraph G', then *- is a weak homomorphism of G' onto G. For additional discussion of weak homomorphisms the reader is referred to Yoeli. In Figure 15,'1 is an example of a weak homomorphism of G1 onto G2, where $1 = {(a,c),(a,e),(b,d),,bf)}. a c 9 e b d f G1 -/> G FIG. 15. Note also that *1 is a full homomorphism of G2 onto G1. -50

3.3. Weak Isomorphism. A binary relation p c VxV' is a weak full homomorphism of a graph G = <Vp> onto a graph G' =V',p' iff in addition to satisfying condition (11) it satisfies conditions (14) p(V) = V', and (15),(p) = p,. A weak full homomorphism of a graph G onto a graph G' is a weak isomorphism iff p (p') = p. Consider Figure 16, where'p = {(a,a'),(a,a"), (b,b'),(b,b")} is a full weak homomorphism of G onto G'. a a'!all b t be X b' G C' FIG. 16. Since i (p') = p, it follows that G and G' are weakly isomorphic. Thatcher [20] has studied both weak full homomorphisms and weak isomorphisms, -51

and offers the following explanation for considering intuitively G and G' to be'isomorphic.' Two graphs G and G' are elementarily equivalent iff they are indistinguishable using the first-order predicate calculus without equality, i.e., no sentence in this language is true of G without its also being true of G', and conversely. Thatcher states that if two graphs G and G' are weakly isomorphic then they are elementarily equivalent. He also believes that the converse is true for finite graphs, i.e., if two finite graphs, G and G', are elementarily equivalent then they are weakly isomorphic. Since in the first order predicate calculus without equality one loses the ability to count, one cannot distinguish whether two graphs have the same number of points. It follows, therefore, that among other things all complete digraphs are weakly isomorphic. Thatcher suggests as an interesting problem the study of these weak isomorphism types of graphs. The following results shed some light on this problem. It is not true however that all ordinary complete graphs are weakly isomorphic. -52

Lemna 3.3.1. If 4 is a strong homomorphism of a graph G onto a graph G', then G and G' are weakly isomorphic, i.e., 4 is a weak homomorphism of G' onto G. Proof. Obviously 4 is a weak homomorphism of G onto G', and as such ~(V) = V' and P(p) = p'. It follows therefore that (-1V') = V. It suffices to show that 4) (p') = p. First, (a' b')ep'. (4 l(a'),4) (b'))Ep, for if ac() (a') and bc)l (b'), then (a,b)ep, since g(a,b) = g'(a),b)) = g'(a',b') = 1. Secondly, (a',b') p' p (I ) (a'),4 (b'))Op, by the same reasoning. Theorem 3.3.2. T)o graphs G and G' are weakly isomorphic iff they have isomorphic simple (with respect to strong homomorphisms) images. Proof. First, suppose that G and C' are weakly isomorphic with respect to the full weak homomorphism *, i.e., G -s G ( l s-l where 4s and )' are strong homomorphisms of G and G' onto the simrple graphs cf. Section 1.9. -S3

Gs and G', respectively. It suffices to show that ifs is a strong homomorphism of G onto G'. The isomorphism of G and G' then follows as a result of Theorem 1.9.7. We must show that Ad' is a well defined mapping of V(G) onto V(GI), where 4 is a full weak homomorphism of G onto G' and s' is a strong homomorphism of G' onto G' (and G' is simple). We do this by showing that s s (i) aPal ^ apal - n(a') = n(a'), and (ii) n(a) = n(a)-ais = as Let us prove, (i) aPaI ^ aia2 I n(al) = n(ap). Suppose n(al) f n(ap). 1 2 1 2 Then either p'(al) p'(a ) or p (al) # p' (a). If p'(al) f p'(a ) then md') [((al,d')Ecp' / (al,d'),p') v ((al,d')gp' ^ (a1,d')ep')], Suppose (al,d')p' ^ (a,d')4p'; then (3c)(-d)[(c,d)cp ^ cla'l dcd']. -1l But since i is a full weak homomorphism of G' onto C, (al,d')ep'.-_ (a,d)cp (al,d')ep', hence we have a contradiction. A similar argument shows that (al,d')~p' ^ (a',d')cp' cannot hold either, 2 2 hence p'(ai) = p'(a2), must hold. The same argument just used to show that p'(a') = p'(a) can be -.54

used to show that p' (a') = p' (a'). Hence n(al) = n(a') must hold. In order to see that (ii) n(a') = n(a) a = one need only refer back to the definition of the equivalence relation _ which determines the strong homomorphism s'. Hence is' is a well defined mapping of V(G) onto V(G'); it is 5 S a simple matter to verify that the mapping satisfies the condition g(a,b) = gl(a*0s,b*s). s S 5 The mapping *p' is therefore a strong homomorphism of G onto G'. S 5 Second, suppose that G and G' are isomorphic, 5 s, G -1 G'I where for convenience we suppose that 4s and 4' are strong homomorphisms -1 is a full weak homoof G and G' onto Gs. It suffices to show that 1 is a full weak homomorphism of G onto G', and similarly that (sfs is a full weak homomorphism s s of G' onto G. But this follows immediately as a result of Lemmna 3.3.1 and -55

the following Lemma 3.3.3. If i is a full weak homomorphism of G onto G', and *' is a full weak homomorphism of G' onto G"' then p*' is a full weak homomorphism of G onto G". -56

SUMMARY AND SUGGESTED PROBLEMS Several definitions have been given of homomorphisms for various classes of graphs and a few results have been stated or derived for each. The nature of the results gives an indication of the kinds of properties of graphs one can effectively study by means of homomorphisms, and gives an indication of the methods one might use in studying properties of the homomorphisms themselves. Several open problems and problem areas have been suggested in the paper, and several new ones can be stated, among which are the following: 1) How does the set of (elementary) homomorphic images of a given graph G characterize G? It can be shown, for example, that the set of all non-trivial homomorphic images of an ordinary graph G, together with the multiplicities associated with each image, i.e., the number of distinct ways the particular image can be formed under a homomorphism, completely characterize the graphs with five points or less which are not complete graphs. 2) Of the 52 ordinary graphs with five points or less, 31 have -57

one elementary homomorphic image (up to isomorphism). Can one easily characterize those graphs G such that all of the elementary homomorphic images of G are isomorphic? The following five graphs have this property 0 —-0 C^ —I_ 1G G2 G3 G4 G5 3) Geert Prins, in a letter to the author, expressed an interest in studying homomorphisms of graphs via elementary homomorphisms. What in general can one say about elementary homomorphisms? For example, one could state the following Proposition: If Ge is that elementary homomorphic image of G obtained by identifying points a,bcV(G), and the chromatic number of G is n, then the chromatic number of Ge is n iff points a and b can be colored identically in some n-coloring of G. -58

4) What sort of graph theoretical results are obtainable from Keisler's logical formulation of the properties of a graph which are preserved under full homomorphisms? For example, a brief explanation of Keisler's formulation by Professor Robert Ritchie led to the following observation: Proposition. If * is a full homomorphism of an ordinary graph G onto a graph G', and G = G + G2, i.e., G is the join of G1 and G2, then G' = G1, + G2. It is believed that almost all of the results derived using Keisler's formulation could be derived very easily without using it. 5) In regard to pre-images of a given graph, how close to a complete graph, in some sense, can a pre-image of a given graph be? For example, if an ordinary graph G has p points and q lines, define its density as q/(P). It would seem, at first glance, that since every ordinary graph G maps onto a complete graph, -59

of density 1, that the density of a given graph G would be smaller than the density of every homomorphic image of G. But this is not the case as the following example illustrates: 1: a - a' e f b,e - b' C,f -- c' d'-d' ( — 9 O — -- a b c d a' b' c' d' G - -> G' Note that the density of G is 8/15, while the density of Go = G' is 3/6. 6) For any class of homomorphisms, what graphs are endomorphismfree? 7) Which graphs are simple with respect to pathwise homomorphisms? 8) Are all prime homomorphisms of functional digraphs, pathwise homomorphisms as well? It appears so. 9) Characterize Prins' type-2 complete homomorphisms. This problem appears to be very difficult. 10) Relative to the study of type-n (complete) homomorphisms several -60

problems naturally arise among which are the following: a) Does there exist for every integer n a type-n (complete) homomorphism? b) Is the order of a type-n complete homomorphism greater than or equal to n? c) Can one state an Interpolation Theorem for type-n complete homomorphistms, i.e., given a type-n complete homomorphism of a graph G, of order m, what can be asserted about type-k complete homomorphisms of G for k < n. d) If the length of the longest chain in a graph G is n, it would seem that G could not have a type-n+l complete homomorphism. Relate this length n to the maximum type-n complete homomorphism of G. 11) Any rule for producing a non-identity partition of the points of an arbitrary graph G determines a full homomorphism in the following sense: Let V1, V2,.,., Vm be a partition of V(G), and let xi -61

denote the chromatic number of the full subgraph generated by the subset Vi. The mapping which maps each subgraph respectively onto K. determines a full homomorphism of G. If we denote the resulting graph in this process by Go and apply the same partition-mapping process to G(, G(, etc., we might ultimately map G onto a complete graph. It would be interesting to study those processes which map a given graph G ultimately onto a complete graph and to examine the relationship between the chromatic numbers of G and the complete graph. Two such processes have already been mentioned; one, of taking partitions determined by 1-bases, and two, of taking partitions determined by n-bases. A third process would be that of considering partitions induced by the associated numbers of the points of a graph. 12) How can the concept of complete homomorphism be applied to directed graphs? 13) The homomorphisms of functional digraphs onto functional digraphs -62

all satisfy the condition (i) od(a) = od(a+). It is suggested therefore that one study full homomorphisms which satisfy this condition, or the following condition (ii) id(a) = id(a4), or both; in particular, study full homomorphisms of ordinary graphs which satisfy (iii) deg(a) = deg(ao). Furthermore, functional digraphs are a sub-class of the class of out-regular digraphs; hence, the suggestion of studying homomorphisms of out-regular and in-regular digraphs and regular ordinary graphs, satisfying conditions (i), (ii), and (iii), respectively, is raised. 14) Y. Give'on has suggested that one study epigenic homomorphisms of directed graphs; homomorphisms for which the inverse image of bases (generating sets) are bases. It can be seen, for -63

example, that any homomorphism of a weakly connected digraph onto a strongly connected digraph is not epigenic, 15) Relative to Proposition 1.5.5, it seems that with the exception of K2 one can strengthen the inequality to ch(G) < 2q - 2. 1.6) Relative to the question raised at the beginning of Section 1.5, one can ask the following, slightly different, and much more interesting question: for a given graph G what is the length of the shortest cycle P for which there exists a homomorphism * which maps P onto G? The homomorphism * need not be a full homomorphism. Suppose we call this the circuit length of G, and denote it by ci(G). The following example illustrates that ci(G) and cy(G) are, in fact, distinct invariants; a little reflection shows further that ci(G) < cy(G). c2 a2 b2 aa4 b — d b- <k-b b. c- 6 -- ca5 a 5b4 c6 c5 Ps > G ------ P7 -64

~: a1 — bl i: c1 -- b a2 ) b2 C2 -b2 a3 b3 C3,c6 - b3 a4 - b4 c4 - b4 a5 - b5 c5,c7 - b5 The mapping * is a homomorphism of P5 onto G; the mapping i is a full homomorphism of P7 onto G. Hence, ci(G) = 5, while cy(G) = 7. It can also be seen that if a graph G has p points then ci(G) = p iff G is Hamiltonian, The parameter ci(G) also can be seen to have a lot of relevance to solutions of the famous Traveling Salesman Problem. It would be interesting in view of these observations to investigate the extent to which the methods used to study cy(G) can be used to study ci(G). -65

APPENDIX OF DEFINITIONS In a graph G = <V,p>... the out degree of a point beV, od(b) = |p(b)|;... the in degree of a point beV, id(b) = p1 (b)|;... the degree of a point beV, deg(b) = jn(b)| = |p(b)U p l(b);.. a loopat a point b is a line of the form (b,b);... a path of length n from a point a to a point b is a sequence of points a. 0 a. *.., ai such that (a. ai )eP, for 0 < j i n - 1, a. = a, and 0 11 n j+l 10 a. =b; n *.. the distance from point a to point b, d(a,b), is the length of the shortest path from a to b;... the associated number of a point bcV is max d(b,c), for all ceV. L... the diameter of G, 6(G), is max d(a,b), for a,beV. *.. an independent set of points is a set V1 c V such that for every a,beV1, (a,b)gp;... a maximal independent set of points is an independent set V1 such that -66

for no independent set V2 is V c V2;... the point independence number, ao(G), is max IV1|, where V1 is an independent set of points;. the point covering number, Bo(G), is min IV2, where V2 C V is such that for every (a,b)cp, either acV2 or bcV2.. the subgraph generated bv a set of points V', is the graph G = <V',p'> where p' = {(a,b): a,bcV' ^ (a,b)ep) An ordinary graph G = <V,p>. is a complete graph on n points iff it has the form V = {kl, k2,..., kn) p = {(ki,kj): i ~ j}; *.. is a cycle of length n iff it has the form V = {P1, P22' *' Pn} P ={(iPip1l),(PilpPi): 1 < i < n-l} U {(p1,Pn),(pnPl)}... is a chain of length n iff it has the form V = {C1, c2, **.. Cn+l} P = {(ciCi+il),(Ci+li): 1 < i < n}; -67

... is connected iff for every pair a,b of distinct points there is a path in G from point a to point b;... is a tree iff it is connected and contains no cycles as subgraphs;... is critical of degree k iff x(G) = k and (V(a,b)cp) [X(G-(a,b)) = k - 1]; in words, the chromatic number of any graph obtained from G by removing any line, or point, of G is less than the chromatic number of G;.. is isomorphic to K35 iff it has the form V = {a1,a2,a3,bb2,b3} p = {(ai,b.),(bj,ai): 1 < i, j <. 3};... has multi-lines iff p is considered to contain at least two occurences of at least one pair (a,b);... is a multi-graph iff it contains multi-lines;... is the join of graphs G1 = <Vl,pl> and G2 = <V2,P2> iff V V1U V2' P p1U P2 U {(a,b)l aeV1, beV2} -68

BIBLIOGRAPHY 1. Adam, A., Culik, K., and Pollak, G., "Ein Satz uber Teilweise Gerichtete Graphen," Czeckoslovak Math. Journal 13 (88) 1963, 619-620. 2. Berge, Claude, Theorie des Graphes et ses applications, Paris, 1958, 3. Culik, Karel, "Zur Theorie der Graphen," Casopis Pest, Mat, 83 (1958), 133-155. 4..Dirac, G. A., "A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger," Proc. London Math. Soc. (3)7 (1957), 161-195. 5. Dirac, G. A., "A Contraction Theorem for Abstract Graphs," Math, Annalen 144 (1961), 93-96. 6. Dirac, G. A., "Homomorphism Theorems for Graphs," Math. Ann. 153 (1964), 69-80. 7. Gallai, T., "Maximum-Minimum Satze und verallgemeinerte Faktoren von Graphen," Acta. Math. Acad. Sci. Hungar. 12 (1961) No. 1-2, 131-173. 8. Ginzburg, A. and Yoeli, M., "Products of Automata and the Problem of Covering," Technion, Israel Institute of Technology, Haifa, Technical Report No. 15, (July, 1963). 9. Halin, R. and Wagner, K., "Homomorphiebasen von Graphenmengen," Math. Ann. 147 (1962), 126-142. 10. Hartmanis, J. and Steams, R. E., "Pair Algebra and Automata Theory," Inform, and Control 7 (1964), 485-507. 11. Keisler, H. J., "Properties Preserved under Retracts and Strong Homomorphisms," NAMS 10 (1963), No. 4, p. 372. 12. Krohn, K. B. and Rhodes, J. L., "Algebraic Theory of Machines," Mathematical Theory of Automata, Microwave Research Institute Symposia Series, Vol. XII, Polytechnic Press, Brooklyn, N. Y., 341-384. 13. Kuratowski, G., "Sur le probleme des courbes gauches en topologie," Fund. Math. 15-16 (1930), p. 271. 14. McNaughton, Robert, "Skeletal Lecture Notes," E. E. 640, The Moore School of Electrical Engineering, University of Pennsylvania, December, 1963. -69 -

15. Moore, E. F., "Gedanken-Experiments on Sequential Machines," Automata Studies, Princeton University Press, 1956. 16. Ore, Oystein, Theory of Graphs, Amer. Math. Soc. Colloquium Publications, Vol. XXxVtl, UT62. 17. Pontryagin, L. S., Foundations of Combinatorial Topology, Graylock Press, Rochester, N'. Y., T192.18. Sabidussi, Gert, "Graph Derivatives," Math. Zeitshcrift 76 (1961), 385-401. 19. Sabidussi, Gert, "Vertex-transitive Graphs," Monat. fur Mathematik 68 (1964), 426-438. 20. Thatcher, James W., "Homomorphisms for Relational Systems," IBM Research Note NC-369, April, 1964, 21. Wagner, K., "Bemerkungen zu Hadwigers Vermutung," Math. Ann. 141 (1960), 433-451. 22. Yoeli, M. and Ginzburg, A., "On Homomorphic Images of Transition Graphs," Technion, Israel Institute of Technology, Haifa, Israel, Technical Report No. 11, April, 1963. 23. Yoeli, M., "Multi-valued Homomorphic Mappings and Subdirect Covers of Partial Algebras," Mathematics Research Center, Technical Summary Report #493, University of Wisconsin, July, 1964. 24. Zeiger, H. P., "Loop-Free Synthesis of Finite State Machines," Ph.D. Thesis, MIT, 1964. -70

DISTRIBUTION LIST (One copy unless otherwise noted) Technical Library Naval Electronics Laboratory Director Defense Res. & Eng. San Diego 52, California Room 3C-128, The Pentagon Attn: Technical Library Washington, D.C. 20301 Dr. Daniel Alpert, Director Defense Documentation Center 20 Coordinated Science Laboratory Cameron Station University of Illinois Alexandria, Virginia 22314 Urbana, Illinois Chief of Naval Research 2 Air Force Cambridge Research Labs Department of the Navy Laurence C. Hanscom Field Washington 25, D.C. Bedford, Massachusetts Attn: Code 437, Information Attn: Research Library, CRMXL R Systems Branch U. S. Naval Weapons Laboratory Director, Naval Research Laboratory 6 Dahlgren, Virginia 22448 Technical Information Officer Attn: G. H. Gleissner, Code K4 Washington 25, D.C. Asst. Dir. for Computation Attention: Code 2000 National Bureau of Standards Commanding Officer 10 Data Processing Systems Division Office of Naval Research Room 239, Building 10 Navy 100, Fleet Post Office Box 39 Washington 25, D.C. New York, New York 09599 Attn: A. K. Smilow Commanding Officer George C. Francis ONR Branch Office Computing Laboratory, BRL 207 West 24th Street Aberdeen Proving Ground Maryland New York 11, New York Office of Naval Research Office of Naval Research Branch Branch Office Chicago Office 219 South Dearborn Street 495 Summer Street Chicago, Illinois 60604 Boston, Massachusetts 02110 Commanding Officer Naval Ordnance Laboratory ONR Branch Office White Oaks, Silver Spring 19 1030 E. Green Street Maryland Pasadena, California Attn: Technical Library Commanding Officer David Taylor Model Basin ONR Branch Office WashingtonD.C. 20007 1000 Geary Street Attn: Code 042, Technical Library San Francisco 9, California

DISTRIBUTION LIST (Concluded) The University of Michigan Lincoln Laboratory Department of Philosophy Massachusetts Institute of Technology Attn: Professor A. W. Burks Lexington 73, Massachusetts Attn: Library National Physical Laboratory Teddington, Middlesex, England Office of Naval Research Attn: Dr. A. M. Uttley, Supt. Washington 25, D.C. Autonomies Division Attn: Code 432 Commanding Officer Kenneth Krohn Harry Diamond Laboratories 6001 Dunham Springs Road Washington, D.C. 20438 Nashville, Tennessee Attn: Library Mr. Laurence J. Fogel Commanding Officer and Director General Dynamics/Astronautics U. S. Naval Training Device Center Division of General Dynamics Corp. Port Washington San Diego, California Long Island, New York Attn: Technical Library Department of the Army Office of the Chief of Research and Development Pentagon, Room 3D442 Washington 25, D.C. Attn: Mr. L. H. Geiger National Security Agency Fort George G. Meade, Maryland Attn: Librarian, C-332

UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA - R&D (Security cla1etfication of title, body of abatract and indexing annotation must be entered when the overall report ie claaailied) 1. ORIGINATIN G ACTIVITY (Corporate author) 2a. REPORT SECURITY CLASSIFICATION Logic of Computers Group Unclassified The University of Michigan 2b. GROUP Ann Arbor, Michigan 48104 3. REPORT TITLE HOMOMORPHISMS OF GRAPHS 4. DESCRIPTIVE NOTES (Type of report and inclusive datea) Technical Report S. AUTHOR(S) (Last name first name, initial) Hedetniemi, Stephen 6. REPORT DATE 7a. TOTAL NO. OF PAGES 7b. NO. OF REFS December 1965 72 24 8a. CONTRACT OR GRANT NO. 9. ORIGINATOR'S REPORT NUMER(S) Nonr 1224(21) 03105-42-T b. PROJECT NO. c. ST. OTH I R RIPO T NO(S) (Any other numbere hlt may be aasCnied hte report) d. 10. A V IL ABILITY/LIMITAiON NOTICES Qualified requesters may obtain copies of this report from DDC. II. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY Office of Naval Research Department of the Navy _ Washington, D.C. 13. ABSTRACT The works of Hartmanis and Stearns, Krohn and Rhodes, Yoeli and Ginzburg, and Zeiger amploy demonstrate the usefulness of homomorphisms in studying decompositions of finite automata. Yoeli and Ginzburg's approach is slightly different from the others in that it is more concerned with aspects of the state transition graphs of finite automata. In their paper, "On Homomorphic Images of Transition Graphs," they give a complete characterization of the class of homomorphisms of the graphs which correspond to input-free automata. (U) This paper was motivated by an interest in extending these results of Yoeli and Ginzburg in the direction of a characterization of the class of homomorphisms of graphs which correspond to arbitrary finite automata. It is a review and a classification of most of the published definitions and results on mappings of graphs which have been called homomorphisms. The paper contains, in addition, several new results and several new definitions of homomorphisms of graphs. (U) DD *1J4 1473 UNCLASSIFIED Security Classification

UNCLASSIFIED Security Classification_ 14. LINK A LINK B LINK C KEY WORDS KOL WT ROLE WT ROLE WT 1. graph theory 2. homomorphisms INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) liied requesters my obin copies o this the report. (I) "Qualified requesters may obtain copies of this the report. report from DDC." 2a. REPORT SECURITY CLASSIFICATION: Enter the over- (2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether 2 orn nnn nt a ieii i "Restricted Data" is included. Marking is to be in accord- report by PDC is not authorized " ance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of this report directly from DDC. Other qualified DDC 2b. GROUP: Automatic downgrading is specified in DoD Di- users shall request through rective 5200. 10 and Armed Forces Industrial Manual. Enter the group number. Also, when applicable, show that optional., markings have been used for Group 3 and Group 4 as author- (4) "U. S. military agencies may obtain copies o this report directly from DDC Other qualified users 3. REPORT TITLE: Enter the complete report title in all shall request through capital letters. Titles in all cases should be unclassified., If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled. Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of.____ report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period is Services, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 11. SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Enter tast name, first name, middle initial. tory notes. If military, show rank and branch of service. The name of the principal author is an absolute minimum requirement. 12. SPONSORING MILITARY ACTIVITY: Enter the name of 6 REPORT AT- E t dat f t r a day the departmental project office or laboratory sponsoring (pay 6. REPORT DAT._ Enter the date of the report as day, ing for) the research and development. Include address. month, year; or month, year. If more than one date appears on the report, use date of publication. 13. ABSTRACT: Enter an abstract giving a brief and factual 7a. TOTAL NUMBER OF PAGES: The total page count 0 summary of the document indicative of the report, even though 7a. TOTAL NUMBER OF PAGES: The total page count it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter th< im as p r elsewhere in tebody o the technical renhould follow normal paginoation procedures, i.e, enter the port. If additional space is required, a continuation sheet shall number of pages containing information. be attached. 7b. NUMBER OF REFERENCES: Enter the total number of 7b. NUMBER OF REFERENCES: Enter the total number of It is highly desirable that the abstract of classified reports references cited in the report, be unclassified. Each paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the paragraph, represented as (TS), (S), (C), or (U) the report was written. There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number, subproject number, system numbers, task number, etc. 14KEY WORDS: Key words are technically meaningful terms or short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offi- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected so that no security classification is required. Identiand controlled by the originating activity. This number must fiers, such as equipment model designation, trade name, military be unique to this report. project code name, geographic location, may be used as key 9b. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical context. The assignment of links, rules, and weights is optional. assigned any other report numbers (either by the originator The assignment of links, rules, and weights is optional or by the sponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any limitations on further dissemination of the report, other than those UNC LASS IF IED Security Classification

UNIVERSITY OF MICHIGAN 3 9015 03026 9248