AUTOMORPHIfiM GROUPS OF GRAPHS Thesis for ”:9 Dawn of DH. D. M231 EGAN STATE EEEVERSETE’ Jufian Kateiey, Jr. 1963 TH ESlS This is to certify that the thesis entitled AUTOMORPHISM GROUPS of GRAPHS presented by Julian Kateley, Jr . has been accepted towards fulfillment of the requirements for Pho Do degree in E. E. Major proiissor a-Ifl’. Date August 6. 1963 LIBRARY Michigan State University AUTOMORPHISM GROUPS OF GRAPHS By Julian Katcley, Jr . AN ABSTRACT OF A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 19(1); ABSTRACT AUTOMORPI-HSM GROUPS OF GRAPHS by Julian Kateley, Jr. A graph is defined to be a systetn (S,R), where S in a finite, non—null set and R is a subset of S x S, or sin‘iply a relation on. R. ,\'o other restrictions are put on R so that the graphs considered are oriented or directed and may have loops or slings. After carefully defining the preliminary mathematical concepts used, a study is made of the problem of finding the automorphism group of a graph. Certain well known techniques are presented in a form applicable to oriented graphs. A special technique is forn‘iulated which considerany simplifies the otherwise difficult task of calculating the automorphism groups of a graph. Some consideration is given to certain classes of special graphs. These are l interchanve Graphs, .1) Ora h roducts, 5 self—comale— s t - s P l mentary graphs, and (4) graphs having specified groups. AUTOMORPHISM GROUPS OF GRAPHS By Julian Kateley, Jr . A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 1963 G 32.9 to '3 7/? no 4 ACKNOWLEDGEMENT Bk)acknowledgernentcan.possfifly'conveythe credfi.duethe many individuals who have contributed to this thesis. The continued assistance, guidance and patience of Dr. G. P. Weeg; the support and counselcd Dr. L“ VV. Von Tersch; andthe cooperatkniand.encouragernent of the author's family are but a few of the factors that have made this thesis possible. -11- II. III. IV. V. VI. TABLE OF CONTENTS INTRODUC TION -- BASIC CONCEPTS AND THE DEFINITION OF A. GRAPH THE AUTOMORPHISM GROUP OF A GRAPH PROCEDURES FOR CALCULATION OF THE AUTOMORPHISM GROUP OF A GRAPH SPECIAL GRAPHS CONCLUSION BIBLIOGRAPHY . ~iii— Page J: 10 {J 1 I» Iv LIST OF FIGURES The graph of Example 3.1 The graphs of EXample 4.1 The graph of Example 4. Z _i\'... Page 15 18 19 An Intersection Table for Example 4. 4 Analysis of the cycle (1) for Example 4.4 Analysis of the cycle starting with 13 for Example 4. 4 Analysis of the cycle starting with 15 for Example 4. 4 LIST OF TABLES Page 28 Z9 Z9 3 O I. INTRODUCTION Graphs have been the object of study for at least the last one hundred years, both as a mathematical discipline in themselves and also as an important tool in various other fields. Thus graphs are used in the study of electrical networks, switching circuits, and corn— munication networks to mention but a few of the areas related to Electrical Engineering. Graphs are used also in branches of Chemistry, Physics, Biology, Psychology, Philosophy and Sociology. Much of the work to date has concentrated on what may be characterized as the topological properties of graphs. Thus the con- nectivity properties of graphs, the path, circuit and tree properties, and such other properties as the chromatic number of a graph are all in the general category of topological properties of graphs. The objective of this thesis is to set forth certain algebraic properties of graphs. D. Konig in his book, "Theorie der endlichen and unendlichen Graphen, " Leipzig (1936) poses questions of an algebraic nature about graphs. For example, Kdnig asks, "When can a given abstract group be set up as the group of a graph, and if possible how can the graph be constructed?" In spite of the early origin of this question in Kfinig's classic book on graphs, literature in the area of algebraic studies of graphs is meager and of fairly recent origin. Ore [OI] in his book on graphs devotes only one short chapter to the groups of graphs. C. Berge in his book, "The Theory of Graphs, " London (1962) makes no reference per se to algebraic properties of -1- -3- graphs. Several of the pertinent works are cited in the text of this thesis, but as evidence of the limited publications on this subject, these references are also cited here. For example, Frucht [Fl] has briefly examined the groups of isomorphic graphs. Frucht [F2] and Sabidussi [SI], [82] have studied the problem posed by Konig of finding graphs with given groups. Kagno [K1], [K2] has investigated certain types of graphs and presented their groups. Sabidussi [S3] has studied graph products, and finally, Sabidussi [54] has studied interchange graphs or graph derivatives. Cre [Ol] apparently includes all other papers in his bibliography pertinent to the subject of algebraic properties of graphs. Unavoidably, use is made of topological properties of graphs in this thesis, not only because there is no clear dividing line between topological and algebraic properties, but also because certain topolo- gical properties result in interesting and useful algebraic properties. Nevertheless, the definition of a graph is based on algebraic concepts as presented in Section II. Algebraic concepts leading to the definition of the group of a graph are presented in Section III. The intent is that these two sections establish a rigorous basis for the following two sections, which contain the main results of this thesis. Of central interest, in this and other algebraic studies of graphs, is the group of the graph. For graphs of even reasonable size, the direct calculation of these groups is extremely difficult. The results of Section IV make feasible the hand calculation of groups of graphs _3_ of nooderate size even when computer calculations were previously too lengthy. Certain results of Section IV also provide a basis for an attack on the problem posed by Konig, as discussed in Section V. In parti- cular, though several authors have examined his question, a completely satisfactory answer has not yet been given. As will be made evident in this thesis, the answer so far given for Konig's question is that every finite group is isomorphic. to the automorphism group of a graph. The graph constructed having the desired property, however, contains many more vertices than the group does symbols. This rather avoids the real intent of the problem, namely, what groups are groups of graphs where the number of vertices and the number of group symbols are equal? It is known that for a cyclic group generated by a single cycle that there is no graph having that group when the graph is non- oriented (see Kagno [Kl]). In this thesis, it is shown that this restriction does not exist if oriented graphs are considered, indeed, it is shown that for a broad class of groups the corresponding oriented graphs do exist. Section V also includes consideration of certain other algebraic properties 'of special kinds of graphs including the problem of finding a graph of a given group, if there is such a graph. The special kinds of graphs considered also develop insight into this problem. For some reason not fully understood by this student, all of the papers cited investigate only non-oriented graphs. As a consequence of the results presented in this thesis, such a restriction is not only un- -4- necessary but undesirable for certain problems. As a final introductory comment, it should be noted that the symbol A is used throughout this thesis to indicate the completion of a proof. II. BASIC CONCEPTS AND THE DEFINITION OF A GRAPH So as to define properly the concepts peculiar to this thesis and to provide continuity to the text, certain standard mathematical concepts and definitions will be given here. Those definitions, which though they might not be original with this thesis, but for which there may be some controversy in the literature, will be assigned a numbered definition. It is thereby hoped that the definitions and theorems of this and succeeding sections follow in a natural and comprehensible way. Every mathematical system ultimately rests upon certain un- definable concepts. In set theory, the undefinables are commonly taken to be "set", "element", and "belongs to'.'. Thus, no attempt is made to define set. However, a set is said to be composed of elements. Moreover a set is said to be well defined if, given any object, it is possible to decide whether or not this object belongs to the set. The set of those elements having a specified property P is denoted by k I x has property 13 . The set with no elements is called the null set, and is denoted by I . Given any two sets A and B, A is a subset of B, denoted by AEB, if each element of A is an element of B. A is a proper subset of B, denoted by ACE, if A is a subset of B, A is not the null set, and there is at least one element of B which is not an element of A. Two sets A and B are 33.11—31.13 denoted by A = B, if A513 and BEA. The Cartesian product of a set of sets A , A 2,...) n I noted by Al x A2. x - - ' x A is the set of all ordered n-tuples 11’ -5- -5- -, an], where ai is in Ai for i = l, 2, - ' - , n. Two elements - , bn] and [c1, c2, - - - , Cn] of A1 x AZ x ' - - x Ar1 are equal if and only if bi :2 ci for all bi and c1 in Ai. This assumes some approp- riate definition of equality of elements in each Ai and will either be apparent from) the context in which the sets are used or else will be defined. This equality is a special case of the general concept called a relation on a set. The idea of a relation is frequently encountered in set theory, but its definition tends to vary from author to author. So as to avoid confusion, the following definition is used in this thesis. Definition 2.1 A binary relation R from a set A into a set B is a subset of R of A x B. If [a, b] is in R, it is common to say that a is related to b and to write aRb. The domain of R is the set of all elements of A which are related by R to at least one element of B, thus dom R = {a in AlaRy for some y in B} . The 33133 of R is the set of all elements of B to which at least one element of A is related by R , thus range R ={b in B IxRb for some x in A} . A binary re— lation from A into A is called a relation in A. Definition 2.. Z A gr_a_p_}l A is an ordered pair A : (S,R) where S is a finite, non-null set and R is a binary relation in S. The elements of S are commonly called the vertices of the graph and the elements of R are commonly called the £C_S\Of the graph. As defined above, a graph may have ”loops". A loop is an arc [5, s] for some 8 in S. Here the arcs of a graph are oriented. The _7- arcs being oriented results from the elements of R being ordered pairs of vertices. A relation R is a symmetric relation if [a, b] in R implies [b, a] in R for all [a, b] in R. There is of course no implication that [a, b] =1 [b, a]. A relation R in a set S is a reflexive relation if [a, a] is in R for all a in S. Arelation R in S is an anti-re- flexive relation if [a, a] is not in R for any a in S. If, for a graph A 2 (S, R), R is required to be reflexive, then for every vertex of S, there is an arc which is a loop. If R is required to be anti-reflexive, then A has no loops. The definition of a connected graph is not standard in the liter- ature. So as to give a precise meaning to that idea, a series of de- finitions must be given. Definition 2. 3 Given a graph A = (S, R), a subgraph B of A is an ordered pair B = (T, Q) such that TES, OER and QET x T. As defineda subgraph is a graph. B is a proper subgraph if TCS. Definition 2.4 Given a graph A = (S, R) where S is a set of n or more elements, a path of A is a subgraph B = (T, Q) of A such that T = {ti I 1:1: n, all ti distinct} , and such that = < ' < - > . ' Q {ti’ t1+1 l l_ 1 _ n l} for n 1 Thus there is a path from t1 to t . — n If there is a path from t to tn in a graph, there need not in 1 general be a path from tr1 to t1. However, given a graph A = (S, R) with R a symmetric relation, if there is a path from s in S to t -8- in S, then there is a path from t to 5. Definition 2. 5 Given a graph A : (S, R) and a vertex 5 in S, let Js be the set of vertices of S such that Js = {t in S Ithere exists a path-f:0m s to t} . Definition 2.6 A set of vertices T58 of a graph A 2 (S, R) is open if, given any 5 in T, JSE T. Also, the subgraph (T, Q) is said to be an open subgph of A. Definition 2. 7 A graph A = (S, R) is strongly connected if, given any 5 and t in S, there exists a path from s to t. Set union and intersection are now defined since these are required in the definition of a connected graph. The union of a set {Ai| i :1, 2, - - 1' of sets, denoted by UiAi’ is the set of all elements which are in at least one of the A,. The intersection of a set 1 {AiI i :2 l, 2, ° - } of sets, denoted by niAi, is the set of all elements which are in all of the A1. If the number of sets is finite, then union may be denoted by UiAi = Al” A2” - - - UAn, i =1, 2, - ' ' , n, and intersection may be denoted by niAi : Aln A20 - - - nAn’ i :1, 2, - - - , n. The following definition is based on a similar definition from topology. Definition 2. 8 A graph A = (S, R) is not connected if there exists non—null open sets U95 and v9.5 such that qu : s and UnV = I; otherwise A is connected. Definition 2. 9 The complement A' of a graph A : (S, R) is the ordered pair -9- A‘ :(S, [SxS]-R) Thus the complement of a graph is a graph. A well known fact concerning the complement of a graph is presented in Theorem 2. 1. Since its proof is straightforward it is included here. The theorem itself will find application in the latter part of this thesis. Theorem 2.1 If a graph A : (S, R) is not connected, then the complement A' of A is strongly connected. Proof: Since A is not connected, there are at least two non-null open sets U ES and VES such that UUV = S and UnV = I . Then [ui, Vj] and [v], ui] are both in S x S - R for all ui in U and all v, in V. Moreover, for any u and u in U and for any vj in V, J k l [uk, vj] and [v], u are in S x S — R. Thus A' = (S, S x S - R) is ,1 strongly connected. A III. THE AUTOMORPHISM GROUP OF A GRAPH The automorphism group of a graph could be defined directly. However, since the concepts leading up to the definitions of an auto- morphism and of a group are also otherwise useful in this thesis, a less direct approach is used. A function F from a set A to a set B is a binary relation from A into B which satisfies the additional properties: (1) dom F i (2) if an1 and an2’ then bl = b2. The notation b : F(a) is commonly used and means an. Two functions F and G are equal if dom F : dom G and F(a) = G(a) for all a in dom F. The domain of F is extended to include functions of subsets of dom F so that the notation F(C) is used where F(C) = {b in range Flb : F(c) for all c in C Edom F}. Afunction F from A ‘to B is a function from A onto B if range F = B. A function F from A to B is said to be one-to—one if F(a) == F(x) implies a : x for all a and x in dom F. A binary operation 0 on a set A is a function F from A x A into A. A binary operation 0 on A is closed if dom F : A x A. The notation aob = c is commonly used and means c = F([a, b]) where [a, b] is inAanndcis inA. An abstract system (S, R, O) is a non-null set S, a set R of binary relations in S, and a set O of closed operations on S. Either R or O may be null, but not both. -10.. -11.. Let (S, R, O) and (T, Q, P) be two abstract systems. A function H from S into T is a homomorphism from (S, R, O) into (T, Q, P) provided that there is a relation q in Q corresponding to every relation r in R, and an operation p in P corresponding to every operation 0 in O such that (1) if [a, b] is in r, then [H(a), H(b)] is in q for all a and b in S, and for every r in R. (2) H(aob) 2 H(a) p H(b) for all a and b in S, and for every 0 in O. If T : range H, then H is a homomorphism from (S, R, O) onto (T, Q, P). Afunction H from S onto T is an isomorphism from (S, R, O) onto (T, Q, P) if and only if H is a one-to—one homomorphism from (S, R, O) onto (T, Q, P). An isomorphism from (S, R, O) onto (S, R, O) is an automorphism on (S, R, O). Since a graph A = (S, R) is an abstract system consisting of a non-null set S and a single binary relation R in S, an auto- morphism f on A is a one -to-one function from S onto S such that aRb if and only if f(a)Rf(b) for all a and b in S. The set G of all such automorphisms on a graph A 2 (S, R) is a group, as is well known. A w is a system (G, 0) consisting of a set G together with a binary operation 0 on G such that (l) the binary operation is closed; i.e., aob is in G for all a and b in G; -13- (2) the binary operation 0 is an associative operation; i.e. , (aob)oc : ao(boc) for all a, b and c in G; (3) there is a left identity element e in G such that eoa : a for all a in G; (4) for each a in G, there is a left inverse element d in G such that doa : e. . 1 . Given a group (G, o), it can be shown that (1) there exists a right inverse for each element in G; that . . -l . -l . 15, there IS an element a in G such that aoa : e for each a in G; (2) there exists a right identity element e in G; that is, aoe : a for all a in G; (3) there is only one identity element in G; (4) the left and right inverse elements are unique. The inverse of an element a is denoted as usual by a- , as in (1) above. Now it is possible to show that the set F : {f} of all auto— morphisms f on a graph A =2 (S,R) is a group (G, :3). To do this, it is first necessary to define the operation =:=. Let f1 and f2 be auto- morphisms on the graph A : (S,R). Then the operation :1: is defined by f1::(4><5)<6>. (12>(34)<56>} is of order 2 and of degree 6. A graph A = (S,R) such that R = S x S is called a complete graph. The group G of all automorphisms on (S; R; O) such that #(G) =[#(S)]1 is called the symmetric group on #(S) symbols and is commonly denoted by Zn, where n : #(S). It is easy to show that G(S, S x S): En, where n 2 #(S). -16- _17- Kagno [K2] has shown that the completrient A' of a graph A 2 (S,R) has G(A') 2 G(A). However, since Kagno considers only connected symmetric graphs without loops, the proof of this useful result is given in a more general form. Theorem 4.1 If A' is the complement of the graph A 2 (S,R), then G(A') 2 G(A). Proof: It is sufficient to show that if f is any permutation in G(A), then f is also in G(A') and if g is any permutation in G(A'), then g is also in G(A). First, suppose f is in G(A). It is sufficient to show that [a,b] is in S x S - R if and only if [f(a), f(b)] is in S x S - R for all a and b in S. Assume then that [a, b] is in S x S - R. Then [a, b] is not in R, so [f(a), f(b)] is not in R. Consequently, [f(a), f(b)] is in S x S - R. Thus if fis in G(A), then f is in G(A‘). The second part of the proof, namely, that if g is in G(A'), then g is in G(A), is identical in nature to this first part and thus is omitted. /_\. However, if the groups of two graphs are identical, the graphs need not be complements nor in any other way related, as is shown by the following example. Example 4.1 Let (S,R) and (T, Q) be two graphs, with s = T = {1, 2, 3}, and R z {[1, Z]: [1 3], [3» 11, 12, 31} : Q = {[1, 1], [1, 3], [2, 2], [2, 3], [3,1], [3, 2], [3, 3]}. Then G(S, R) 2 G(T, Q) and (T, Q) is not the complement of (S, R). The ~18- graphs and their complements are shown in Figure 4.1. All four graphs have the same group. Note that (S, R) and (S,R)' are connected but not strongly connected, (T, Q) is strongly connected and (T, Q)‘ is not connected. (a) Graph (S,R) (C) Graph (T,Q) ' (d) Graph (TiQ)' Figure 4.1. The graphs of Example 4.1. -19- Ore [01, p. 239], notes that the determination of the group of a graph which is not connected can be reduced to the problem of finding the groups of the connected subgraphs of the graph. This re- quires the notion of the direct product of groups, here defined. Definition 4.1 The direct product of the groups (G1 01), (G2, 0 ), ° ' ' (G , on) is the system (G, 0) consisting of the 2 n Cartesian product G 2 G1 x G2 x - - - X Gr1 and the operation 0 defined by “1’ f2’ {Ii} 0 [g1’ g2’ gn]2[f101gl,fzozgz'°°, fsongs] for all [f1, f2, ' ° ' , fn] and [g1, g2, ° ° ' , gn] in G. The direct product G of these groups is denoted by Gl X G2 X ' ' ' X Gn. It is known that the direct product of groups is a group.. The determination of the group of a graph in terms of its connected subgraph is detailed in the next theorem. So as to make this next theorem more comprehensible, it is preceded by the following example. - Example 4. 2 Find the automorphian group of the graph A (S,R), where s = {1, 2, 3, 4, 5, o, 7, 8, 9, 10, 11] , and II ,p. o1 R {12. 11. 12. 31. 1 . 1, is. 41, 16. 71. 17. 61. 18. 91. [9. 81. [9. 101, [9, 11], [10, 11], [11, 10]}. This graph is shown in Figure 4.2. Figure 4. 2 The graph of Example 4. 2. -20.. The graph A can be decomposed into the graphs A :(s, R), A = (s , R ), and A3 {(53, R3)where sl : {1, 2, 3}, 1 1 1 2 2 2 R1: {[2, 1], [2, ISUIZ s = {4, 5, o, 7} , R2 : {[4, 5], [5, 4], [6, 7], [7,8],} —{8,9,10,11},ahdR : {[8, 9], [9, 8], [9, 10], [9, 11], [10,11], [11, 10]}. Note that s = LJisi and R : UiRi, i-: 1, 2, 3, and 81 n sj : - foriijandi,j2l, 2, 3. The graph A R2) can be further decomposed into 2: isomorphic graphs, A212 (521’ R21) and A22 2 (822’ R22) where 521 = {4, 5}, R21:{[4, 5,] [5, 43-52 :,{6 7}, ahdRZ Z=,{[o 7], [7, 8]] . An automorphism of A is simply a re-arrangement of the vertices of A which "leaves the figure unchanged. " But such changes can be determined piecemeal for each A1, A2 and A5. Thus G(A1)= {(1) (2) (s). (13)} G(AZ): {(4) (5) (6) (7). (45). (67). (45mm). (46)(57) (47)(5o)} G(A3): {(8) (9) (10) (11), (10, 11)}. Moreover, any composition of permutations, one from each of G(Al)’ G(A2)’ and G(A3) is still an automorphism of A, and in I fact there are no other automorphisms of A. Thus G(A) 2 G(Al) x G(A x G(A3)° 2) These intuitively obvious results are now stated formally in the next theorem. A similar statement is made by Ore [01, p. 239], but once -31- again, for symmetric graphs. The proof of the theorem is for arbitrary R, and since the proof is long, it will be omitted. Theorem 4. 2 Let the graph A 2 (S, R) be composed of the subgraphs I Al : (81’ R1), A2 : (52’ R2), I I I ’ n n n such that z ': g ..., , A (Uisi,UiRi),1 1, , h and Further, let the subgraph A12 (Si, R ), i 21, 2, - - - , n be composed of the connected subgraphs A.-:(S.-, R--)3j:1: 2: ...,m.2 1] 1] 1] 1 such that the graphs Aij for j 2 l, 2, ° ° ° , mi are isomorphic to each other but not to other subgraphs of A, and such that A. :( ..S.: ...R)’ I :1: 2: ...; m.) 1 UJ 1.] UJ 1J J and S. n S. 2 for Xfy and x, y 2 l, 2, '°', 111,. Then G(A) 2 G(A ) x G(AZ) x X G(A ). 11 1 This leaves the problem of finding the group of a graph composed only of isomorphic subgraphs. Frucht [Fl] has stated a theorem which can be used to find these groups. For completeness, that theorem is presented here in a restated and more general form. The theorem uses -23- the concept of simply isomorphic permutation groups. Two iso- morphic permutation groups are simply isomorphic if they are of equal degree. Since the proof of this theorem is lengthy, but otherwise not complicated, and since such proofs are commonly omitted, this proof is omitted here. Theorem 4. 3 Let A 2 (S, R) be a graph composed of the connected subgraphs A1: (51’ R1” A2 2 (52’ R2)’ ’ Am : (Sm’ m) such that the graphs Ai’ i 2 l, 2, - - - , m are all isomorphic and such that A : ’ o - 9 . : 9 Z! . . . 7 ’ (U15i UlRl) 1 l m and sins]. : for if-jandi, j: 1, 2, m. Then the groups G1 = G(Ai) are all of the same degree, of the same order and so they are simply isomorphic one to another. If h 2 #(Gi) and n 2 #(Si), then G(A) is of order m1 hm and of degree mn. The elements of G(A) can be described in the following way. Let 5.: 5.. S.» '°', s_ fori212, "', m. Formth mat' 1 {11 12 in}, ’ e rix S11 S12 ' ' ’ S1h S S o o o S 21 22 2 M = “ ‘iml SniZ I I I Sm: An element of G(A) is any permutation of the rows of 1\/I followed by any permutation in G(S,). 1 Relying on these theorems, a technique is now developed which simplifies the task of finding the group elements of a graph. Definition 4. 2 Given a graph A 2 (S, R), let FS 2 {uinS I (s, u) is inR} , "rt : {v inS | (v, t) is in R}. FS is the set of vertices u in S with arcs from s to u and Tt is the set of vertices v in S with arcs from v to t. FS and Tt are not independent for a given graph because Tt 2 {s | t in F8} and FS:{tls inTt}. Definition 4. 3 Given a graph A 2 (S, R) with s in S, let 11 1t 2 0(3) 1(8) = # (T )- If R is symmetric, then FS 2 T8 for all s in S and 0(5) 2 i(s). These two numbers are commonly called the degree of the vertex 5 when R is symmetric. For R in general, 0(5) is the number of arcs from s to vertices in the graph and i(s) is the number of arcs from vertices to 5. Definition 4. 4 Given a graph, let Ok2{sIo(s) k}, k20, 1, 2, I]. ={t (i(t) 1}»1'“ Thus OR is the set of vertices in S having "out degree" k and H I O 5—: N Ij is the set of vertices in 5 having "in degree" j. Note that UkO 2 S, k Okn Of 2 ”I forkf-fl , UjIj 2Sand Ijnlm: forjfim. If a graph A 2 (S, R) has a subset XCS such that FX 2 for -g4- all x in X, then 0(x) 2 O and X 500- If a graph A 2 (S,R) has a subset ch such that Ty : for all y in Y, then i(x) = 0 and Y 510. The automorphisms of the graph A 2 (S,R) are functions from FS onto F5, from T8 onto TS, from OR onto Ok and from 1j onto 1]. as is shown by the following theorems. Theorem 4. 4 Let A 2 (S,R) be a graph. If f is in G(A), then for all 0k and 1j defined by (S,R). Proof: Suppose i(a) 2 j for some a in S. Then there are vertices yl, yz, ' ° °, yj in S such that [yi, a] is in R, for i 21, 2, ' ' ° , Since f is in G(A), [f(yi), f(a)] is in R. Thus i[f(a)]:j. If there is a b in S such that b #- f(yi) for i 2 l, 2, ' ' ° , j and [b, f(a)] is in R, then [f-1(b), a] is in R, hence f-1(b) 2 y].L for some i=1, 2, ° ° - , j. But this implies b 2 f(yi), a contradiction... Hence i[f(a)] 2 j and f(a) is in I]. Since this is true for any a in S such that i(a) 2 j, then f(I.) 2 I]. The proof for Ok is identical except for obvious changes. A According to well known set theory theorems, f(U 1A1) = f(Al)Uf(AZ)U U f(An). g( n i18m) -- g(Blmngm- - . nssm), where f is a function defined on A1, i 2 l, 2, ' ' ° , n, and g is a function defined on Bi, i :. 1, 2, - - . , m. These relations. are implicit in the proof of the next theorem and are also used in the proof of theorems in the latter part of this section. -35- Theorem 4. 5 Let A 2 (S,R) be a graph. If f is in G(A), then for all s and t in S such that Fs 7f and Tt f i . Proof: Suppose b is in F3. Then [a, b] is in R, so [f(b), f(a)] is in R. This implies that f(b) is in Ff(a)’ so f(Fa) E Ff(a) -1 Suppose c is in F Then [f(a), c] is in R and [a, f (c)] is f(a). -l in R because f is in G(A). This implies that f (c) is in Fa’ so {-1 (F )EFa, orF Cm? ). But thenf(F ):F f(a) f(a) - a a f(a). The proof for Ta is similar. A The requirements FS )5 ’I and Tt # in Theorem 4. 5 are not restrictive since 0(5) 2 O or i(s) 2 O and the group functions of these vertices are considered in Theorem 4. 4. The following theorems consider the converse situation from that of the previous two. It is assumed that a permutation on the vertices of the graph is given, and sufficient conditions for this permutation to be an automorphism of the graph are given. Theorem 4.6 Let A 2 (S,R) be a graph and let f be a per- mutation on S. If for all a in S such that Ta 2 , then f is in G(A). Proof: To show that f is in G(A), it is sufficient to show that if [b, a] is in R, then [f(b), f(a)] is in R and if [c, a] is not in R, then [f(c), f(a)] is not in R for all a, b and c in S. Suppose [b, a] is in -39,- R. Then b is in T , so that f(b) is in f(T )2 T. . Hence a a f(a) [f(b), f(a)] is in R therefore, [1), a] in R implies [f(b), f(a)] is in R. Suppose [c, a] is not in R. Then c is not in Ta. Since f is a permutation on S, c not in Ta implies f(c) is not in f(Ta). But f(c) not in f(Ta) 2 T implies [f(c), f(a)] is not in R. Thus [c, a] not in f(a) R implies [f(c), f(a)] is not in R. Therefore, f is in G(A). A Theorem 4. 7. Let A 2 (S,R) be a graph and let f be a permutation on S. If for all a in s such that Fat .5 , then f is in G(A). Proof: The proof of this theorem is identical to that of Theorem 4.6, except for obvious changes. A Theorems 4.6 and 4.7 constitute the converse of the theorems in Theorem 4. 5. However, the converse of Theorem 4. 4 is not true as is shown by the following example. Example 4. 3 Let A : (s.R) be the graph 5 : {1, 2, 3} , R z {[1, 1]. [1, 2], [2, 1], [2, 3], [3. 2]}. For this graph, 01 : {3}, O2 : {1, 2 , 11: {3} and 12 z {1, 2}. For the permutation f = (12), {(1) : I and £(1 2’ 1 1 1:1 2 2° Yet G(A) 2 I and f is not in G(A). A simple combination of Theorems 4. 4 and 4. 5 yields the following theorem. Theorem 4. 8. Let A 2 (S, R) be a graph. If f is in G(A), then v) )7] {(1921an) - f(a)” 1.. f(Tanj) = Mmj. f(FanOk) = ”amok, f(TbnOk) =—. Twr'Io for all I]. and Ok defined by A and for all a and b in S such that Fa )é ‘ and Tb # , and assuming f(i ) 2 . Proof: Since all four statements have essentially the same kind of proof, the proof of only one is given. f(TbnOk) = f(Tb)n(Ok) = Tf(b)n0k. A Of all the theorems in this section, the following theorem yields the most powerful device for calculation of the group elements of a graph. Theorem 4. 9 Let A 2 (S,R) be a graph and let f be a permu- tation on S. If f(Fan 1].) 2 (“Ij for all 1j defined by A and for all F f(a) a in S with the special provision that f(i ) 2 , then f is in G(A). Proof: Use is made of the set-theoretic properties of functions of the union and intersection of sets as given on page 24. Ff(aj)n1 as stated, then f[Uj(Fan 11.)] f[Fan (UjIjH f(FanS) If f(Fan Ij) U. {(12 n1.) 1 a 1 While H hq D (I) H 1T] ..., -28— Hence f(Fa) 2 Ff(a) and by Theorem 4. 7, f is in G(A). A Theorem 4. 9 is true for the other three intersection equations, that is for H f(Tbn IJ.) f(Fan 0k) f(Tbn ok) = Tf(b)n0k. Tf(b)n1j, ll Ffla)!‘ ok. The use of Theorem 4. 9 in the determination of group elements of a graph is illustrated by the following example. Example 4.4 Let A = (S,R) with s :{L 2, 3, 4, 5, 83am R={[1, 2], [1, 3], [2, 2], [2, 4], [3, 4], [3, 5], [4, 4], [4, 8], [5, 1], [5, 8], [8, 2], [8, 8]} . Table 4.1 shows a table of all Fan IJ, and Fan Ok' 11:{1, 3, 5} 13 :{2, 4, 8} oZ : 5 F1 :{2, 3} 3 2 2,3 F2 = {2, 4} 2,4 2,4 F3 = {1, 5} 5 4 4, 5 F4 = {4, 8} 4,8 4,8 F5 = {1, 8} 1 8 1,8 F6 : {2, 8} 2,8 2,8 Table 4.1. An Intersection Table for Example 4.4 It is apparent from the 11 column or the 13 column of the table that only cycles starting with 13, 15, 35, 53, 51, 31, 24, 26, 46, 64, 62, and 42 need be considered for permutations in G(A). This isnot apparent from the O column, and while all permutations in G(A) could 2 -g9- be determined from the O2 column, it is much easier to use the 11 and 13 columns. For example, suppose a possible permutation is to have a cycle (1). Then (1) implies (2) and (3), (2) implies (24)or (2) and (4). This and the rest of the analysis for (l) is carried out in Table 4. 2, with : meaning "implies", 1 meaning "impossible", and C indicating the order in which the closures are determined. (1) Cr : (2) Cg, (3)Cq (6) Ch : (2)C1., (6)Cb (3) C (5) Cr, (4)C (2) : 241 p o k (4) 461 (2) Cf : (2) CC, (4)Cd (4) C. : (4)C . (6)C. (5)C :(1)C , (61C J a 1 n I m (6) : 261 Table 4. 2. Analysis of cycle (1). Thus the identity is the only element of G(A) with the cycle (1). The above analysis can be done for any cycle consisting of just one element of S and always yields the identity permutation. Thus the identity element is the only element in G(A) and so any other element in G(A) permutes every vertex of A. Consider the analysis for the cycle starting with 13 as carried out in Table 4. 3, with closure order omitted. 13C : 35C 24C 46C : 46C 62C 241 : 261 62C : 62C 24C 24C : 24C 46C 35C : 51C 46C 461 :42 661 51C: 13C 62C Table 4.3 . Analysis for the cycle starting with 15. -50- From Table 4. 3, it is apparent that f :: (135M246) is in G(A). Consider next the cycle starting with 15. as carried out in Table 4. 4. 15C: 31C 36C 64C : 64C 26C 26C : 26C 42C 31C : 53C 42C 42C : 42C 64C 53C : 15C 64C Table 4. 4. Analysis for the cycle starting with 15. From Table 4. 4, f 2 (153) (264) is in G(A). Since this exhausts all possible cycles to be considered, G(A) ={1, (135)(248), (15.3)(2640, A computer prOgram was written1 which will calculate the group of a given graph. Since it is interesting to compare the method of this program with the technique of Theorem 4. 9, the method used in this program is described using the. following definitions. Definition 4. 5 Given a graph A 2(S,R) of order n, the connection matrix C(A) is the n x n matrix C(A) 2 (a. .1. where 1) a,,:l if [5,, s.]is inR, 1.1 1 J a,,20 if [5,, s,]is not inR 1J 1 for s, and s. in S. 1 Definition 4.6 Given a set S of order n and a permutation f on S, the permutation matrix P(f) is the n x n matrix P(f) 2 (b]) where 1 b,, 2 1 if and only if, f(s,) 2 s. for s, and s. in S, and b,, 2 0 otherwise. 1] 1 J 1 J 1J This program was written by lVlrs. Elizabeth Phillips of the Computer Laboratory at Michigan State University. —31- Note that P(f) 2 P'(f-l) where C' is the transpose of C. A permutation f on S is a group element of G(A) of the graph A 2 (S,R) if and only if P(f) ° C(A) ° P'(f) 2 C(A). The computer prOgram presently in use is given C(A), generates all possible permutations on S. and forms this matrix product. I or the graph of Example 4. 4, there are #(S)! 2 6'. 2 720 permutations to be tested. For a graph of order 6, the present computer program requires 18. 75 minutes of computer time on a Control Data l60-A digital computer. The same test can be used to check the pernqutations determined by the method of Theorem 4. 9. Since not all possible permutations need be considered, the task of finding group elements of a graph is con- siderably simplified. In fact, use of Theorem 4. 9 allows hand calculation of group elements where the order of the graph is too large to allow calculation by a direct method with a computer. V. SPECIAL GRAPHS Having considered the automorphism group of a graph, it would seem reasonable to ask about the effect of the group permutations on the arcs of the graph. The following definition establishes the basis for several ideas about functions of arcs of graphs. Definition 5.1 Given a graph A 2 (S,R) and its automorphism group G(A), let F(A) be the set of permutations on R such that, for each g in G(A), fg is in F(A) if and only if fgla: b] = [g(a), g(b)] for all [a, b] in R. Theorem 5.1 There is a homomorphism from G(A) onto F(A). Proof: It is sufficient to show that there exists a correspondence TT associating elements of F(A) with elements of G(A) such that (1) TT is a function from G(A) into F(A). (2) w is an operation preserving function, where in each system the single binary operation is taken to be composition, so that H(g1g2)2 H(g1)n(gz) for all g1 and g2 in G(A). (3) TT is an onto function, i. e. , for every f in F(A) there is a g in G(A) such that Tr(g) 2 f. Let TT be defined by 7T(g) 2 fg if fg[a, b] 2 [g(a), g(b)] for all [a, b] in R. That TT is function from G(A) onto F(A) follows directly from the way in which TT is defined. _32. _35_ To show that 11' is operation preserving, let 71(g,) 2 f, _, 1 1 for i=1, 2, 3 and let glgZ 2 g3. Then 11(g1g2) 2 7T(g3 )2 f3, and fsla, bl = 181.3(9), 83(b11 = 1818201): 8121.2in for all [a, b] in R. Let gz(a) 2 c, g2(b) 2 d. [c, d] is in R for all [a, b] in R. So f3[a, b] 2 [g1(C). g1(d)1=f11<‘-: d1 Thus 7(g3) 2 Tr(g1) 11(gz) and so 11(g1g )2 17(g1g2): H(g1)n(g2).A It follows from Theorem 5.1 that F(A) is a group and it Inight seem at first that F(A) would be isomorphic to G(A). This is not so in general, as is shown by the following example. Example 5.1 Let s = {1, 2, 3, 4} and let R = [1, 2], [2, 1] Then G(A) .—. {1, (12), (34), (12)(34)} and 7T(I) = e(34) = ([1, 2])([2, 1]), and Tr(12) 2 11(12)(34) 2 ([1, 2] [2, 1]). Thus 11 is not a one-to-one function. This is not a short-coming of TT, but rather of A. In this example, the graph has two perfectly isolated vertices. A perfectly isolated vertex s is one for which 0(5) 2 0 and i(s) 2 0, The condition for it to be a one -to-one function and therefore, an isomorphism from G(A) to F(A) is given in the following theorem. Theorem 5. 2. Let A 2 (S,R) be a graph and let 11 be the function as defined in Theorem 5.1. If A has less than two perfectly isolated vertices, then TI’ is an isomorphism from G(A) onto F(A). Proof: It has been shown in Theorem 5.1 that TT is a homomorphism from G(A) onto F(A). Thus it is sufficient to show only that 17 is a -3-1- one-to-one function; i.e. , if F(gl) 2 17(g ), then g1: g for all gland 2 2 ga in G(A). 1f Tr(gl) 2 77(g2), then [g1(a), g1(b)] 2 [g2(a), gz(b)] for all [a, b] in R. Thus gl(a) 2 gz(a) and g1(b) 2 g (b). 2 Suppose A contains no perfectly isolated vertices. Then every vertex in S appears in some element of R, and gl(x) 2 gz(x) for all x in S, either because x 2 a or because x 2 b for all [a, b] in R. Therefore, £11 : g2- Suppose A contains exactly one perfectly isolated vertex 5 in S. Then g1(s) 2 gZ(s) 2 s for all g1 and g]Z in G(A). Again, either gl(a) 2 g2(a) for all a in S - {s} or g1(b) 2 g (b) for all b in S - {s} . 2 Thus, g12 g2. A From Theorem 4.1 a graph A and its complement A' both have the same group, that is G(A) 2 G(A'), a fact pointed out by Kagno [K2] for non—oriented graphs. From Theorem 2.1, either A or A' has no perfectly isolated vertices. Assuming A has no perfectly isolated vertices, A' may or may not have isolated vertices. Thus, G(A') is at least homomorphic to F(A') and #[F(A')]l #- [F(A)]. Suppose A 2 (S,R) is a graph with k perfectly isolated vertices. Let K be the set of perfectly isolated vertices. Let B 2 (S, RU(K x K)) . Then three cases are of interest. (1)1f 2k 2 #(S), then G(A) 2 G(B). (2) If 2k 2 #(S), and R f- (S - K) x (S - K), then G(B) 2 G(A). (3) If 2k 2 S and R 2 (S - K) X (S - K), then G(A)CG(B) and G(B) is the group as given by Theorem 4. 3. ,— - 35- Since an automorphism group F(A) does exist for the vertices of A 2 (S,R), it would seem that some relation or operation on R is preserved by the elements of F(A). This is indeed true as shown by the following definition and theorem. Definition 5. 2 Let A 2 (S,R) be a graph, let x, y, z be in S and let a, b be in R. Then arlb if a 2 [X, y] and b 2 [z, y] aer if a 2 [y, x] and b 2 [y, z] ar3b if a —- [x, y] and b 2 [y, z] The relations thus defined have many interesting properties in themselves. For example, r1 and r2 are symmetric relations. A relation r is said to be transitive if arb and brc implies arc; r1 and r2 are transitive relations. The fact that these relations are preserved by F(A) is presented in the next theorem. This theorem is presented without proof since the form of the proof is the same as the form of the proof given for Theorem 3.1. Also the important part of the proof of the following theorem is supplied by Theorems 5.1 and 5. 2. Theoretri 5. 3 Let A 2 (S,R) be a graph and let B 2 (R, {$1, r2,r3'} ) be a system. Then the elements of F(A) are automorphisms on B. It is interesting to note that B may be thought of as graphs. If R is symmetric, then r12 r2 2 r3 2 r and B 2 (R, r) is what Ore [01, p. 245] calls the interchange graph B 2 1(A). Sabidussi [S4] calls B the graph derivative of A. Both Ore and Sabidussi present several results for these non—oriented graphs . The n-uiinterchange, denotedtntino4)o£the graph.A nsthe ') graph An where A 2 1(A), A 2 1(A ) 2 I[I(A)] 2 15(A), etc. Under 1 2 l certain specified conditions on A not developed here, In(A) exists, and F[In(A)] is homomorphic to A for all n. Thus, an entire family of homomorphic groups is generated by In(A). Another special type of graph that has received some attention in the literature is the graph which is the product of two or more graphs. For‘example, Sabisussi [S3] has presented a detailed study of the product of non-oriented graphs without loops. Much of the work of Sabidussi can be extended to the more general oriented graph with loops, thus graph product definitions are given which extend those of Sabidussi to this more general case. In the following definitions, it is convenient to use the concept of the projection p, from the Cartesian product of sets 1 onto its i-th coordinate, so that for any 5 2 [s], 52’ ' ° ° , s,, - ' - , s ] 1 11 ms XS x--- XS. X’" XS , p,(s)2 5, ins. fori21, 2, ---, n. In 1 2 1 n 1 1 1 the following definitions 1 2 {1, 2, - - - , n} is assumed to be the index set. Definition 5. 3 Let {Ai : (Si, Ri) | i in I} be a set of graphs. The Cartesian product AC of these graphs is the system (S, RC) where. (1) S28 XSZX'°°XS; 11 l (2) for a, b in S, [a, b] is in RC if and only if there exists a k in I such that [pk(a), pk(b)] is in Rk’ and pj(a) 2 pj(b) for all j in 1-{k}. -57- Definition 5. 4 Let {Ai 2 (S. 1, R1) I i in I) be a set of graphs. ) wher e The direct product A of these graphs is the system (S, R d d (1)S:SIXSZX"’ xSnz (2) for a, b in S, [a, b] is in R if and only if there exists a d non-null subset K51 such that [pk(a), pk(b)] is in Rk for k in K, and pj(a) 2 pj(b) for all j in I - K. Thus these products of a set of graphs are graphs possibly with loops and not necessarily non-oriented. This suggests the following problem. Given a graph A 2 (S,R), is it possible to factor A into two (or more) graphs A 2 (S R1), A 2 (S , R2) such that A is the product 1 1’ 2 2 of A1 and A '? At least a partial answer can be given to this question. 2 To etnphasize the problem, the following example is presented. Example 5. 2 Let A1 2 (81, R1 with 51: {1, 2}, R12 {[1, 2]}, s2 = {3, 4, 5} and R2 2 {[3, 4], [4, 3], [4, 4], [5, 4], [5, 5]} . Then the Cartesian ) and AZ 2 (52, R2) be two graphs product is AC 2 (S, Rc)’ and the direct product is A 2 (S, Rd) where d s e {[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]}, and letting u 2 [1, 3], v 2 [1, 4], w 2 [1, 5], X 2 [2, 3], y 2 [2, 4], z 2 [2, 5], then RC 2 {[u, v], [u, x], [v, u], [v, v], [v, y], [w, v], [\v, w], [\v. a), 1x. 3']. 1y. x]. hr. 3']. [2. y]. [2. 2]} Rd = Rcu {[w. y]. [n x]. Lu. 3]}. Actually, the two graph products defined are not independent, for given one it is always possible to determine the other directly. Also, the existence of certain arcs in the graph product is determined by the existence of certain other arcs in the product. The following theorem exhibits these details. Theorem 5. 4 Let AC 2 (S,R ) be the Cartesian product and c let Ad 2 (S, Rd) be the direct product of the graphs A 2 (S , R ) and l l l : . ' ' ad I: ' .. A2 (82’ R2) Letuandvbelns1 n vxandxbe in S2 (1) If [u, w] Rc[u, x] then [v, w] RC[v, x] and [v, w] R v, X] d1 (2) If [u, w] RC[v, w] then [u, x]RC[v, x] and [u, x]R v, x] d[ (3) If [11, w]RC[u, X] and [u, x]RC[v, x], then [u, w] Rd[v, X] Proof: The first two statements follow directly from the definitions of Cartesian and direct products. Statement (3) is true because from [u, w]RC[u, x] it follows that w R2 x; and from [u, x]RC[v, x] it follows that uRlv. Therefore [u, w]Rd[v, x]. A Theorem 5. 4 can be generalized to any two dimensional cross section of any product of more than two graphs. Furthermore, it is much easier to draw the product graph when the results of Theorem 5. 4 are used. The problem of factoring a graph A 2 (S,R) will be considered assuming the factors A12 (8 , R ) and A 2 (S , R l 1 2 2 2) are both Without loops. This assumption simplifies the enumeration of arcs in A, as given in the following theorem. Theorem 5. 5 Let A12 (51, R1) and A2 2 (82’ R2) be two graphs, both without loops. Then # (R) = #(51) #(R2) + #(sz)#(R1). # (S) #(SI) #(52) .59- where A 2 (S, R) is the Cartesian product 01A1 and AZ. Proof: Clearly #(S) 2 #(S ) #(S ). Next [i, x]R[i, y] for all )#(R ) i: 1, 2, ' ° ' , #(SI) and for all [x, y] in R2, for a total of #(S1 2 such elements in R. Similarly there are # (SZ)#(R1) elements (7., i)R(w, i) in R. A Theorem 5. 5 provides a basis for considering the problem of factoring a graph. If the graph A 2 (S, R) is of p.rirne order, then no factoring is possible. So assume #(S) 2 mn. Then a necessary condition for (S,R) to be the Cartesian product of (51, R1) and (52‘, R2) is that #(S 2 n, and l) m. #(s,) mx + ny 2 #(R) where x 2 #(R ) and y 2 #(R ). Thus it is necessary to find integral 2 1 solutions to this equation with the additional restrictions that O E y E n1(m - l) and 0 _<_ x : n(n — 1). This is a Diophantine problem and has solutions if and only if the greatest common divisior of m and n divides #(R). Let (1 2 (m, n) denote the greatest common divisor of m and n. Then if d divides #(R) all solutions are given by — ‘l‘ n X -— X't‘ + a t . _ m 3 — Y'“ - g t where x 2 x* and y 2 y* is any particular solution and t is any integer, positive, negative, or zero. Several methods exist for finding X* and y*. The requirements 0 < y < m(m - l) and O < x < n(n-1) assure a finite number of solutions. -40- Although only the product of pairs of graphs is considered from Theorem 5. 4 on, these results can be extended to products of more than two graphs. However, the Diophantine problem in more than two variables is complicated. Also, in determining the factors of a graph, all possible factors of the order of the graph may be considered and even if a set of factors is found that gives a solution to the Diophantine equation, it is still necessary to determine the individual vertex sets and their arcs for each graph in the product. Primarily, the Diophantine solutions will indicate what factors are not suitable for the factoring of a graph. A third type of graph of special interest is the self-complementary graph. The self-complementary graph is defined as follows. Definition 5. 5 A graph A 2 (S, R) is self-cmnplementary if there is a permutation h on S such that [a, b] is in R if and only if [h(a), h(b)] is not in R. The permutation h is said to leave the graph self-complementary. The set of all such permutations is denoted by H(S,R). The connection matrix C(A) exhibits several useful properties of self-complementary graphs. One of the more useful properties is this. For a self-complementary graph A 2 (S,R), a permutation h on S is 1nH(A)1f and only if Cab 2 Ch(a)h(b) for all cab in C(A). Here, if .C 2 0, then 3 21, and if c 21, then 3 2 0. That this is true is shown as follows. First assume h is in H(A). Suppose Cab 2 1 so that aRb. Then [h(a), h(b)] is not in R so that Ch(a)h(b) 2 0. Then suppose -4]- c21b 2 0 so that [a, b] is not in R. Then [h(a), h(b)] is in R so that Thus, for h in H(a), c — 1 f ’ . ° . . ab Lh(a)h(b) or all cab in C(A) Next, assume c, 2 ab Ch(a)h(b) for h a permutation on S and for all cab in C(A). Thus, if [a, b] is in R, then [h(a), h(b)] is not R or if [a, b] is not in R, then [h(a), h(b)] is in R. Since this is true for all a and b in S, h is in H(A). Several other features of self-complementary graphs are obvious in light of the above discussion, namely: (1) Every permutation h in H(S, R) leaves no element 5 in S fixed. This means that h(s) 2 5 Suppose it were true that h(s) 2 s for some sin S. The c 2 c f ' A . ss h(s)h(s) or CSS 111 C( ) But this is impossible, as shown by the above discussion. (2) A self-complementary graph A has an equal number of ones and zeros on the main diagonal of C(A). This is true because aa h(a)h(a)for Caa m C(A) and all a 1” 5° (3) A self-complementary graph A 2 (S,R) is of even order. This follows directly from statement (2), above. (4) A self-complementary graph A 2 (S,R) has an equal number of ones and zeros off the main diagonal of C(A) This follows from the above discussion. (5) Every cycle of a self-complementary permutation h is of even length. Suppose some cycle of h were of odd length, say 1 2’ --°, S2n+l)° Then for c in C(A), c . s s m m l 2 l 2 for m even and c —— 2 s s 2 c m m for m odd. 1 l 2 h (Sl)h (52) 2 '1 2 +1 But h nT(s )2 s andh n (s c . — c 2 + 2 + h n 1(sl)h n 1(52) 5182 $152 which is impossible. Thus, all cycles of h are even in length. I These properties of self-complementary graphs are used in the theorems presented. The following theorem is unusual in that it proves the existence of a self-complementary graph for any even positive, integer. Theorem 5. 6 If n is an even positive integer, then there exists a self-complementary graph of order 11. Proof: The proof consists of constructing the self-complementary graph (S,R) for which h 2 (12)(34), -_ - - , (n-l, n) is in H(S,R). This is done by filling in the entries of C(S,R) by letting cn .2 1 and 1—l,J Cm j: 0 for m2 2, 4, 6, --°, nandj2l, 2, ---, n. Then consider c.“ and C , , . IJ h(1)h(J) c..,thenc,.2e . ,L 11 11 11(1)h(1) The next theorem presented depends on two relationships Since the latter entry is in the row above or below Hence (S,R) is self-complementary} A between the elements of H(S,R) and G(S,R), namely: (1) If h and h are in H(S,R) for the self-complementary l 2 graph (S,R), then hth is in G(S,R). This is true because c ' 2 Z 2 c for all c in C(S,R). , I- . 1‘. 3 h . h . , . . Si 5] h1(51) 1(SJ) hl 2(81) hlh2(sj) 518] (2) If h is in H(S,R) and g is in G(S,R) for the self—cmnplenientary graph (S,R), then hg is in H(S,R). This is true because for all c in C(S,R). 5,51 1 or . 2 These two properties show that [H(S, R)] E G(S,R) and H(S,R)G(S,R) 5 H(S,R). It is necessary to define normal subgroup to complete these results. A subgroup A of a group B is said to be a normal subgroup if x—IA x 2 A for all x in B. Theorenn 5. 7 If (S,R) is a self-connplementary graph, then G(S,R) U H(S,R) is a subgroup of the symmetric group on S; the order of G(S,R) is equal to the order of H(S,R) and G(S,R) is a normal sub- group of G(S,R)UH(S,R). Proof: It is first sufficient to show that HZ(S,R) 2 G(S,R) 2( and H(S,R)G(S,R) 2 G(S,R)H(S,R) 2 H(S,R). To show that H S,R) 2 G(S,R), observe that if h , h and h} are in H(S,R), then 11 l 2’ 1h2 2 hlh3 1mp11es , 2 hZ 2 h]; thus the order of H (S,R) is greater than or equal to that of H(S,R); hence the order of G(S,R) is greater than or equal to that of H(S,R). But since H(S,R)G(S,R)EH(S,R) then the order of H(S,R) is greater than or equal to that of G(S,R) by a similar argument. But then the order of H(S,R) is that of G(S,R), so that 2 #[H (S,R)] : #[G(s,R)] : #[H(S,R)]. Hence HZ(S,R) 2 G(S,R) and G(S,R)H(S,R) 2 H(S,R)G(S,R) 2 H(S,R). Next, that G(S,R)UH(S,R) is a group follows by a simple verification of the group postulates. -44- Finally, since gG 2 G 2 Gg for any g in G and hG 2 H 2 G11 for any h in H, then G is a normal subgroup of GUH. A The following example is intended to illustrate some of these ideas. Example 5.3 Let s : {1, 2, 3, 4} and 1et 13,]: {11. 21. [1, 31. [1. 41. [2. 21. [3. 11. [3. 21. [3. 31. [3. 41} . R z {[1, 2], [1, 3], [1, 4], [2, 2], [3, .3], [4, 1], [4, 2], [4, 3]] , R‘ = {[1, 21. 11. 31. 11, 41. [2. 11. 12, 21. 12. 31. [2. 41. 13, 31} Then A12(S. R 2 (S, R ) are self-complementary ), A 2 (5, R2) and A3 3 graphs with H(Al) : {(12)(343 G(Al) : {1} H(AZ) = {(12)(34), (1:3)(24), (1234), (1342)], G(AZ) : {1, (23), (14), (2,3)(14)}, H(A3) : {(13)(24)} G(Ap : {I}. As a closing topic for this section, the problem of producing graphs with a given group is considered. Specifically, the problem is this. Given a permutation group F of degree 11, find a graph (S,R) of order n such that the automorphism group G(S,R) 2 F. Kagno [K2] has shown that there is no non—oriented graph whose group is the cyclic group generated by a single cycle. If oriented graphs are used to realize the graph having a given group, then this cyclic group generated by a single n—cycle always has a graph as shown by the following theorem. Theorem 5.8 If F is the cyclic group generated by the permutation (l, 2, ' ‘ ' , n), then there exists a graph A 2 (S,R) such that G(A) 2 F. Proof: The proof consists of specifying C(A) 2 (a,,) for A 2 (S,R) 11 so that G(A) 2 F. Let a_, 21f0ri2l,2,"',n—l 1, 1+1 a :1, n, l a 2 a , 2 2 a , ll 22 rm and let a,, 2 0 otherwise. First, (1, 2, ° ' °, 11) is an automorphism of (S,R). This is true because 51.. 2a_ _ for i, ' n, then 77(1) 2 i + k - n). Then 77(i +1) 2 i + k +1, since a], 1+12 ai + k, n(i + 1) and then the £le 1 in row i + k is at column i + k +1. Therefore, 71(1) 2 l + k, 77(2) 2 2 + k, k etc. But thennr-(l, 2, °", 11) is in F. A L4,,- Actually, it is possible to specify a graph for a more general type of group, namely for a special cyclic group, where a cyclic group on n symbols is the group generated by all powers of a single permutation on n symbols. The particular cyclic group and a graph for this group are given by the following theorem. Theorem 5. 9 Let F be the group of degree n generated by the permutation 77 2 plp‘Z - - - pq where the pi, i 21, 2, " ', q are the cycles composing 77. Let the length of pi be aifor i 21, 2, ' ' ' , q. If (ai, aj) 2 l for i 2 j and i, j 21, 2, ~- - ,q, there is an oriented graph A of order n such that G(A) 2 F. Proof: First, G can be written as fhe product of the subgroups ° , G where Gi is the cyclic group generated by p , i: 1, 2, .. -, q. This is proved by observing that pi is in G, since 1 . . - 77 2 p, for some integer k, and for 1 2 l, 2, - - -., q. Next, the order of 1 1 G. is a,, hence the order of the product G G -- - G is a a - - - a ; 1 1 l 2 q 12 q moreover, G G. ° ' ' G is a group since G.G. 2 G.G. for 1 2 q 1 J J 1 i, j 21, 2, " ' , q. Finally, the order of G is the same as that of GG."'.G- l 2 q __ ... ’ -_ 7 ... Let pi (50,11, 81, p.’ sr _ l, p.) for 1 21, 2, , q. 1 1 p, 1 1 Then the graph Ai : (Si' R1) given by [Sj,p.’ sj +1(r ), ]1n R 1 P. 1 1 for j 2 O, l, "', rp - 1 has G, 2 G(A,). Moreover, the graph . 1 1 1 has for its group G(A) 2 G(Al) x ' ' ' x G(Aq) 2 G. A On the basis of the previous two theorems, it would seem reasonable to attempt to prove that a graph always exists for any cyclic group. While no such proof is given in this thesis, the following example tends to support the conjecture that a graph exists for any cyclic group. In. this example, the given group is not of the type covered by the previous theorem. 'Example 5.4 Let s z (1, 2, 3, 4, 5, 8} and let F : {(1234)(58), (13)(24), (1432)(58), I} be the given group. Then for 010003 B 1 O l 1 L0 it can easily be shown that G(A) 2 F. An approach to the general problem of finding a graph A 2 (S,R) given a permutation group F on S such that G(S,R) 2 F, is to symbolically fill in C(A) for some f in F using the property Cij 2 c.. . for all C.. 1(1)f(J) 1J in C(A). This process is illustrated by the following example. Example 5. 5 Let f 2 (l2)(34)(56) be in the given group F on 2 v 2'! 3) 4, 3 I ' )- 3 : »- I r I Z I I 3 I : : 9 S {l 5 o} Thcnt11 C22 a L12 c21 b c13 C24 c and so on for all Ci. in C(A), so that for J w 1 H] 3 n r q t s_] fis in G(S,R) where (S, R) is determined by any assignment of ones 2 C(S,R). or zeros to Cf entries so that Cf Thus, if it is desired to determine a graph A 2 (S,R) of order n for which G(A) 2 F for some predetermined group F of degree n, it would appear that the following would be sufficient: (1) Construct a C for each f in F. f (2) Assign the value 0 or 1 to each entry of each Cf avoiding contradictions if possible. (3) Determine all subgroups D of En which contains F as a subgroup. For each d in D-F. select an i and j and set Ci] #Cd(i)d(j)’ if possible. The result would be a connection matrix of a graph whose group is possibly F. If it is impossible to complete step (2) or step (3), then F is not the group of any graph. The above procedure involves extensive calculations. Possibly, the intersection table technique as developed in Section IV could be used to simplify these calculations. -49_ One final observation is of interest. Nlost large groups are not specified by giving the elements of the group, but rather by specifying sonie defining characteristic of the group. Thus, the group to graph problem should be considerably simplified for groups so specified as is the situation with the groups considered in Theorem 5. 8 and 5. 9. VI. CONCLUSION The original interest in graphs which prompted this study resulted from a problem in switching circuits. Because of the possible application of groups of graphs to such problems, the subject of algebraic properties of graphs was considered. Without regard to possible applications, this study in itself, presented some difficult and interesting problems. For this reason, this thesis completely ignores the possible applications of this work. Two such applications deserve mention. First, the original switching circuit problem involved state merging and state re- duction in sequential machines. Since the merger diagram of a flow table is actually a graph of the (S,R) type, the possibility of an algebraic attack on the merger problem should be considered. Secondly, the problem of counting the total number of non-isomorphic trees in a network has received considerable attention in the circuit theory liter- ature. Since trees of a given network that are isomorphic are related by the automorphism group of one such tree, it. would seem reasonable to attempt to classify and to count trees by use of algebraic techniques of the sort used in this thesis. Any application of this work requires a re-evaluation of the type of graph which is studied. It is easy to specialize the graph (S,R) to the non-oriented or to the loopless case. But, some applications of graphs require multiple arcs from one vertex to another. This is not possible with the graph (S,R), and is one shortcoming of this type -5()- -,1- of graph. Conversely, many of the, results in this thesis can be extended to include a more general type of system having sets of relations rather than just a single relation. Thus, a study of the algebraic properties of systems, in general, would seem to be an area for possible further work. There are several other areas of possible further work using just the graph (S,R) as the basic system. For example, the problem of finding a graph of a given group requires much more study. It should be possible to express the group of a graph product in terms of the groups of the graphs. Self-complementary graphs, oriented and non—oriented, offer many problems that could be studied. These are but a few of the Inany areas involving algebraic concepts as presented in this thesis. BIB L10 GRAPHY Robert Frucht, "0n the groups of repeated graphs, " Bull. Amer. Math. Society, v. 55 (1949). pp. 418-420. , "Graphs of degree three with a given abstract group," Canad. J. of Math., v. 1(1949), pp. 365-378. , "A one-regular graph of degree three, " Canad. J. of Math., v. 4 (1952), pp. 240—247. I. N. Kagno, "Linear graphs of degree 5 6 and their groups, " Amer. J. of Math., v. 68 (1946), pp. 505-520. , Correction to [Kl], v. 69 (1947), p. 872 , Correction to [Kl], v. 77 (1955), p. 392 "Desargues' and Pappus' graphs and their groups," Amer. J. of Math., v. 69 (1947), pp. 859—862. Oystein Ore, Theory of Graphs. Rhode Island: American Mathematical Society, 1962. Gert Sabidussi,"Graphs with given group and given graph—theoretical properties," Canad. J. Math. , v. 9(1957), pp. 515-525. "On the minimum order of graphs with given automorphism group, " Monatsh. Math. , v. 63 (1959), pp. 124—127. ”Graph Multiplication, " Math. 7.eitschr. , v. 72 (1960), pp. 446—457. ”Graph Derivatives, " Math. 7.eitschr. , v. 76 (1961), pp. 385—401. meag- , A )- 7) ' . ‘ I ,1 ‘1 a ‘- J o h f: ._ H LY