THE UNIVERSITY OF M I C H I GAN Technical Report ENTROPY AND THE COMPLEXITY OF GRAPHS Abbe Mowshowitz CONCOMP: Research in Conversational Use of Computers F. H. Westervelt, Director ORA Project 07449 supported in part by: DEPARTMENT OF DEFENSE ADVANCED RESEARCH PROJECTS AGENCY WASHINGTON, D. C. CONTRACT NO. DA-49-083 OSA-3050 ARPA ORDER NO. 716 administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR August 1967

ENTROPY AND THE COMPLEXITY OF GRAPHS by Abbe Mowshowitz A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the University of Michigan 1967 Doetoral Committee: Professor Anatol Rapoport, Co-Chairman Associate Professor Manfred Kochen, Co-Chairman Doctor Stephen T. Hedetniemi Associate Professor Eugene L. Lawler Professor Nicholas Rashevsky

ACKNOWLEDGEMENTS I would like to thank the members of my doctoral committee for their kind cooperation and guidance throughout the writing of this dissertation. In particular, I am deeply grateful to Professor Anatol Rapoport, without whose confidence and intellectual stimulation, this work would never have been undertaken. I am also grateful to Professor Manfred Kochen for his encouragerment and support, as well as the considerable amount of time he has spent with me discussing the progress and direction of the research. I would like to thank Dr. Stephen T. Hedetniemi for guiding me through the literature of graph theory, and for his many valuable suggestions and critical reading of my work. My thanks are also due to Professor Eugene L. Lawler for his cooperation and interest. The rnotion of the topological information content of a graph, which is the starting point of this thesis, is due to Professor Nicholas Rashevsky. I am honored by his willingness to serve on my committee, and I wish to thank him for his interest and encouragement. Finally, I would like to thank my wife, Hoppy, Miss Helen Ann Dugan, Mrs. Ruth Ash, and Miss Jane Grabois for their indispensable assistance in preparing the manuscript. The research reported in this dissertation was conducted at the Mental Health Research Institute, and was supported by National Institute of Health grant NIH-MH-O'+238-06, National Science Foundation grants NSF-GS-82 and NSF-GS-1027, and Advanced Research Projects Agency contract no. DA-49-083..i.

TABLE OF CONTENTS LIST OF ILLUSTRATIONS........ iv INTRODUCTION........................... 1 CHAPTER I: AN INDEX OF THE RELATIVE COMPLEXITY OF A GRAPH.... 8 1.1 Introduction..................... 8 1.2 Preliminary definitions and remarks........... 8 1.3 Definition of the information content of a graph..... 11 1.4 Properties of I e............. 16 g 1.5 The information content of a class of graph products... 30 1.6 Applications...................e 39 CHAPTER II: THE INFORMATION CONTENT OF DIGRAPHS AND INFINITE GRAPHS..... *. *.. 46 2.1 Introduction................ 46 2.2 The information content of digraphs........... 49 2.3 The construction of digraphs with given information content.............. 56 2.4 An extension of the information measure to infinite graphs..................... 59 CHAPTER III: GRAPHS WITH PRESCRIBED INFORMATION CONTENT...... 67 3.1 Introduction...................... 67 3.2 Digraphs with zero information content......... 70 3.3 Conditions under which two digraphs have the same information content......... 78 3.4 The information content of digraphs whose adjacency matrices have prescribed properties... 88 CHAPTER IV: CONCLUSION: E1NTROPY MEASURES AND GRAPHICAL STRICTIRE O............. 101 4,1 Introduction o O o 0 0 o o o. 0. 0.. O.. 0 101 4.2 The chromatic information content of a graph...... 103 4.3 Properties of the measure I.......... O 107 4.4 Comrarison of the two measures of graphical information.. 113 4.5 Smma o.,. 0,.,...,..,. 115 BIBLIOGRAPHY,. O O O 0 9 ~ O 0 9 9 0 0 0 118 111

LIST OF ITLJSIAT IONS Figure Page 1.1 The information content of graphs with four points...................... 15 1.2 Some operations on graphs............... 18 1.3 Graphs with non-isormorphic groups having the same information content.............. 19 1.4 The information content of the cartesian product of two graphs................. 25 1.5 The information content of the composition of two graphs..................... 26 1.6 An example where the information measure fails to be additive on a cartesian product...... 35 1.7 An n * n grid..................... 39 2.1 The information content of 3-point digraphs...... 49 2.2 Operations on digraphs................. 51 2.3 Path and cycle digraphs............. 57 2.4 The construction of a 24-point digraph with given information content........ 58 2.5 A countable graph with no unique information content.0.a. o ~ o. ~. ~ 62 2 6 A countable graph showing an infinite variation in information content...... * *. 64 2.7 G - defining sequences................. 65 3.1 Digraphs with five points having zero information *.. 0 * 0 * *... 74 3.2 A regular digreph of degree 2 with zero infonnrmation o o.............. 77 303 Digraphs having non-similar adjacency matrices but equal groups.......... o o 84 iv

LIST OF ILUJJSTRATIONS (Concluded) Figure Page 3.4 Digraphs having similar adjacency matrices but non-pernutationally isomorphic groups. * * * * * * * *... *.... 85 3.5 The information content of the Kronecker product of graphs.............. 99 4.1 Illustrations of horrmorphisms and n-colorings. o 103 4.2 Chromatic decompositions of graphs.......... 106 4.3 Uniquely k-colorable graphs.............. 109 4.4 Chromatic information content of a graph homeomorphic to a star............ 112 4.5 Graphs on which I and Ic differ............ 114 4.6 Graphs on which Ig and Ic agree........... 114 v

INTRODUCTION The present work is addressed to the problem of measuring the relative complexity of graphs. The central idea in our approach to this problem can be characterized as follows. Let X be a finite graph given by a set V = V(X) of n vertices together with a set E = E(X) of edges (or adjacencies). If {Vi}h is a decomposition of V into equivalence i=l classes V. containing ni vertices (1 < i < h), then a finite probability n. scheme can be constructed by assigning the probability Pi = n to Vi for each i = 1,2,...,h. The entropy of a finite probability scheme associated with a graph in this manner can then be viewed as a measure of the complexity of the graph relative to the given decomposition of its vertex set. There are, of course, many ways of obtaining a decomposition of the set of vertices of a graph. We will be concerned here with two decompositions, both of which have been the object of considerable study by graph theorists. The first, which will command most of our attention, is given by the set of orbits of the autormorphism group of a graph. The second is called a chromatic decomposition and is determined by a coloring of a graph. So far as this author is aware, the idea of defining an entropy measure on graphs first arose in a paper of Rashevsky [29], dealing 1

2 with the complexity of organic molecules. Rashevsky made use of the fact that a structural formula of organic chemistry can be regarded as a graph whose points represent physically indistinguishable atoms and whose edges represent chemical bonds. With this interpretation, one can consider the topological properties of a molecule in a graph theoretic setting. Of particular interest here is the automorphism group of a graph. An automorphism of a graph X is a one-one mapping of V(X) onto itself which preserves adjacency. The set of all automorvphisms of X forms a group, the orbits of which constitute a decomposition of V(X). Suppose X is a graph corresponding to the structural formula of a molecule M. If points a and b are in the same orbit of the group of X, it is clear that when the atoms corresponding to a and b are interchanged, the resulting molecule has the same structure as M. So, if X has n points and the orbits of the group of X contain ni elements for i = 1,2,...,h, the ratio ni/n can be interpreted as the probability that a particular atom of M (in a set of topologically equivalent atoms) will be involved in a given chemical reaction. If the (topological) complexity of a molecule M is viewed in terms of the freedom with which it can interact with other molecules, Rashevsky's topological information content (i.e. the entropy of the finite probability scheme constructed from the orbits of the group of X) is appropriate as a measure of complexity, since it depends both on the number of equivalence classes and on their respective cardinalities. Using Rashevsky's measure, Karreman [21] examined the change in information content produced by chemical reactions (which in this context correspond to simple operations on graphs). As one might expect,

3 it was found that information is sometimes lost and sometimes gained in such reactions. We will be concerned with the general analogue of this problem when we examine the behavior of the information measure on various graph products. One can easily imagine other contexts in which an entropy measure defined on graphs can serve as a measure of complexity. Of course, the way such a measure is defined (i.e. the underlying decomposition) will depend on the particular structural characteristics of interest in that context. For example, Rashevsky's topological information content might be useful in the study of friendship relations in certain populations. On other hand, it is not clear that this particular measure would be of much interest in the case of finite automata. In any case, the wide range of applications of graph theory makes graphs particularly wellsuited for a mathematical study of complexity. The principal aim of this dissertation is to deronstrate the usefulness of the entropy function as a measure of the relative complexity of graphs. We will attempt to accomplish this objective in two ways. First, we will present a detailed, systematic treatment of the entropy measure defined with respect to the autormorphism group of a graph. In so doing, we hope to establish scme tools for studying entropy measures in general, and to provide a basis for a complete classification of graphs in terms of this one particular measure. Second, we will briefly examine a measure defined in terms of a class of chromatic decompositions We treat a second measure largely for the sake of comparison. That is to say, we wish to indicate those peculiar structural characteristics of a graph which are reflected in the behavior of each of the respective measures.

In what follows we will confine our attention to graphs (both directed and undirected) which contain no loops and no parallel lines. The only reason for making this restriction is to simplify the exposition, since entropy measures can be defined for arbitrary graphs; and, in fact, objects more general than graphs can be studied from this point of view. The problem we are investigating is of such a nature as to require material from a diverse collection of sources. In particular, we use results from a variety of papers in graph theory, elementary theorems from information theory, the theory of groups, and the theory of matrices. Thus, it is appropriate to indicate a policy with regard to our use, implicit and explicit, of the expression "well-known."1 In the case of graph theory, a result which can be found in the standard references (Berge [2], Konig [23], and Ore [27]) will be considered well-known, and used without any specific citation. For group theory, we will consider results well-known if they are of an elementary nature and can be found in Hall [14] or Scott [38]. Virtually all the results we will have occasion to use from matrix theory can be found in Gantmacher [12] or Bellman [1]; and those from information theory can be found in Khinchin [22] or Fano [6]. Needless to say, if a theorem we use is of central importance in the development of a concept or method, we will present it in full. The major portion of the thesis is devoted to a systematic treatment of an entropy measure defined relative to the autormorphism group of a graph. So, a brief survey of the relevant literature on automorphism groups is in order. Studies of the autorrmorphism group of a graph are

5 largely concerned with the following two problems: 1) the existence of a graph whose autowrrphism group is isomorphic to a given group, and 2) determining the group of a graph. In the case of finite graphs, the first problem (posed by YKnig [23, p. 5]) was largely settled by Frucht [9] who showed that there exist infinitely many non-isomorphic connected graphs X whose automorphism group is (abstractly) isomorphic to a given finite group G. The same author further showed in [11] that the result still holds if the class of connected graphs is restricted to those which are regular of degree three. This result was sharpened even more by Sabidussi [32] who proved that the condition of being regular of degree three can be replaced by several other conditions. In the general case of graphs with an arbitrary number of vertices, Sabidussi [35] proved that given any group G, there exists a graph whose automorphism group is isomorphic to G. Since the automorphism group of a finite graph can be regarded as a permutation group, one can also consider when there exists a graph whose automorphism group is (permutationally) isomorphic to a permutation group. This problem is much more difficult than the former, but also more important for our purposes. This is so since there is a one-one correspondence between the orbits of two permutationally isomorphic groups which preserves cardinality. Relatively little work has been done on this problem outside of the two papers by Chao [3,41 which we will use extensively in Chapter III. Computing the automorphism group of a graph is, in general, quite difficult. Kagno [20] determined the groups of all graphs with up to six vertices; and, very recently, Hemninger [18] supplemented the listing by giving the groups of directed graphs with up to six vertices. Moreover, the automorphism group of a tree has been determined by Prins [28]. Since direct computation is usually not feasible, there is

6 considerable interest in finding the group of a composite graph in terms of the respective groups of the graphs in the composition. Perhaps the simplest composition from this point of view is the representation of a graph as a sum of its connected components. It is well-known that the group of the sum of non-isormorphic graphs is just the direct sum of the groups of the respective graphs in the sum. Moreover, Frucht [10] showed that the group of a sum of n graphs which are isomorphic to a graph X is the wreath-product of the symmetric group of degree n with the group of X. Thus, the automorphism group of a graph can be expressed in terms of the groups of its connected components, which simplifies matters somewhat. Other compositions of graphs which have corresponding group compositions are the so-called cartesian product, composition (or lexicographic product), and Kronecker product. Harary [15] and Sabidussi [33,34] treat the groups of the cartesian product and composition of (undirected) graphs. In the course of studying the entropy measure defined relative to the automorphism group of a graph, we generalize some of their results to directed graphs, and examine the group of the Kronecker product of digraphs. In Chapter I we define the structural information content Ig(X) of a graph X as the entropy of the finite probability scheme constructed from the decomposition (given by the orbits of the automorphism group) of the vertex set of a graph. In addition to examining the elementary properties of the measure Ig, we study its behavior on several graph operations, and determine a class of graph products on which it is semi-additive.

7 In Chapter II we enlarge the class of graphs on which I is defined g to include directed graphs, and show that most of the results of Chapter I generalize to the directed case. It is shown, in addition, that there exists a digraph having information content equal to the entropy of an arbitrary partition of a given positive integer. Finally, we define an extension of the measure I on infinite (undirected) graphs and discuss g its properties. The results of Chapter III depend on the connection between the adjacency matrix and the automorphisms of a digraph. We exploit this connection to develop a method for studying the automorphism group and, thus, the information content of a digraph. First, we generalize some results of Chao [4] to produce an algorithm for constructing digraphs with zero information content, and examine the properties of such digraphs. Then we give an algorithm for computing the automorphism group of a digraph, and use it to find conditions which insure that two digraphs have the same information content. This algorithm is further used to determine the information content of digraphs whose adjacency matrices have prescribed properties. In Chapter IV we discuss an entropy measure Ic defined relative to a class of chromatic decompositions of a graph, and compare it with Ig

CHAPTER I AN INDEX OF THE RELATIVE COMPLEXITY OF A GRAPH 1.1 Introduction Ideally, an index of the complexity of a mathematical object should be a function of all the elements of a complete set of invariants for that object. Unfortunately, no (tractable) finite complete set of invariants for a graph is known to exist. So, in this case, one must settle for something less: an index which is defined in terms of a partial set of invariants.l In this chapter we shall define such an index (which will be seen to take the form of the entropy of a finite probability scheme), discuss its properties, and apply it to a particular class of graphs. 1.2 Preliminary definitions and remarks A graph X is an irreflexive, symmetric binary relation on a finite set whose elements are called the points (or vertices ) of X. The unordered pairs of points in the relation are the lines (or edges) of X. We shall use V(X) and E(X) That is to say, a set of parameters which are common to isonmorphic graphs.

9 to denote the set of points and the set of lines, respectively. If V(X) = 5 (the empty set), we shall call X the trivial graph. x, y c V(X) are said to be adjacent if (the unordered pair) Ex, y] e E(X). For x E V(X), let V(X; x) = {y C V(X)j Ex, y] c E(X)}. Then the number d(x) = IV(X; x) of elements in V(X; x) is called the degree of x. A non-trivial graph having every point adjacent to every other point is called a complete graph; a non-trivial graph with no adjacencies is called a null graph. We will use Kn and rn to denote the n-point complete graph and null graph, respectively. A graph Y is a subgraph of X (written Y C X) if V(Y)CV(X) and E(Y) C E(X). Let X be a graph and V' C V(X). Then the graph Y = X(V') given by V(Y) = V' and E(Y) = { [x,y] e E(X) I x and y e V'} is called a section subgraph of X. Clearly, X = Y if V' = V. A sequence S of lines Z. z E(X) (O < i < n) is defined by S (0,'1 l...,*n) where 0 z xO' Xl]' go = [Xl, x2],., Zn = n, Xn+l]. xO and Xn+l are called, respectively, the initial point and endpoint of S. A sequence of lines is called a path when no line occurs more than once in it. A path is called a cycle if its initial point is identical with its endpoint. Two points x and y are said to be connected if there exists a sequence of lines with x0 = x and Xn+l = y. A graph is said to be connected if any pair of points is connected. It is clear that the relation of being connected is an equivalence

10 relation on the points of a graph. A graph is said to be labelled if each point has a unique letter associated with it. Note that two graphs X and Y with the same number of points (labelled with the same set of symbols) are equal if and only if E(X) = E(Y). We shall be primarily concerned with labelled graphs, and shall thus drop the adjective when no confusion is likely to occur. Two graphs X and Y are said to be isomorphic if there exists a one-one mapping c of V(X) onto V(Y) such that [x, y] e E(X) if and only if [x, y] ~ = [x~, y~] ~ E(Y); such a mapping 4 is called an isomorphism of X onto Y. An automorphism of a (labelled) graph X is an isomorphism of X onto itself. It is well-known that the set of all automorphisms of a graph forms a group. We shall denote the automorphism group of a graph X by G(X), and refer to it as the group of X. Suppose X is a graph with V(X) = {x1, x2,..., xn}, and G(X) is the group of X. If a C G(X), then xia = x. = xi for 1 < i < n. Hence, to each a E G(X), there corresponds a unique permutation of the elements 1, 2,..., n. So, we can regard G(X) as a subgroup of Sn, the symmetric group of degree n. Suppose H < S (ioe., H is a subgroup of S ), and 1 < i< n. Then { i a a e H} is called an orbit (or transitive set) of H. Let A1, A2,.., Ah be the distinct orbits of H. Then AinA. = ~ for i # j, and.(J. Ai = {1, 2,..., n}, i.e., the 1=] 1

11 orbits form a partition of the set {1, 2..., n}. Throughout the following, we shall denote the cardinality of a set S by IS J, and all logarithms will be taken to the base two. 1.3 Definition of the information content of a graph The idea of defining an entropy-like function on a graph was first explored by Rashevsky [29]. Trucco [39,L4 then followed with a formal definition of Rashevsky's "topological information content" in terms of the automorphism group of a graph, and traced out some simple consequences of the definition. 1.3.1 Definition (Trucco [40, p.238]). Let X be a graph with IV(X)I = n and let A. (1 < i < h) be the orbits of G(X). We construct a finite probability scheme PX as follows: A13Al' A29 0 * * Ah Ail /p A1 A2, *' h', where p =, 1 < i < h. Pi, P2' s i Ph n Then the structural information content I (X) of X is given by h Ig(X) - - Pi log Pi' the entropy of the scheme PX. i~l Before discussing the properties of this function, let us consider its appropriateness as a structural index, or as an index of relative complexity. First of all, it should be noted that I is not a selective measure of information as the g term is understood in information theory. That is to say, it does not give the average uncertainty per event (graph) of a

12 given ensemble of events (graphs). Rather, it gives the information content of a particular graph relative to a system of transformations under which the graph is invariant. Since this distinction is crucial for a proper interpretation of the measure, let us belabor the point with the following illustration. For a fixed positive integer n, let Cn be the collection of all distinct labelled graphs X consisting of n points. If F is the set of all possible adjacencies among n points (i.e., F {[xl, x2],..., [xl, Xn], [x2, x3], x2 xn].'. [Xn-l' Xn]} where xi s V(X) ), then to each graph X c Cn there corresponds a unique function f with domain F and range {O, 1} such that if [., E(X) f ([.X X.]) = 1 1 if [xi, xj] EE(X) (I.e., each X e Cn can be represented as an ordered sequence of (n ) zeros and ones.) Hence, the number IC I of elements of Cn is 2 2 Now, if we assume that each X e Cn occurs with the same frequency, and independently of all the others, then the average uncertainty per graph in Cn is given by ( n n log 2( 2 )n A refinement of this scheme can be obtained by grouping isomorphic graphs together. Suppose there are k non-isomorphic graphs X1, X2,..., Xk in Cn, and that each Xi is isomorphic to ki graphs (including itself) in C (1 < i < k). Clearly, we have i ki 2( n ) If we let the relative frequency i=l k. of occurrence pi of X. be given by pi - 1 and assume 1 1 --- ndasm2e 2

13 that each Xi occurs independently of all the others (1 < i < k), then the average uncertainty per graph of the ensemble{Xl, X2,..., Xk} is - Pi log pi. In the former case, the structure of the graphs is completely immaterial except for determining the number of elements in Cn; in the latter case, we are concerned with structural properties only insofar as they are needed to decompose Cn into disjoint classes of isomorphic graphs. However, it is clear that in both cases, the average uncertainty per graph is a characteristic of the particular ensemble, and not of a given graph. One way of interpreting the structural information (or uncertainty) Ig(X) of a graph X E Cn is in terms of the number of graphs in Cn which are isomorphic to it. For example, suppose we are asked to construct a particular graph X e Cn and to label its points with the symbols al, a2,..., an. Now, the number of distinct ways of labelling X is just the number k of graphs in Cn (including X) which are isomorphic to X. Hence, the probability of constructing a particular labelled copy of X is 1k. Thus, we can say that the larger the number of distinct (labelled) graphs to which a graph X is isomorphic, the smaller is the probability of constructing any given labelled copy of X. The connection between the number of graphs in Cn isomorphic to X, and Ig(X) is given (partly) by the following 1.3.2 Remark. Let X e C0, and G(X) be the group of X.

14 Then the number of distinct labelled graphs Cn (including X) which are isomorphic to X is n! / IG(X) I. Proof. The set of all one-one mappings of V(X) onto itself is Sn, the symmetric group of degree n. Clearly, each a ~ Sn determines an iscmorphism of X onto some Y e Cn. However, two distinct elements of Sn may have the same image graph. In fact, we will show that each B c Go maps X into the same graph Y, where Ge is a right coset of G. Suppose B: X + X$ (and a: X + Y) for all F e G a. Let Ex,y] c E(X) *~ x,y]a = [xr,yl] e E(Y), and [x,y]$ = ([x,y]y)a, where y E G(X). But Ex,y]y z [xy,yy] E E(X) since y m G(X), so [x,y]8 ~ E(Y). Hence, the image under f of every line [x,y] c E(X) is a line of E(Y), which shows that X$ = Y. Thus, we conclude that the number of distinct graphs in Cn isamorphic to X is given by the number [Sn:G] of cosets of G, which is, of course, n!/lG(X). It follows immediately from 1.3.2 that the minimum number of isomorphic images of a graph X e Cn occurs when G(X) = Sn, which is always the case for the complete graph Kn and the null graph Kn. Moreover, the n n maximum number occurs when G(X) is the group consisting of the identity above, i.e., G(X) = {e}1 Analogously, it is clear that Ig(K )=Ig(K )=O, and I (X) = log n when G(X) = {e}. Let X,Y ~ Cn and suppose a = JG(X) I, a' = IG(Y), and n! nt a < a' (or a- < ). Then it is possible to have Ig(X) < I (Y). However, the difference II (X) - Ig(Y)J will usually Note that the smallest graph (excluding K1) with group {e} has six points.

15 Number of Orbits X. GX) IG (XiI no I (X.) with Y Xi G g(X 2..3 S4 24 1 { 1,2,3,4 } 0..53 {e,(12),(34),'] Ii (12)(34),(13)(24) 8 (1423),(1324) 8 3 1234 (1 {5 {e, (12), (14), 3 (24), (124), 6 4 {1,2,4} {3} 2 - 1o g, 1 —-, >4 (142) } t1.*3 {e, (12), (34), (12)(34) } 4 6 {1,2},{3,54} 1 I.4_ {254}1{1}1 3 {e, (24)} 2 12 {3} 2 z~~~~ 3 L A 1 {e, (14)(23)} 2 12 {1,4} 1 1I 471 {e, (12)} 2 12 {1,2} {3} 3 {4} 1 2 {e, (13), (24), 14 | 6. 11 41. (13)(214)} {2,1,4} 1 -~2-~ ~ (4 {e, (23) (24), 6 14 {2,3,4},!2 - 311g 3 (243)}__ - - 5t 3 {e,(1234),(13), -. (24),(13)(24),(12: 8 3 {1,2,3,4}1 0,L-!(34),(14)(23)(143 )} Si4 24 1 {1,2,3, 4} 0 Figure 1.1 The information content of graphs with four points

16 be relatively small when la' - al is small. For example, when a' a 2, I g(X) - I (Y) < n- In any case, the agreement (with respect to the relative complexity of X in C n) between I (X) and na in the extreme cases lends plausibility g a to the definition of I as a measure of the structural inforg mation content of a graph. Figure 1.1 shows the relation between I (X) and the number of Y e Cn which are isomorphic to X for the case n = 4. 1.4 Properties of I g In this section we shall investigate the behavior of I g on several graph operations. We begin with some definitions of group operations. Let G1 and G2 be permutation groups with (disjoint) object sets Al and A2, respectively, with IGii = ni, IAil J di (i = 1,2). Suppose, moreover, that Oi (1 < i < hi) and 01 (1 < i < h2) are the orbits of G1 and G2, respectively. I1 - - 2 1 2 First, note that G1 and G2 are said to be permutationally isomorphic (G1 p G2) if there exist one-one mappings f:A1 -* A2 and T: G1 + G2 such that (xa)f = (xf) (am) for all x E Al, a e G1; and w is a group isomorphism, i.e., (a)T = (aTT) (iT) for a, S e G1. The direct sum of G and G2 is the group G1 + G2 = IG1 + G2, = nl n2, and if O is an orbit of G1 + G2, then 0 = Oi or O = O'. The number of such orbits is clearly hi + h2.

17 The cartosi f f Gr andG2 is the pzoup 1X X2' {(a,,)I aeG1, TeG2 } with object set A1X A2. The elements of G1X G2 act on elements of A1X A2 as follows(a,b) (a,T) 3 (aa, bT), where (a,b)- A1X A2, (a,T) e G1X G2. IA1X A2 = d1d2, IG1X G21 = nlnn, and if O is an orbit of G1X G2. then ~ 0i X 0! for some i and j. The number of such orbits 0 is hlh2, and IUI 1o0x o'.I =1il.o' 10o ]30 i3' The composition (wreath product or Gruppenkranz) of G1 and G2 is the group G1. G2 consisting of all elements for the form <o;T, 2' * * Tdl >, where aeG1 and Tic G2 (1 < i < dl) The object set of G1 0 G2 is A1' A2, and the action of EG1 o G2 on (ai, bj) E AlX A2 is given by (ai,b.j) = (ai,bj)< a;1T,..., Tdl> = (aiobj) IA1X A21 = d1d2,1G1 o G21 = nn2d 1, and again each orbit Oof G1 G2 is of the form OiX 0' for some i and j. Now let X1, X2 be graphs with V(X1) = V1, V(X2) = V2, E(X1) - E1, E(X2) = E2, and G(X1) = G1, G(X2) = G2. The complement of X1 is the graph X1 with V(1) = V1, and E(X1) ={[x,y] I [x,y] ~ E1, x ~ y, x,y ~ V1}. The sum of X1 and X2 is the graph X1 U X2 given by V(X1U X2) - V1U V2, and E(X1U X2) = E1U E2. As indicated earlier, the set of points of a graph is partitioned into equivalence classes by the relation of being connected. So, if X is a graph, n V(X) = Vi (Vi(n Vj =for i $ j) and [x,y] E(X) i-1 n only if x and y are in the same Vi for some i. Thus, = U Xi where Xi = X(Vi). The section subgraphs Xi are called the connected components of XO

The join of X1 and X2 is the graph X1 + X2 defined by V(X1 + X2) = V1U V2 and E (X1 + X2) = E(X1U X2)U j [x,y]xE V1, yCV23. The cartesian product of X1 and X2 is the graph X1 X X2 defined by V(X1X X2) =VX VV2, and E(X1X X2) = [[x,y] = [(x,x2), (Y1, Y2)] I X1, Yl( V1, x25 Y2 V2 and either xl z Y1 and [x2,yY2] E2 or x2 Y2 and [xl,yl]6El. It is easily seen that the effect of "multiplying" X1 and X2 in this fashion is to substitute an isomorphic copy of X1 for each point of X2, and to connect corresponding points of isomorphic copies whenever there is a line in X2 connecting their associated points. As noted in Sabidussi [34,p.4471, the set of all (non-isomorphic) graphs under cartesian multiplication form a connmutative semi-group with identity, the identity being K;. The composition of X1 with X2 is the graph X1 o X2 given by V(X1 o X2) = V1X V2 and E(X1 o X2) = [Ex,y] [(x1,x2), (Y1Y2)] 1 Xl, Y1lVl, x' Y2 y V2 and either [xl,Yl] 6 E1 or x1 - Yl and [x2,Y2] E E2. The effect of formning the composition X1 o X2 is to substitute isomorphic copies of X2 for the points of X1, and lines joining each point of one copy with every point of another copy for each line in X1. This operation is not commutative, but, as noted in Sabidussi [33,p.693], it is associative in the sense that X o (Y o Z)0-(X o Y) o Z. The foregoing graph operations are illustrated in Figure 1.2. Li if i X Figure 1.2 Some Operations on Graphs

19 We bgin our investigation of the properties of tht mesu=e I with g sone remarks on the conditions under which two graphs have the same information content. 1.4!1 Leuma. Let X and Y be graphs with IV(X) I = IV(Y) J, and with groups A h A G(X) and G(Y), respectivelyG Suppose A {A} and B {B } h2 are li=l lail the sets of orbits of G(X) and G(Y), respectively. If there is a one-one A A A mapping ~ of A onto B such that IAI = IAI for each A t A, then I (X) = I (Y). Proof. Without loss of generality, let A~~ z Bi. Then since Ai = 5AiI, the respective finite probability schemes associated with X and Y have the same entropy. Hence, I (X) z I (Y). The converse of this result is not true as can be seen from thetwo graphs in Fig. 1.3. G(X) has four orbits, each consisting of two elements; G(Y) has one orbit with four elements, and four orbits each containing one element. So for this example, we have Ig(X) = 4 (1 log 4) = 2, Ig(Y) z i1 l o2 1 1 3 log 2 + 4 (8 log 8) x + T= 2. 8 2 2SCL 2z 7 e ar,6 b 4- C X Y Orbits of G(X): Orbits of G(Y): {1,8}, {2,7}, {3,6}, {4,5} {a,b,c,d}, {e}, {f}, {g}, {h} Figure 1.3 Graphs with non- isomorphic groups having the same information content The group G(X) of a graph X partitions the vertex set V(X) into disjoint classes. Thus, to a given set of orbits, there corresponds a unique partition P of the integer n = IV(X)I, where P={nl n2,..., nh} and

20 ni is the number of elements in the i-th orbit of G(X). Suppose we want to construct a graph X with n points and with a specified information content I. It is clear that a necessary condition for the existence of such a graph is that there exists a partition P of the integer n, which gives rise to a finite probability scheme having entropy I. Necessary conditions for the existence of such a partition when I is rational are given by the 0 following 1.4.2 Theorem. Let n be a fixed positive integer, and let Io = p/q, where p and q are integers ( p ~ o, q - o). Then there exists a partition Q with entropy I only if the following three conditions are satisfied: 0 (i) p = qal - n r2 +44 + kt22 rt 23 ZnL2 2 (ii) ncai =Pi rpi + k2pi r2pi... kt rti] for all i 1 Pi t~pi ip I (iii) If = 0, then r. = 0 for all integers j (1 < j < ti) h where n = II p'i (Pi is a prime with Pi -n and Pi pj for i / j); r. is the numiber of times 9 occurs in Q; k. = j(l + Pi), where h' j = n p~; and ti is such that tipi < n and (ti + l)Pi > n. Proof. The entropy of Q is given by H(Q) = I ri ( log ) = log n - 1 n 1 n ri (i log i). n Hence, we have p = q [log n - ri (i log i)]. h i=l Now, log n = I log p ci = + h iI ai log pi, so i=2 h1 n P: i[m+ i Pi log pi r i log i).

21 1 n Moreover, n ri (i log i) = 2 [r2 + 4r + 3r +kt2 rt2] fl ~i=l 4 6 2 2 + (3 log 3) Er3 + 2r6 + 6r9 +..+ kt 3rt33 + (5 log 5)'[rs 5 2rlO +.' + kt5 rt5] +* * + (Ph log ph) [rph]. Since p is an integer, the oefficients of log Pi, n Pi P 2pi tiPi tiPi must equal i for 2 < i <h; and p =q -1. 2 Er2 + 4r4 + 3r6 +... + kt rt] which = n 2 2 6t22 give conditions (ii) and Ci), respectively. Condition (iii) follows from (ii) when a. = 0, since the k. > O and r. > 0. 1 Jpi 3pi As applications of this result, consider the following 3 2 (1) Let IO = 4, n- 4. By condition (i), 3 = 4.2 - 4[r2 + 4r4], which implies Er2 + 4r4] = 10. But 0 < r2 < 2 and 0 < r4 < 1, which shows that condition (i) cannot be satisfied for these values of I0 and n. Hence, no partition of n = 4 can yield an entropy of 3 (2) Let IO = 2 and n = 40. Then 2 = l3 - [r2 + 4r4 + 12r8 + 5r16 + 20+ 8 0r 32 by i) and (iii). So, Er2 + 4r4 + 12r8 + 5r10 + 32r16 + 20r20 + 80r32] = 20, which implies that r16 = 0 and r32 =. Take r10 = 4. Then r2 = r8 = r20 =. According to (ii), we must have 40.1 = 5 E[r + 2r10 + 4r20 + l0r25], which means r5 + 2r10 + 4r20 + 10r25 = 8; but r10 4 and r = r = O is an allowable assignment. (Note that 10r10 - 10.4 = 40 = 40. iri, which i=1

22 is obviously necessary.) As it turns out, the partition Q {10,10, 0, 10, 10} has entropy 4(1 log 4) z 2 Io. Now, let us examine the behavior of the measure on the graph operations discussed earlier. 1.'4.3 Theorem. Let X be a graph. Then I (X) = I (X). g g Proof. By 1.4.1 using the fact that G(X) = G(C). 1.4.4 Lemnma. Let X and Y be isomorphic graphs with V(X) (f V(Y) —. Then, (i) I (X U Y) = I (X) g g (ii) I (X + Y) z Ig(X) Proof. (i) In general, if X1,..., Xn are isomDrphic to X, we n writeUXi z nX. Suppose X z k1 X1U k2 X2U r U krX i-l1 2 rr where the Xi(l < i < r) are the connected components of X, and Xi and Xj are not isomorphic for i A j. Since X and Y are isomorphic, Y = EkY1 U ~. **U krr where Yi! Xi (1 < i < r). Now, G(X) = G(klX)+...+G(krXr)= Sk ~ G(X1) +... + Sk G(Xr), by a theorem of Frucht [10,p.4L18]. 1 r (Note that + and o denote the direct sum and composition operations, respectively,and Sk is the symmetric group of degree ki). And G(X U Y) = i G(2klXl) +... + G(2k X ) S2k o G(X) + + S G(X Hence, G(X) and G(X U Y) have the same number of orbits, namely, number of orbits of G(Xi)]; moreover, each orbit of G(X) corresponds i=l to an orbit of G (X U Y) containing twice as many elements, since each orbit of the group Sn o G is just the product of a set of n elements with some orbit of G. So, if IV(X)I = n and PX =(~' A2'' then n n n

23,PUB1, ~ ~ ~, VBh 2_,, 2%), and it is clear that H(PX) H(PXUy) 2n 2n (ii) By a result of Zykov [43, p. 6], X+Y = XUY. Thus, Ig(X + Y) I (CUY) =I CUY) Ig( ) = Ig( X), by 1.4.3 and part (i). By a strictly analogous argument, we obtain the following generalization. 1.4.5 Theorem. Let XI (1 < i < n) be graphs isomorphic to a graph X, and suppose V(Xi) t V(X.) for i f j. Then, <i>) Ig(XU X2U.. u Xn) = g(X) Cii) I (X1 + X2 +... + X ) I (X) As an application of this property of invariance under repetition, we observe the following. Sum. (1) Let X= 2, Y = b 1L a Then Ig(X U Y) r Ig(X) = I g(X) < IgCX) + Ig(Y) = 2 Ig(X), since Ig(X) > 0. (2) On the other hand, if we let X = K1 and Y = K2, we have Ig(X U Y) > 0 = Ig(X) + Ig(Y). Join. (1) Let X and Y be as in (1) above. Then Ig(X + Y) = I (X) < I g(X) + I g(Y) = 2 I (X) since I (X) > 0. (2) Let X = Kaand Y be as in (1) above. Then we have Ig(X + Y) = 1> log 3 - = I (X)+ Ig(Y).

24 It is clear froam 1.4.5 and the above example that the sum and join operations are not likely candidates for establishing a general semiadditivity relation for the measure I. Thus we shall proceed to examine the two graph product operations, cartesian multiplication and composition in greater depth. Before doing so, however, we shall state the following fundamental 1.4.6 Lemma. Let X and Y be graphs, G(X) and G(Y) their respective groups. Suppose o and V denote binary relations defined on graphs and groups, respectively, which satisfy the following three conditions: (i) V(XoY) = V(X) x V(Y) (ii) G(X) VG(Y) - G(XoY) (iii) C is an orbit of G(X) v G(Y) if and only if there exist orbits A and B of G(X) and G(Y), respectively, such that C = A X B. Then I (XoY) < I (X) + Ig(Y), with equality if and only if G(X) V G(Y) and G(XoY) have the same orbits. We shall defer the proof of this lermma until section 1.5 where it will be seen to follow from a more general result. A graph X is said to be prime with respect to the cartesian product if whenever X )X1 X2, then either X1 or X2 is the identity graph K1. Since every graph is a unique (up to order and isomorphism)product of prime graphs, we define graphs X and Y to be relatively prime with respect to the cartesian product if whenever X = X' Y. Z and Y = Y' X Z, we have Z K1. (I.e.. X and Y are relatively prime if they have no common prime factor). 1.4.7 Theorem. Let graphs X and Y be connected and relatively prime

25 with respect to the cartesian product. Then Ig(X x Y) = Ig(X) + Ig(Y) Proof. Harary [15,p. 33] has shown that G(X X Y) = G(X) X G(Y) if and p only if X and Y are relatively prime. The theorem follows immediately from this result and lemma 1.4.6. Since it is always the case that G(X) K G(Y) - G(X X Y) for any graphs X and Y, we have by lemma 1. 4.6 that Ig(X XK Y) A Ig(X) + Ig(Y). This holds since the effect of an automorphism O e G(X X Y) with ~ G(X) Y G(Y) can only be to collapse two or more orbits of G(X) X G(Y). Figure 1.4 illustrates the two possible cases. Ii X Y X'I Y' X (Y X' x( Y' I(X X Y) = I (X) + Ig(Y) I (X"K Y') = 2 log 3- 16/9 = log 3 - 2/3 < 2 log 3 - 12/9 Ig(X') + Ig(Y') Figure 1.4 The information content of the cartesian product of two graphs Sabidussi [33,p. 694] gives the following necessary and sufficient condition cn graphs X and Y under which the relation G(X o Y) = G(X) o G(Y) is satisfied: The relations R and S defined ty xRy if and only if V(x;X) = V(y;X) and xSy if and only if V(x;X) U {x} - V(y;X) U {y3

26 are easily seen to be equivalence relations on V(X). Let A be the relation z (x,x) x v(x)3 Then G(X o Y) z G(X) o G(Y) if and only if Y is connected whenever R i A and Y is connected whenever S ~ A. An immediate consequence of this result is the following 1.4.8 Theorem. Let X and Y be graphs. Suppose Y is connected if R ~ A and Y is connected if S A. Then I (X o Y) = I (X) + Ig(Y) Proof. Lrna 1.4.6 using Sabidussi's theorem. Now we shall establish a weaker condition under which additivity of information content obtains for composition. (Figure 1.5 shows that such a condition is possible.) We shall show that for any graphs X and Y, I (X o Y) I g(X) + I (Y) if whenever % G(X o Y) with (p,q), =(pt,q'), (p,q), (pt,q') E V(X o Y), there exists T E G(Y) such that qT =q'. X' Y' X o Y X' o Y X o Y X' o Yt G(X) o G(Y). G(X o Y) G(X) o G(Y) = G(X o Y) Ig(X o Y) I(X) + I(Y) = Ig(X) + Ig(Y) Ig(X o Y) = Ig(X) +Ig(Y) Figure 1.5 The information content of the composition of two graphs

27 In order to demonstrate this result, we shall need the following 1,4.9 Lemnma. Let X and Y be graphs with respective groups G(X) and G(Y). If for each + E G(X o Y) with (p,q)O =(p',q), for some (p,q), (p',q') E V(X o Y), there exists a E G(X) and T E G(Y) such that pa = p' and qT = q, then I (X o Y) = I g(X) + I g(Y). Proof. Let Ai(1 < i < hl) and Bi(l < i < h2) be the orbits of G(X) and G(Y), respectively. It is clear that each Ai X B (1 i (1 < i <hl, 1 <j <h2) is a subset of some orbit C of G(X o Y), since G(X) o G(Y) < G(X o Y). In fact C = U Ai X B. for some choice of index sets I and J. Now, aI eJ suppose (i,j) E Ai. Bj and (k,Q) E A. X B. where A. X B. I1 li'2 32 1 Jl / Ai; B. are arbitrary orbits of G(X) o G(Y). If Ai A, there -12 32 2 does not exist a e6 G(X) with io = k, since A. and Ai are distinct 11 12 orbits of G(X). Thus, by hypothesis, there is no 0 E G(X o Y) with (i,j)4 = (k, ), which implies that A. X B. and A.2x B are distinct 1 - l 2 2 orbits of G(X o Y). Similarly, if Bj. Bj, there is no T e G(Y) with 2 jT = Q, since B. and B. are distinct orbits of G(Y). So, again by hypothesis, there can be no qeG(X o Y) with (i,j)o = (k,Q) which implies that A. x B. and A. ( B. are distinct orbits of G(X o Y). Clearly, if both'1 3l'2 32 A.i Ai and B. ~ Bj,we have again that Aix B and A. B are distinct. Thus, for each i and j (1 < i < hl,l < j < h2)AiX Bj is an orbit of G(X o Y); or G(X o Y) and G(X) o G(Y) have the same orbits. The result follows from lemna 1,4.6. Let X be a graph. The adjacency matrix A=A(X) of X is defined as follows: A = (ai) where a.i = 1 if [ij] E E(X)'I (.0 if [iAj1 ECX) Clearly, A is symmetric and ai. = 0 for 1 < i < n where n =IV(X) I; moreover, cG(X) if and only if ai = ai ja for all i,j(l < i,j _ n). Suppose X

28 and Y are given with IV(X)I = n, IV(Y)I = m, and A = A(X) = (aij), B = A(Y) = (bij). Then the matrix A o B = (a(i j) (k,1)) defined by Ibj if i k a(i, ),(kl) aik if i # k is the adjacency matrix A(X o Y), for if i=k, [(i,j),(k,l)] e E(X o Y) if and only if [j,l] E E(Y), and if itk, [(i,j),(k,l)] e E(X o Y) if and only if [i,k] E E(X). If we assign the number (i - l)n + j to the point (i,j)E V(X o Y), and number the rows and columns of A(X o Y) consectuively from 1 to in, then it is easily seen that A o B = A(X o Y) takes the following form: B a12 J a13 J... aln J a21 J B a23 J... a2n A(X o Y) = nl J an2 J an3 J... B where J is an m x m matrix consisting of all ones, B = A(Y) and aij (i $ j) is the i,j-th entry of A(X). 1.4.10 Theorem. Let X and Y be graphs with respective groups G(X) and G(Y). Let E G(X o Y) with (p,q)% = (pY,qV) for some (p,q), (p,q, ) E V(X o Y). If there exists a T E G(Y) with qT = qv, then Ig(X o Y)= Ig(X) + Ig(Y). Proof. By the previous lemma, we need only show that there exists a a E G(X) with pa =p'. Let A(X), A(Y) and A(X o Y) be as above. For each r(l~rLn), let Ir ={ii |(r,j) =, 1-) for 1 ej; and fn-r P A eih T I,r in f-Trn l be m r a for each iEIr (1l _i ~n), let mr be the number of.points (ir, lj)=(r,j)) n k n with ir =i. Clearly, >. mr = m and ( = k for each i=l 1 t=l i=l'

29 k k = 1, 2,..., n. Now, ifI U Ir i k, then there are fewer t=l t k than k elements in U I. So, without loss of generality, t=l t k suppose 1, 2,..., h (h < k) are the elements of U I. t=l rt Then, since k n r n k r h k r hm < km = ( m. ) ( m. ) ( mit), t=l i=l i=lt=l i=l t=l k r there must be some i for which [ m. > m, which is impossible. t=l Thus, for any choice of k subscripts rl, r2,..., rk, k IU Ir > k for all k = 1, 2,..., n; consequently, by t=l t the well-known theorem of P. Hall, there exists a system of distinct representatives (SDR) for the sets Il, 12,... I. n Claim: there exists an SDR i1, i2,..., i with i p' (~ I ). Without loss of generality, let p' = n; and let Jr = {icIrl i 9 n} for r ~ p. We need only show that there exists a SDR for J1, J2,... Jp l Jp+l1 *., J. For any k = 1, 2,..., n - 1, n k n-l r (k- l)m < I ( I mt )< kmn, t=l i=l1 k where rt p. IfI U Jr I= h(h < k), then, as before, there must be some t=l t k r i with [ m. > m, which is impossible. Thus, let il, i2..., i be t-l an SDR for I1, 12,.., In with i = p', and leta be defined by.ee fr xapl 1See, for example, Ryser [31,p.48]

30 ra = i (1 < r < n). Clearly, a is a permutation of the integers 1, 2, r - -.., n. We will show that aeG(X). For each r(l < r < n), there exists a j(l < j < n) such that (r,j)4 = ( rc, j'), by the definitions of the sets Ir, and of the permutation a. So, if r A s, there exist jr and js (l < <r s < n) such that rs a(r,Jr),, ) a(r ), ( a(ra, ir), (Sa, Js) ra sinceqeG(X o Y) and ra A sa. Moreover, for each r we have o = a = rr are' r. Hence, for every r and s (1 < r, s < n), ars = ara s',and pa = p', as required; so a is the desired automorphism of X. 1.5 The information content of a class of graph products In this section we shall prove the principal result of the chapter concerning the semi-additivity of the measure on a class of graph products. Let X and Y be graphs with IV(X)I = n, IV(Y)I = m; let G(X) and G(Y) have orbits {Ai.}hl (where IA. ni), and {Bi}h2 (where JBi2 mzi) respectively. Furtheniwre, let PX and Py be the finite probability schemes associated with X and Y: P -( A1 2( A A), = ( i 2, h2), where P1 P2' * * 1'P ql( q2' qh2 n. m. Pi l jrand qi = m_ Now we define the product schemes PXy and Py as 1 m XY XY follows: C C2,' = P = 2 and PX 2 2, where (lX 1*h2h r1 r r

31 Ck Ch(i-1) + j Ai Bj (1 < i <h, 1 < j h2), rk = r(i) + j Piqj; and PIy is the scheme associated with the product graph X ~ Y where the operation e satisfies the conditions of lemmna 1.4.6. I.e., C (1 < k < h) is an orbit of G(X' Y), and r= mn. Next, for 1 < k <hlh2 and 1 < < h, we define the conditional probabilities, if cn c, L rkL PECkl C'] x if Ck n cl r rk Conditions (ii) and (iii) of lemra 1.4.6 guarantee that 0 < r < 1; moreover, since there is exactly one Q (zt) with Ck C, we have h P[ECk C; z o for 9. t, Z P1Ck I C] P for t, P[Ck I Ct] P[C'] = rk hlh2 h. r.rt =rk = P[Ck], and,finally, X X P[Ck I C;] PECr] ~~~~~~~t ~k=l Z1= h h2 ~ PCCk] 1. k'l Thus, we can define the conditional entropy of Pxy given P'Xy in the usual way as hlh2 h H(PXyI PI'Xy) - X k P[Ck I CY] P[Cl] log P[Ck I C.'] Now we are in a position to state the 1.5.1, Theoren. Let X and Y be the graphs characterized above. Suppose O and V denote binary relations defined on graphs and groups, respectively, which satisfy the following three conditions: (i) V(X o y) 2 V(X) X V(Y) (ii) G(X) V G(Y) < G(X ~ Y)

32 (iii) C is an orbit of G(X) V G(Y) if and only if there exist orbits A and B of G(X) and G(Y), respectively, such that C - A X B. Then I (X o Y) = I (X) + I (Y) - H(P I P) g g g XY XY Proof. The average mutual information between PXy and PIy is given by I(P; PXy) = H(PXy) - H(Pxy I Py)' But h1h2 h PC CQ] XY XY, k=l Q-1 Q k Ck log h hh~ PLCk Ck] IPLC,];kl PL Ck I Ci] log PC Since P[Ck j CQIt k, there are two cases Pk to consider. Case 1. Suppose there exist Q" (C < Q < h) and k*(l < k* < h1h2) such that P[Ck* j CQ*] 1. Then Ck* 2 CQ*, and since P[Ck I C,] r 0 for k A k*, we have that h1 h2 P[Ck I CQl*] kl P1 Ck C'*] log PC] - log PLCk*] - log PLC] 5 - log r, Case 2. Suppose there exists an *(1 < Q* < h) such that rk P[CT I CQ C*] 0 for all a satisfying 1 <. a < u < hlh. Then P -Ck | CQ* O for all k f ka (1 have U), and

33 h11 1 ~ Pick I cPE b 12 CQz' l Cka' Thus, X P[Ck I C'] log k I ) I FU L r P*C]* rk k rrk k al log Q r l = log a azl r - log PECoJ. Since one of the two cases must occur, we have for each (J.1 < Q < h) h1h2, P[Ck I C] rk I PlC I C,] log - log PlCg] kdl P ZCk Hence, I(Py; Pxy) l - PLC] log PC H(Pky) x I (X e Y); so we Sine one that IC(X * Y) E H(PXy) - H(PXy I PXy) (1) hlh2 h h2 Now, H(PXy) E - C PECk) log PCk] - rk log rk k= P[klo kCl hi h2 h2 1 %=1 *jI 5 piqj log Y) H(P q 1 Pi log y) (1) J-zl 3P- j~1 jz h1 h2 Pi q log qj H(P + H(P I (X) + I (Y) (2). izl l g g Combining (2) with (1), we have Ig(X X Y) = Ig(X) + Ig(Y) -H(Pxy I PXy), as required.

34 The proof of lImu 1. L4.6 follows idmediately from this theorem and the observation that H(Pxy I Py) = 0 if and only if G(X) V G(Y) and G(X o Y) have the same orbits. Before illustrating the theorem with an application, let us characterize H(PXy I Py). 1.5.2 Theorem. Let X and Y be as in the previous theorem. Suppose gk Co Y Ck = for 1 < k < h'(<h) and C =1Ck for h' + 1 < k < h, i=l ik 1 h where gi + (h- h') = hlh2. Then i=i gk gk h' gk I ICkil ~H(P~ I Pt I I i=l kI ~- [ [ icki-log. e gk gk prof. Since ~: U C k.(and C =I I ICk I), we have i=l i i=l i rk I k. I- 1 ICk. I 1 1 for 1 < i <gk P[C.ikC r(z =k1 rkr 1 gk gk i=l i i=l i = 1, for i=l and h'+l < k < h; and P[CjICQ = O for any j A ki and Q A k (1 < j < hlh2, 1 < < h). h hlh2 Thus, H( PXY) P P[CQ] I) P[C C log P[Cj I CT] P=1 j=l h' gk = - P[CT i 7 P[Ck] P[Ck C] log P[Ck C] k=l i=l 1 1

35 gk k ( i Z C Icl). C log l, which k=1 Ok T ~~k=l im~~~nn]iz Ck[l iJl 1 gives the desired result. (i) ) (C) (Id) 1aa 2, E b I (Laa (tb+(2.c f(2. 2 b X 2 Y: 3 Y: |b) ZC)(d3 4 d (4,b) (4,1) (I,d) Orbits of G(X) Orbits of G(Y) Orbits of G(X X Y) {1,4}, {2,3} [ad}, {b,~} {(l,a), (l,d), (4,a) (4,d)), {(2,b), (2,c), (3,b), (3,c)} {(l,b), (l,c), (4,b), (4,c), (2,a), (2,d), (3,a), (3,d)} Figure 1.6 An example where the information zmasure fails to be additive on a cartesian product. Example. Let X and Y be as in Fig. 1.6, and let the graph operation o be the cartesian product as indicated in the figure. The orbits of G(X), G(Y), G(X) x G(Y) and G(X X Y), respectively, are: {A1= {1,4}, A2 ={2,3}},{B1 = fa,d}, B2 = {b,c}}, {C1 A1 B1', C2 =A1 X B2, C3 = A2 X B1, C4 = A2 X B2} and {C1 = C2 U C3, C2 = C1, C3 = C4}. So, H(PXy j Px,) = -[ 4 log + 4 log -] -, and I (X X Y) = I (X) + I (Y) 1 2 2(2 log 2) 12 2 g g g 2 2.

As in this example, it is clear generally that strict inequality obtains if at least two orbits of G(X) V G(Y) become collapsed into one orbit of G(X o Y). An immediate consequence of theorem 1.5.1 is the following 1.5.3 Corollary. Let X and Y satisfy the conditions of theorem 1.5.1. Then I (X o Y) < I (X) + I (Y) if and only if there exists 4eG(X o Y) g g g such that u~ =v for some usCi and vCj (Ci 9 Cj). Proof. This follows from theorem 1.5.1 and lemma 1.4.9 (which holds for arbitrary graph and group products satisfying the conditions of 1.5.1). Theorem 1.5.1 generalizes in a natural way. Let X1(1 < i < t) be graphs with groups G(Xi). Suppose o and V denote binary, associative (up to isomorphism) operations on graphs and groups, respectively, which satisfy the conditions of 1.5.1; and let Ai) A2 (i) be the orbits of G(Xi). First, we define the product schemes: Ct PX1X2... Xt ( ) where Ck = X A k2 X ~ ~ C1, r2,..., 1 2\ and rk = P[Ck], for 1 < k hhlh 2 h t X1X2 Xt, where each is a union of r, r?, elements of the form Ck (i.e., % is an orbit of G(X1 o X2 o.. o Xt) ) anr r = P[C~], for 1< k < h', where h7 is the number of orbits of G(X1 o X2 o... o Xt).

37 Next, we define conditional probabilities P[Ck j CI] as before: ri PCk if Ck n ci 0 if Ck n C.= Now we can state the generalization. 1.5.4 Theorem. Let X.(1 < i < t) be the graphs described above. Then, t (1) Ig(X o X20 oXt) = Ig (X) X1H(PX.. Xt X1X2. Xt (2) H(Px.. X X1 t 1. Xt t = [ H(P X P X )I where i12 1-1 1 i-l i Yi = X1X2o oXi Proof. (1) The reasoning here is exactly analogous to the proof of theorem 1.5.1. (2) I (XloX2.. oX) I (Yt) I (Y o t) Io t g t g t-1 t' By 1.5.1 we have Ig(Yt) = Ig(Xt) + Ig(Yt-i) H(PtlXt t-Xt g t 9 t 9 g -i Yt_tXt Yt-lXt But I (Yt ) I (Yt2~Xtl) = I (Xt) + I (Y g t-l g t-2 -1 g t-l g X-2

38 Repeating this argument, we obtain t t I (Y) = I I (Xi) - I H(P X PiP g t) l i g i 2 YilXi YilX Now, (2) follows from (1). Since the cartesian and composition products for graphs (and the corresponding group operations) are associative, we have the following immediate consequences of the theorem. 1.5.5 Corollary. Let Xi(l < i < t) be graphs. Then (1) Ig(X1x X X ~ ~ ~ XXt) =)i I (Xi) g 2 i=l g - H(P P H(P. x I P' ) X1...Xt X1 ~.. Xt (2) If the Xi are connected, and for each i A j, Xi and X. are relatively prime, then Ig(X X X X2.. XXt) =i I (Xi). g 1 2 g a Proof. By theorem 1.5.4 and repeated application of theorem 1.4.7. 1.5.6 Corollary. Let Xi(1 < i < t) be graphs, and let o be graph composition. Then t (1) Ig(X.. oXt) ) I I (X) - H(PX X I X X t izl 1 2 2.. t X1X2...t (2) Let Y X1 oX2 o.. oXi, and let Ri, Si, A.i be the relations of theorem 1.4.8 defined for Y.(1 < i < t-l). If Xi is connected whenever R. 1 Ai and Xi is connected whenever S. i for 2 < i < t, then I (XlOX2o. oXt) = I (Xi). i=l g

39 Proof. By theorem 1.5.4 and repeated application of theorem 1.4.8 1.6 Applications In this section we shall examine the information content of the elements of some particular classes of graphs. We begin with the "square" grid-like structure formed by the cartesian product of a path graph Ln with itself, as shown in Fig. 1.7. (1)1) (/,2) (i,) (j;#) (I~n3) (&nt -)(/,,9(ln) +?- ('~~-/j])..-... ( ). *. (-,) Ln:Ln X Ln: nk-3 (&-3,5 - ^ b! _... _ (A-3,n) )A-L (rt-2,1), 4 (n-2,n) n-( tn-l~l)- - ( Ig () (nAZ)(n,3) (n,,) (n,n3) (n,,-.y,-, ) (nn) Figure 1.7 An n x n grid Lemma 1.6.1 Let Ln with V(Ln) = {1,2,..., n} be as in Fig. 1.7. Then (1) The orbits of G(L ) are {1,n}, {2,n-l},...+ } if n is even {l~n}, {2,n-1},...,{n l +l nisl n- l - 1, n+l n}l if n is odd

40 (2) The number h of orbits of G(L ) is given by n if n is even h =l; and n+1 if n is odd 2 (3) I (Ln) log 2 if n is even g n n-l n 1 log 2 + log n, if n is odd n 2 n Proof. It is clear that the permutation (l,n) (2,n-1)... (I, n + 1), if n is even (l,n) (2,n-1).. (n+l n+l + 1), if n is odd is an automorphism of Ln, and, hence that each of the sets listed in (1) is a subset of some orbit of G(Ln). Since d(l) z d(n) = 1 and d(i) = 2 (2 < i < n-l), and {l,n} is a subset of some orbit, {l,n} must be an orbit of G(L ). Moreover, any *eG(L ) must be an automorphism of the subgraph Ln with V(Ln) {2,..., n-l}. But L- is isomorphic to Ln 2 n n-2 so {2,n-1} must also be an orbit of G(L ). Now, (1) follows from repeated application of this argument; (2) is an immediate consequence of (1); and (3) follows from (1) and (2). 1.6.2 Lemma. Let Y be a graph. Then the mapping 9 defined by (i,j)% = (j,i) for each (i,j)h V(Y X Y), 1 < i, j < n = IV(Y)I is an automorphism of Y X Y. Proof. Clearly,4 is a permutation of the elements of V(Y x Y). Let (i,j) and (k,:) be arbitrary elements of V(Y X Y).

41 Suppose [Ci,j),(k,L)]E E(Y X Y). If j =- and [i,k]e E(Y), then [(~,j),(k,q)] = [(j,i), (L,k)]E E(YX Y); if i = k and [j,Z]~ E(Y), then again [(i,j), (k,2)]$E E(Y X Y). Similarly, if [(i,j), (k,l)]~ E(Y X Y), then [Ci,j),(k,Z)]i4 E(Y X Y). Hence, *~G(Y X Y). 1.6.3 Lemma. Suppose Ln X Ln with V(Ln X Ln) = {(1,1), (1,2), ) a. ~, (1,n),.., (n,), (n,2),...,(nn)} is as shown in Fig. 1.7. Let {is n-i+ll} (1 < i < 2-) when n is even Ai z n1l l n+l n+l {i, n-i+l} (1 < i< n1- 1), {1-} (i = n) when n is odd be the orbits of G(Ln ). Then the sets 1 <_ i < if n is even r1 < i n+l if n is odd 2n 1 < i,j < 2 if n is even and (Ai X Aj) U (Aj ~ Ai) for i A i and n+l if n is odd 1 < i,j' if n is odd are the orbits of G(Ln X Ln)Proof. It follows from lemmas 1.6.1 and 1.6.2 that each of the sets Ai K Ai and (Ai X A.) U (Aj K Ai) is a subset of some orbit of G(Ln ( Ln). Since d(l,l) = d(l,n) z d(n,l) z d(n,n) - 2, d(l,i) = d(i,l) 5 d(n,i) = d(i,n) = 3 (2 < i < n-l), and d(i,j) = 4 (i,j A 1, # n), it is clear that A1X A1 is an orbit of G(Ln X Ln). Moreover, any *EG(LnX Ln) must be an automorphism of the subgraph X1 with

42 V(X1) = {(1,2),..., (l,n-1)} U {(2,n),..., (n-l,n)} U {(n,2),..,(n,n-1)} U {(2,1),..., (n-l,1)}, and also of the subgraph X2 consisting of all points (i,j) with i,j f 1, $ n. But X1 consists of four isomorphic copies of L2 so 1 < j < n if n is even (A1 A Aj) %) (Aj X A1) for j ~ 1 and 2 -- 1 < j < n+l -1 i j 2 if n is odd are orbits of G(Ln ) Ln). Since X2 is isomorphic to Ln-2 X Ln-25 the result follows from repeated application of the above argument. 1.6.4 Lemma. Let L ) L be as above. Then n n n-2 -- -n 2if n is even H(P PLL n nn n n2 2 if n is odd n Proof. Suppose n is even. By lemma 1.6.3 and theorem 1.5.2, we need only consider orbits of the form (Ai X Aj) U (Aj X Ai) where the Ai(l < i. a) are the orbits of Ln as in the previous lemma. These orbits are (Alx A2)U (A2X A1), (Alx A3) U (A3X A1),...,(A1X Ah)U (Ahx A1) (A2x A3) LJ (A3x A2),...,(A2X Ah). (AX A2 ) (A1x Ah) U (Ahx Ah-1)

43 and there are exactly 1 + 2 +. + (h-l) h of them, where h is the number of orbits of G(L ). Since A. X A. and n I. Aj X Ai each contain four elements, we have from theorem 1.5.2 that H(PL L L)=1 h(h-1) [4 log ~ + 4 log L] nn nn n n 4h(h-1) But h = 2, so 4) n(n-2) n-2 as required H I ('L L 2 - 2 - -n-, as required. n n n n n n Now, suppose n is odd. Again we look at orbits of the form (Ai X Aj) U (Aj X Ai) as above. In this case, however, the sets Ai X Ah and Ah X Ai for 1 ~ i 4 h-l and h = each contain two elements, while all other such sets contain four elements. It is clear that G(LnX L n) has h-l orbits of the form (Ai X Ah) U (Ah X Ai), and h(h-l) - (h-) (h-l)(h-2) 2 2 orbits of the form (Ai X Aj) U (Aj X Ai) for i f h. Hence, theorem 1.5.2 gives LH(PL I L ) ={ 2 (h-1)[2 log 4 + 2 log ] nn nn n n (h-l)(h-2) 8 8 1 + (h-2 [4 log - + 4 log 4]}- - [(h-1)(4) n (h-l)(h-2) (8)] 4(h-l) [l+ h-2] = 22 2 2 n n

44 n+l Finally, since h n21 2 n+l 2n H(PNow we can state a general result for -1)wdimeioa gridL L I PL L and L be ath rahs. Then n 2 2 2 gn g f2 I m, as required. n mn 1.6..5 Theorem. Let Ln and m, be path gr aphs. TL hen I9(Ln) + I (Lm), if n ~ m _ n 2 n g theore 1.4.7 guarant nta if n = i and n is even n n- n t (n-l)2 with lemmas n if n m and n n 2gn n tively prime with respect to the cartesian product. Thus, theorem 1.4.7 guarantees that I 9 is additive in this case. When n = m, the result follows from theorem 1.5.1 together with lemmas 1.6.1 and 1.6.4. One consequence of this theorem is that IIg(LnX Ln) - 2 I (L n) <' Thus, the loss of information arising from the additional symmetries of a square grid is at most one information unit. The case of the composition of two path graphs is much simpler.

45 1.6.6 Theorem. Let Ln and Lm be path graphs. Then Ig(Ln o Lm) = I (Ln) + I (Lm) Proof. The result follows immediately from theorem 1.4.8.

CHAPTER II THE INFORMATION CONTENT OF DIGRAPHS AND INFINITE GRAPHS 2.1 Introduction In this chapter we will extend the definition of information content to finite directed graphs, and explore the implications of the measure in the case of infinite graphs. Most of the results of Chapter I will be seen to carry over to the directed case. In addition, the greater generality of digraphs will allow us to show that for any partition of an integer, there exists a digraph whose information content equals the entropy of the partition. The generalization of the measure to finite digraphs is immediate, since the automorphisms of a digraph form a group as in the undirected case. In fact, we could consider objects of a more general nature, such as graphs with loops and parallel lines. However, the structure of a digraph is sufficiently rich with respect to the information measure as to render unwarranted the added difficulty of exposition which would be incurred by such an extension. The case of infinite graphs (or digraphs) poses a more difficult problem. There does not appear to be any 7lnatural?1 way of extending the information measure to the infinite case, since it is not clear how 46

47 to assign probabilities to the orbits of the group of an infinite graph. However, we will examine the behavior of the measure on sequences of finite graphs whose sum is an infinite graph. As in the case of undirected graphs, the absence of standardized terminology and notation in the literature compels us to present a great many definitions.l We will define the general concepts here; specialized definitions will be given as the need arises. A directed graph (or digraph) X is an irreflexive binary relation on a finite set whose elements are called the points (or vertices) of X. The ordered pairs of points in the relation are the (directed) lines (or edges) of X. As before we will use V(X) and E(X) to denote the set of points and the set of lines, respectively. If V(X) = 0, X will be called the trivial digaph. A point x is said to be adjacent to y if the line (x,y) E E(X); x is said to be adjacent from y if (y,x) E E(X). X is called a symrmtric digraph if (x,y) C E(X) when and only when (y,x) C E(X). For x E V(X) we denote the set of points adjacent to x and the set of points adjacent from x by Vi (X;x) and VO (X;x), respectively; that is to say, Vi (X;x) = fy C V(X) (y,x) C E(X)3 and VO (X;x) {y C V(X) I (x,y) CE E(X). The indegree id(x) and the outdegree od(x) of a point x are given by id(x) = Vi(X;x)I and od(x) = IVo(X;x) The total degree td(x) of x is the sum id(x) + od(x). We shall call a digraph X regular of degree k if id(x) = od(x) = k for every x C V(X). 1 The definitions used here are largely those of Harary, Noran and Cartwright [16].

48 A sequence S of points x.i E V(X) (0 - i 4 n+l) and lines i e E(X) (0 - i m n) given by S = (Xoo0,Xll,, Xn tXn+1) where {i (Xi X +1),(xii +)i+,x is called a semisequence with initial point and endpoint n+. is called a sequence if i (x.,x+ ) for x S_ _ 1 1+1 O L i ~ n. A (semisequence) sequence is called a (semipath) path if no line occurs more than once in it. A (semicycle) cycle is a (semipath) path whose initial point and endpoint are identical. Two points x and y are said to be weakly connected if xzy or there exists a semipath with initial point x and endpoint y; x and y are strongly connected if x-y or there is a path, with initial point x and endpoint y, and one with initial point y and endpoint x. A digraph is (weakly) strongly connected if any two points are (weakly) strongly connected. The relation of being weakly connected and that of being strongly connected are both equivalence relations on the points of a digraph. A digraph X is said to be disconnected if it is not weakly connected, and totally disconnected if it contains no lines. X is called complete if for every x and y in V(X), (x,y) (E E(X) or (y,x) e E(X). We will use the notation K and K to denote, respectively, the complete symmetn n ric and totally disconnected digraphs of n( t O) points. As in the undirected case, a digraph Y will be called a subdigraph of X (written Y C X) if V(Y) C V(X) and E(Y) C E(X); and if V' C V(X), the digraph Y = X(V') given by V(Y) = V' and E(Y) = j(x,y) ( E(X) I x and y C V'j will be called a section digraph of X. Suppose X and Y are digraphs. Then, as before, q is an isomorphism of X onto Y if 4 is a one-one mapping of V(X) onto V(Y) such that

49 (x,y) (46 E(X) if and only if (x,y) ( = (x(),y4) e E(Y). An autonarphism of a labelled digraph X is an isomorphism of X onto itself, and the set of all automrrphisms of X forms a group which we shall again denote by G(X). It is clear that from the standpoint of the autonrrphism group, a symmretric digreph is just an undirected graph in the sense of Chapter I. So, when we discuss symmetric digraphs, we will use the terminology of Chapter I. If X is a digraph we will call X' given by V(X')eV(X) and E(X' )E(X) U I (x,y) I (y,x) E E(X)} the (undirected) graph associated with X. 2.2. The information content of digraphs Since the autororphisms of a digraph form a group, it is imnediately evident that the measure Ig given in 1.3.1 is defined for digraphs. Moreover, it is clear that 1.4.1 and 1.5.1 (and, thus, 1.4.6) hold for digraphs. Figure 2.1 shows the groups and information content of digraphs with three points.l,nfor m~at~ion Digraphs with three Points S3 3 z e,(1l23),(132) O0 e, (l2) log 3- I 3 j. 2. IwI, - I e 3 log 3 /1Z 1i\ 1 A Figure 2.1 The information content of 3-point digraphs In illustrations, the points of a digraph will be represented as points in the plane; an edge (x,y) will be indicated by a continuous line segment with an arrow pointing from x to y. If both (x,y) and (y,x) are edges, a line without an arrow will be used, as in the undirected case.

50 We begin our investigation of the information content of digraphs by defining operations analagous to those considered in Chapter I for undirected graphs. Let X1 and X2 be digraphs with V. = V(Xi) and Ei = E(Xi) for i = 1,2. The complement of X1 is the digrlaph X, with V(Xi) = V1 and E(X1) = {(x,y) / (x,y) E1, x f y, x,y E V1 The sum of X1 and X2 is the digraph X1U X2 given by V(X1l X2) = V1U V2 and E(X1 U X2) = E1U E2. As in the undirected case, the relation of being weakly connected partitions the set of points of a digraph into equivalence classes. Thus, if X is a digraph n V(X) = U V i (Vi Vj = for i f j) and Vi = V(Xi) where the i=l J Xi = X(Vi) are section digraphs of X. Moreover, when x 4 y, x and y are in the same Vi if and only if (x,y) or (y,x) is in E(X). The section digraphs X are called the weakly connected components of X. The join of X, and X2 is the digraph X1 + X2 defined by V(X1 + X2) = V1U V2 and E(X1 + X2) = E(X1U X2) U t(x,y)( x V1,yV2i The cartesian product of X1 and X2 is the digraph X1 X X2 defined by V(X1 x X2) = V1 x V2 and E(X1 X X2) = t(x,y) = ( (xl,l)' (X2'Y2) ) I x1,y1 V1, X2',y2 e V2 and either x1 = Y1 and (x2,y2) C E2 or x2 = Y2 and (xl,Y1) e E1j. The composition of X1 with X2 is the digraph X1 o X2 given by V(XloX2)= V1XV2 and E(XloX2) = t (x,y) = ( (x1,yl), (x2,y2) ) I xlY1 C V1l x2,y2 E V2, and either (xl,y1)C E1 or x1=Y1 and (x2,Y2) e E2. It is clear that the algebraic properties observed to hold for these operations in the undirected case hold for digraphs as well.

51 Of, course, they coincide with those defined in 1.4 when X1 and X2 are symmntric digraphs. The operations are illustrated in Figure 2.2. X1 X2 1 X1U X2 X1 + X2 X1l X2 X1 0 X2 Figure 2.2 Operations on digraphs Let X be a digraph. Then X can be expressed in the form X=: (b Xi.) where the X..i are weakly connected components, i=l j=j 1J and for each i = 1,2,...,r, Xi X. (1 j~ k.). As in the undirected case, it is well-known that (1) G(X) = G(X) and (2) G(X) = Sko G(X) +...+Sk oG(X ), where S. is the 1 r i symmetric group of degree ki, and o and + denote the composition and direct sum operations, respectively, defined on permutation groups. Now, it is easily seen that theorms 1.4.3 and 1.4.5 hold in the case of digraphs. We suniarize in the following 2.2.1 Theorem. Let X and X. (l4 iLn) be digraphs, and suppose Xi X (14iXn) and V(X.) fA V(X.) = for i j. Then (i) I () = I (X) g g (ii) I g(XlU X2U... U Xn ) = Ig(X) (iii) I (X1 + X2+...+ X I (X) g 1 2 n g

52 Proof. The proofs for (i) and (ii) are exactly analogous to those of 1.4.3 and 1.4.5 (i), respectively. To prove (iii), we need only note that as in the case of undirected graphs Xi + X. = X U X., and then appeal to the proof of 1.4.5 (ii). Next we will show that theorem 1.4.7 also holds in the directed case. Let X be a digraph. X is said to be prime with respect to the cartesian product if, whenever X' X1 X X2, either X1 or X2 is the identity digraph (or graph) K1. The result (Harary [15,p. 33]) used in proving 1.4.7 hinges on a theorem of Sabidussi [34,p. 456] which states that if X1, X2,...,Xn are connected prime (undirected) graphs with V(Xi) 1 V(Xj) = (i # j), then G(X1l X2U... U Xn) G(X1/ X2 X... X Xn). The proof given by Sabidussi is easily seen to carry over to the directed case if we can show that any digraph X is isomorphic to the cartesian product of prime digraphs which are unique up to isomorphism. Thus, we prove the following 2.2.2 Lema. Let Y z Y1X Y2 X... n Y be a digraph where each Yi(lL —i n) is prime with respect to the cartesian product. Let Fi = E(Yi) and F(i)= t(x,y) = ((x1,x2...xn)(yy 2.y n E(Y) (Xi,Yi) e E(Yi) Then the collection F(i) i=l is a partition of E(Y), i.e. F(i) n induces an equivalence relation on E(Y). Proof. 1) Let X be a symmetric digraph with X=X1 X XX... XXn where the Xi are prime. Then there exists a partition of E(X) given by E(i)l where E(i) = (x,y) e E(X) I (xi,Yi) G E(Xi)~ Suppose X = 1 X X2X... Xn is a digraph where each Xi is prie,E(X) A A E(Xi) and V(Xi) = V(Xi) for litn (i.e. each Xi is a subdigraph of Xi). Then, we claim that (F iil with F(i)= (x,y) e E(X)

53 A A (xi,yi) E E(Xi) i is a partition of E(X). For, suppose the contrary. Then there exists (x,y) 6 E(X) C E(X) such that (xi,yi)E) Fi C E and (xi, Yi)g F(j) C E(j) for i j. But this implies that E(i)xi E(j) / 9, which is impossible. 2) Consider the symmetric digraph X = K X K...K r1 r2 rn where E(Yi) C E(Kr) and V(Yi) = V(i%). Clearly, the Kr are prime since the cartesian product of any two graphs cannot be complete. Moreover, E(i) D F() for l5i'n. Thus, according to part 1), IF(i) i gives the desired partition of E(Y). The conclusion of lemma 2.2.2 is equivalent to the existence of a unique (up to order and ismcrrphism) decomposition of a digraph into a cartesian product of prime factors. Thus, we define digraphs X and Y to be relatively prime with respect to the cartesian product if whenever X x Z and Y ~ Yx Z, Z is the identity digraph K1. 2.2.3 Theorem. Let digraphs X and Y be weakly connected and relatively prime with respect to the cartesian product. Then I (XX Y) z Ig(X) + Ig(Y) Proof. Lenmma 2.2.2 allows us to invoke the proof given by Sabidussi [34,p. 456] to assert that G(XU Y)' G(XX Y), since X and Y are relatively prime. So, as shown by Harary [15,p. 33] for undirected graphs, G(XA Y) - G(X)X G(Y). (In general, we can now say that for any digraphs X and Y, G(X)X G(Y) = G(XX Y) if and only if X and Y are relatively prime.) The theorem now follows from 1.14.6. The situation involving the composition of two digraphs is less tractable. The (necessary and sufficient) condition given by Sabidussi [33,p. 694] for G(X o Y) to be equal to G(X) o G(Y) when X and Y are

54 undirected graphs can be generalized as follows. Suppose X and Y are A A digraphs. Let the relations R and S on V(X) be defined by A x R y if Vi(X;x) z Vi(X;y) and Vo(X;x) - Vo(X;y) x a y if Vi(X;x)U [x} = Vi(X;y)I U y and Vo(X;x) U (x- Vo(X;y)U yI and let A = (x,x) { x 6 V(X)3 (the trivial relation). Now, the condition is (*) Y is weakly connected whenever R A f and Y is weakly connected whenever S f. It is easy to see that Sabidussi's proof of necessity also shows that the condition (*) is necessary for G(X o Y) to be equal to G(X) o G(Y). However, the sufficiency proof given by Sabidussi does not appear to carry over to the directed case. Moreover, since a counterexample is not forthcoming, we shall have to be satisfied with a weaker result in the directed case. 2.2.4 Theorem. Let X and Y be digraphs. Then I (X o Y) a: I (X) + Ig(Y). Proof. This follows immediately from theorem 1.5.1 since G(X) o G(Y)_C G(X o Y), as in the undirected case. We will conclude the section by establishing a connection between the information content of undirected and directed graphs. 2.2.5 Lemma. Let G1 and G2 be permutation groups with the same object set V satisfying G14_ G2; and let P1 and P2 be the finite probability schemes constructed from the orbits of G1 and G2, respectively. Then H(P2) -- H(P1), where H is the entropy function. n. Proof. Let Pi = n (lgih), where n = Vi and ni is the number of elements in the i-th orbit of G1. Since G1 and G2 have the same object

55 set, and G1 is a subgroup of G2, each orbit of G2 will be a union of orbits of G1. So, suppose 0' is an orbit of G2 with 0' z 0i U Oj(i#j), and that every other orbit of G2 is equal to some orbit Ok(k4i,k;j) of G1. Then H(P1) - H(P2) - - Pi log Pi - Pj log pj +(Pi + Pj) log (Pi + pj) pi[log (Pi+Pj) - log pi] + pj[log (Pi+pj) - log pj] Pi log [1 + (Pj/Pi)] + pj log [1 + (Pi/j)] > 0. Now, suppose that the orbits of G1 are Oij(l < i < h', 1 < j < ri), and the orbits of G2 are given by 0o z 1 Moreover, let i n j jzl ~~~~r. ~~~~~hv Pij 3 Pi' Clearly, we must have j ri z h, the number of orbits of joi h' isl Gl, and Pi 1. It is obvious from the above that izl ri h' r. 3=J ________ H(P!) - H(P2)- Z= zij [log Pui Pi jlPij j=l H(p1) - H(P2) > 0. Since H(P1) z H(P2) if and only if G1 and G2 have the same orbits, the lemma is proved. 2.2.6 Lemrna. Let X be a digraph and X' its associated graph. Then G(X) < G(X'). Proof. By the definition of X', (x,y) E E(X') if and only if (y,x) E E(X'). Suppose 9 E G(X). Then (x,y) and (y,x) are in E(X') if and only if (x,y)or (y,x) is in E(X). But this is true if and only if (x,y)q or (y,x)4 is in E(X) which, in turn, can hold if and only if (x,y)p and (y,x)~ are in E(X'). An immediate consequence of lenmmas 2.2.5 and 2.2.6 is the following

56 2.2.7 Theorem. Let X and X' be as in 2.2.6. Then Ig(X'I) - I (X). g g 2.3 The construction of digraphs with given information content As noted earlier, an undirected graph is just a symmetric digraph, from the standpoint of the automorphism group. Thus, it is natural to expect digraphs to exhibit a greater variety of group structures than undirected graphs. For example, the smallest undirected graph (excluding K1) whose group consists of the identity alone has six points. In the case of digraphs, as we shall show presently, for every n:l there exists a digraph X with n points for which G(X) = je. This of course means that for every nl 1 there exists a digraph X with n points such that I (X) = log n. Much more can be said, however. We g will now give a construction showing that for every n > 1, there exists a weakly connected digraph X such that I (X) ni log ni where g 1=l n n ni(l-Li —h) are any positive integers satisfying h ni = n. i=l First, some preliminaries. We will call a digraph X a path of length n C(O) if V(X) = Jxo,xl,...,x and E(X)= I(xl,x2),,( Xn_l n) (if n=O, V(X) = [x}, E(X) = ); X will be called a (directed) cycle of length n(C _1l), if V(X) = xl,x2,...,xn5 and E(X) = ((XlX2), (X2'x3 )x (xXn-lxn ),(xnxl) (if n-=l, V(X) = tx, E(X) = 0 ). 2.3.1 Lemma. Let X be a (directed) path of length n( O) and Y a - n n (directed) cycle of length n( 7-> 1). Then (i) The orbits of G(Xn) consist of the individual points of X, so I (Xn) = log (n+l) g n (ii) G(Y ) has exactly one orbit V(X), so I (Y ) = 0. n g

57 Proof. (i) Let V(X) O,l,...,n7 and E(X) (0,l),(l,2),...,(n-l,n)3 as in figure 2.3; and let X' be the associated symmetric digraph. From 2.2.6 we have that G(Xn) 4 G(X'), so that each orbit of G(X ) is a subn n n set of an orbit of G(Xn). Now, the orbits of X' are n n 0n: l,n-l,,n-+l n+l + 13 if n+l is even t 0,n,,n-1,..., — n 1, n22 + 3, if n+ is odd Since od(O) = 1, od(n) a 0, 0 and n must be in different orbits, so t0 jn} are orbits of G(Xn). Hence, any automnrphism of X must be an automorphism of the subgraph X- consisting of points 1,2,...,n-1. n But X is isomorphic to X Thus, by repeating the argument, we see n n-2' that o0, 13,..., n! must be the orbits of G(X). (ii) Let V(Yn): 1,2,...,n and E(Yn) (n-l,n),(n,l) as in Figure 2.3. It is obvious that the cycle (12...n) is an automprphism of Yn' so G(Yn) has but one orbit. n. nn 2. 3 X Y n n I (Xn) = log (n + 1) I(Y) 0 g g n Figure 2.3 Path and cycle digraphs. 2.3.2 Theorem. Let n be any positive integer, and suppose P= insij is a parttition of n where n. = ni(lj 2ri) n n il i2); and i = 1,2,...,k. Then there exists a weakly connected digraph X with k n points such that G(X) has exactly r = L ri orbits, and for each i=l 1

puezuoo uo.T~z~ou-. U9tA-F2 [.TM qTIdpxap ui.od —hZ w so uo.-onmlzsuo o aqtz -y' a'nB ({ 1 %Se'E'4T } )H z [(trL Z2LZ)Z + e(s hZ+)Z + (tzB3~tZ)8 + (fZB+Z)yl]- z (X) I )I i E Z Z T TT fX + EX + zX + IX = X xl x x - X xZ X TC0 0 x he 9C E 15 ED Z3 3q E-'~ i a7rPi' 4

59 n.. there is an orbit A with IAI = n.i; and, hence, k I(X) = H(P)- ri ( ni log n. g i-l n n Proof. If n = 1, the proof is trivial. So let n>l. For each i = 1,2,...,k consider the digraph Xi=L _lX C where L is a path 1r n. r.-L 1 1 1 of length r i-l, and C is a cycle of length n.. Since L and C 1 n. 1 r.-l n. are relatively prime with respect to the cartesian product, the set of orbits of G(Xi) is just the cartesian product of the respective orbits of G(L ) and G(C ). Hence G(Xi) has exactly ri orbits each conr.-l n. sisting of n. element-s, since by lemma 2.2.8 G(Lr ) has r orbits each consisting of one element, and G(C ) has one orbit with ni elements. Now consider the digraph X = X1 + X2 +... + X. Since Xi X. for i, j, it is clear from the discussion preceding theorem 2.2.1 that G(X) = G(X1) + G(X2) +...+ G(Xk), i.e. G(X) is the direct sum of G(X1),...,G(X). Hence, the orbits of G(X) are just the union of the orbits of the G(Xi), i.e. G(X) has r orbits, ri of which each contain ni elements for i=1,2,...,k. Moreover, since each Lrl and Cn are i i1 weakly connected, Xi is weakly connected; and, thus, X is weakly connected, as required. Figure 2.4 illustrates the theorem for n - 24, P = 14,23,32 42 2.4 An extension of the information measure to infinite graphs In Chapter I we defined a graphl as an irreflexive symmetric binary relation on a finite set. By dropping the finiteness restriction, one obtains an arbitrary graph which may have infinitely many points and lines. The definitions given in 1.2 are the same in the general case with the 1To simplify the discussion, we will consider only undirected graphs, and use the notation of Chapter I.

60 following modifications: Let X be an arbitrary graph. A sequence S n (..., _n,,... ) of lines i=[xi,xi+l] e E(X) may be finite or infinite. However, as in the finite case, two points x and y are connected if there is a finite sequence S with initial point x and endpoint y. As before, the set of automorphisms of X forms a group G(X). An orbit (which may contain infinitely many points of X) of G(X) is given by jxgl g e G(X)3 for some x; V(X). Again, the collection of orbits of G(X) is a decomposition of V(X) into disjoint subsets whose union is V(X). An arbitrary graph X is said to be countable if j V(X) U E(X) is countable; X is locally finite if d(x) (the degree of x) is finite for every x 6 V(X). In what follows we will be dealing exclusively with countable graphs which may or may not be locally finite. Ideally, any extension Ig of the measure Ig to the (countably) infinite case should satisfy: A (i) Ig(X) = I (X) for all finite graphs X (ii) g(X) is defined and unique for all countable graphs X. Unfortunately, the particular extension we will examine satisfies (i) but not (ii). However, the reason for its failure to satisfy (ii) turns out to be interesting in itself, as will be seen presently. Let X be a countable graph. A sequence IX n of finite graphs X n= n with V =V(X ) and E =E(Xn) is said to converge to X as a limit (written Lim X X ) if lim V V(X) and liam E E(X) where the latter two o n r n a n limits are simply limits of a sequence of sets. Note that in general, ifAnn__ is a sequence of sets A, lim inf An= U Aand im sup A A is said to converge to A (written im AA)

61 if lian sup An lin inf An = A. Moreover, if {An}' converges to A, then nzl any subsequence {(A } also converges to A. k. kzl 2.4.1 LemIa. Let {Xn}s be a sequence of finite graphs, and let h(n) nzl be the number of orbits of Gn = G(Xn). If sup h(n) < ho, then n sp Ig(Xn) < log ho. Proof. For each n, let ki(n) be the number of elements in the i-th orbit of Gn, f(n) zIV(X), and let ki(n) k(n) Clearly, ( 1, izl h (n) ^ik (n) and - > g log - < log h(n), for each n. But Ig(Xn) h r n k i n) h(n) h(n)kn) — / -~) log - t -o. (n) ki. (n) i h.l log R3-. So, h(n) < hO for all n gives sup I (Xn)<log h0 - n g h A sequence {Xn} of finite graphs X will be nn=l n called a defining sequence for a countable graph X if Xn Xn+l for every n, and A.Xn X. Note that for any sequence {An} of sets An with n n nzl n A C A+1 for all n, the limit At An always exists and is equal to n h+l U An; so,; z Xn r U Xn. It is clear that every countable graph X n=l n=l has a defining sequence. For, if X is a countable graph, we can take V(X) z {xl,x2,...} and define a sequence {Xn I by the relations n n=l V(X1) = {xl} and E(X1) z 0 V(Xn+1) x V(Xn) U {xn+l}and E(Xn+) E (Xn) U [xn+l,y] E E(X)ly V(Xn) It is trival to verify that Xc Xn+ for all n, and ni X 5 U Xn z X. Now we are in a position to define an extension of Ig. nul

62 2.4.2 Definition. LetIX 3 be a defining sequence for a countable nl A graph X. Then the structural information content I (X;X ) of X with'g n respect to the sequence Xnx_ is given by Ig(X;Xn) = lim I (X ), ~Xn... g n n=l g n n-wg if the limit exists. If lim I (Xn) diverges, we will write ^A n g n I (X;Xn) = ~. Consider the countable graph X (shown in Figure 2.5) g n defined by the sequence [Xn where X C4 (the cycle of length four), n=l X2C4 U K2, and + 2Xn-1 for n - 2. ILI,i_ ZJ,LI Z I,I] II LU U,... X1 X2 X3 X4 x5 0c X lin X =U X n n n=l Figure 2.5 A countable graph with no unique information content Now, it is easy to see that I (Xn) ( = I0 if n is odd for g n log 3-2/3 if n is even all n. Hence, lim inf I (Xn) = and lim sup Ig(Xn) = log 3-2/3, Ayg n g n so Ig is not defined for the sequence iX However, the subn=l C =1 and iznX 2n and Z =X2 for sequences t n 2n n1 n-l n X2n-1 A n=l,2,... are both defining sequences for X, and I (X;Yn) = 0 and A Ig (X;Zn) = log 3 - 2/3. What this example points out is that the information content (whenever it exists) of a countable graph depends on the way the graph is defined (or constructed). From one point of view, this is a shortcoming of the definition. However, from the standpoint of measuring the complexity of a countable graph, it might be desirable to have a measure which is a function of the way in which the graph is constructed. For

63 example, such a measure might be useful for characterizing the relative complexity of an algorithm. For, if the computation at each step can be associated with a finite graph (or, perhaps, a digraph), the algorithm can be represented as a sequence of finite graphs. In any case, it is intuitively plausible that in certain cases the complexity of an object is not an intrinsic property of some structural feature, but rather depends on the way the object is constructed. A Now we shall examine some of the properties of the extension I. 2.4.3 Theorem. Let X be a countable graph with defining sequence X. Then Xn n=l A (i) If X is finite, I (X;Xn) exists and is equal to I (X). g n g 0o A (ii) There exists a subsequence [Yn such that I (X;Y ) exists. n=l g n Proof. (i) Since X is assumed finite, it is clear that there exists a positive integer N such that Xn = X for all n,m N. Hence n m lim Ig(Xn) = Ig(X). (ii) If the sequence {Ig(Xn)}n=l is bounded, there is a convergent subsequence {I (X )1}; if not, there is a subsequence whose limit is ing nk kk=l finite. In either case, the subsequence has a limit, so we can choose a subsequence {Yn}n=l of the defining sequence such that Ig(X;Y ) exists. Theorem 2.4.3 shows that there always exists a defining sequence for a countable graph for which I is defined. The variation in information content given by different sequences, however, can be infinite. Consider the countable graph X (shown in Figure 2.6) with defining sequence {Xn[ given by X1 = K2,X2 = 2KU K2 and for n~2 C( (jrK. if x = nl,r ji=k} iX rK {i ir n = t~lnifr irk} and m = m n {i,rlir=k} {i,:k}

64 Clearly, Ig(X2n ) = 0 for all n=1,2,...; and Ig(X2n) is of the form k (~ log k = log k where IV(X2n) I = kr. In the latter case, it is obvious that lim Ig(X2n) =-. Hence, there are defining sequences n"w ^ A for X given by Y X2 and Z X such that I (X;Y ) =0 and I (X;Z )=. n X2 2n g n g n X1 X2 X3 x4 X = lim X n Figure 2.6 A countable graph showing an infinite variation in information content 2.4.4 Theorem. Let X be a countable graph with defining sequenceeXnc nsl and let h(n) be the number of orbits of G(Xn). If sup h(n) = ho < co there exists a defining sequence Y such that I (X;Yn ) log h. n=l A g Proof. By lenma 2.4.1, sup Ig(Xn) _ log h0, so Ig(X;Yn) log ho whenever it exists. Theorem 2.4.3 assures the existence of the appropriate defining sequence. When the condition of the theorem is satisfied, it is easy to see that G(X) has finitely many orbits. However, the graph given in Figure 2.6 shows that if G(X) has only a finite number of orbits (namely, one) it is still possible for Ig(X;Xn) to be infinite. A less pathological case is characterized in the following 2.4.5 Theorem. If X is a countable graph and VE(X)I < -, g(X;Xn) 0 for all defining sequences iXnt 9 ~~~~~nn n=l Proof. Let Y be the (finite) subgraph of X defined by E(Y) = E(X) and V(Y) = Ix 6V(X){ d(x) >0t; let Ai with IAi ri(li t h) be the orbits of G(Y). Since IE(X)j 4 X, it is clear that there exists a positive integer N such that E(Xn) = E(X) for all nl N where I[ is an arbitrary defining sequence for X; and I V(Xn) I IV(Y) I

65 Let (V(Y)\ + k z IV(X). Then h r. r+k k r+k I (X) log n + nwhere izl n i n n ~V(Y) =h r. Z r. Hence, lirm I(X) izl n i zl n - r+k log n log k- 0 3i n 1 I Lr n n since kn is a monotonically increasing sequence and log x. Since the ntion of a defining sequence allows for infinite variation in the information content of the same countable graph, it is appropriate to consider various restriction on such sequences. In particular, it seems reasonable to require that the groups of the respective graphs in a defining sequence for a countable graph X reflect the orbit structure of G(X). So, let us call a defining sequence iXn' for a countable n nzl graph X a G-def2iE sequence if G(X) has a finite (infinite) number of orbits when and only when Ihn' is a bounded (unbounded) monotonically increasing sequence, where hn is the number of orbits of G(Xn). An immediate consequence of this definition and theorem 2.4.4 is 2.4.6 Theorem. Let Gx be a G-defining sequence for a countable n nzl graph X. If G(X) has finitely many orbits, there is a subsequencenY' ~~~A.~~~~~~~~~ ~nzl such that I (X;Yn) exists and is finite. Sane simple examples of G-defining sequences are given in Figure 2.7. I, A, I O. fl, rIzrIrz,... Figure 2.7 G-defining sequences.

66 Many other special types of defining sequences could no doubt be invented which would yield results more profound than theorem 2.4.6. However, it seems likely that such an investigation would be more fruitful if one were interested in particular applications of an information measure on infinite graphs. In any case, we are principally concerned in this dissertation with the prior task of investigating the behavior of the information measure on finite graphs.

CHAPTER III GRAPHS WITH PRESCRIBED INFORMATION CONTENT 3.1 Introduction The relationship between the automorphism group, and other structural properties of a graph is extremely elusive. Several necessary conditions for the existence of an autanmorphism mapping a given point into another are known; but none of them are sufficient. The simplest of these necessary conditions is the one requiring that the two points in question have the same degree. At first glance, one might expect that this condition would lead to some simplification insofar as it suggests restricting the search for sufficient conditions to regular graphs. That this is not the case is dramatically evidenced in some results of Frucht and Sabidussi, among others. In order to discuss these results, we will require some definitions. The connectivity of a graph X is the smallest number of points whose removal results in a disconnected graph or the graph K1. The chromatic number of X is the smallest integer k for which there exists a decomposition of V = V(X) into disjoint sets k VlV2...,*Vk, V = Vi VinVj = (ifI j) such that if x,y e Vi, then [x,y] 4 E(X). A subgraph X' of X is said to span X 67

68 if V(X') = V(X). A graph X is said to be fixed-point-free if there is no point x of X which is invariant under all autcnorphisms of X. Suppose a graph X contains a point x of degree two such that [x,y], [x,z] e E(X). Then the operation of removing x together with the lines [x,y], [x,z], and adding the line [y,z] is called the suppression of the point x. The operation of replacing a line [x,y] by a new point z and adding lines [x,z], [y,z] is called the insertion of the (seconddegree) point z. Two graphs X and Y are said to be homeoamorphic, written X =Y, if by means of the suppression and insertion of second-degree points, X can be transformed into Y. (Clearly, any two isomorphic graphs are homeomorphic; and for two graphs with the same number of points, the converse is also true. ) lFrucht [9] proved that given any finite group G there exist infinitely many non-isomorphic connected graphs X whose automorphism group is (abstractly) isomorphic to G. Moreover,in [11] he showed that this result still holds if we replace the words "connected graph X" by "connected regular graphs X of degree three." Thus, it is immediately evident that there exist infinitely many non-isomorphic connected regular graphs X of degree three having information content log I V(X)I. As we will indicate presently, this is also true of connected regular graphs X of arbitrary degree >_3. Sabidussi [32]generalized Frucht's results by considering other properties of graphs, in addition to regularity. In particular, he considered the following properties Pj (14_j L4) of X: P1: The connectivity of X is k, where k is an integer 1. P2: The chromatic number of X is k, where k is an integer -2. P3: X is regular of degree k, where k is an integer' 3.

69 P4: X is spanned by a subgraph X' homeomorphic to a given connected graph Y. Sabidussi's generalization of Frucht's results is contained in the following theorem [32,p. 515]: Given a finite group G of order>l 1 and an integer j(lj +4), there exist infinitely many non-homeno phic connected fixed-point-free graphs X such that (i) the autarorphism group of X is (abstractly) isormorphic to G, and (ii) X has property P.. An immediate consequence of this theorem is that for an integer j(l14jiL4), there exist infinitely many non-hcaneomorphic connected fixedpoint-free graphs X such that (i) I g(X) = log n - 1 (ii) X has property Pj This follows from the fact that any fixed-point-free graph X with IG(X)I = 2 has an even number of points, and each of the n orbits of G(X) contains exactly two points. That is to say, g n 2 n Ig(x) ~ 2 ( log 2) = log n- 1. Many (infinitely many, in fact) such consequences of Sabidussi's result can be established simply by examining the possible orbit structures of a permutation group of degree n which is iscmorphic to a given finite group. Thus, it is clear that for each of the restricted classes of graphs determined by the properties P1,...,P4, there are infinitely many graphs (within the given class), with radically different structure, having virtually any realizable information content. The point to be made in this discussion is that in studying the conditions under which a graph has a prescribed information content (or decomposition of its vertex set relative to its group), restricting attention a priori to any of the well-known

70 special cases (e.g. those defined by the properties P1,...,P4 above) does not appear to afford much leverage. Consequently, what we propose to do in this chapter is to explore a technique (based on matrix algebra) which is applicable to all finite graphs (directed as well as undirected), and to consider special cases within the framework of that technique. First we will develop an algorithm for obtaining arbitrary digraphs with zero information, and discuss the properties of such digraphs. Then we will give sufficient conditions (in terms of an algorithm for computing the automorphism group of a digraph) for two digraphs to have the same infonnation content. Finally, we will treat special cases of digraphs whose adjacency matrices have prescribed properties, with the aim of providing some tools for classifying digraphs on the basis of their information content. 3.2 Digraphs with zero information content In this section we will first present an algorithm for constructing digraphs with zero information content, and then characterize some special classes of zero information digraphs. The primary reason for presenting the algorithm (which is based entirely on a result of Chao [4]) is that it exploits the relationship between the adjacency matrix of a digraph and its automorphism group; and most of the remainder of this chapter will be devoted to exploring that relationship. In Chapter I we had occasion to use the adjacency matrix of an undirected graph. In the more general case of digraphs, the definition is precisely analogous. Let X be a digraph. Then the adjacency matrix A = A(X) = (aij) of X is given by aij = O otherwise Let F2 denote the field of integers module 2, and let Mn be the vector 2 ~~~~~~~n

71 space of all nx n matrices over F2. Then it is clear that a digraph X with n points given by V(X) and E(X) determines a unique matrix A(X)iMn Moreover, each matrix A6MMn with zeros on the main diagonal determines a unique class of isomorphic digraphs. If X is a symmetric digraph, A(X) is symmetric; and if A EMn is symmetric with zeros on the main diagonal, the isomorphic digraphs determined by A are all symmetric. Now, let X and Y be digraphs, and suppose V(X) - V(Y) 3= l,2,...,n3, A = A(X) = (aij), B = A(Y) = (bij). If ) is an isomorphism of X onto Y, then for each i,j e V(X), (ij) 6 E(X) if and only if (i,j)4 = (ip,j ))6J(Y). Thus, since V(X) = V(Y) we can view 4 as a permutation of the elements 1,2,...,n, and it is clear that ) is an isomorphism if and only if aij = bi,j. So, ( has the effect of permuting the rows and corresponding columns of B to give A. To be more precise, let Pi be the permutation matrix corresponding to BP1 = A. We summarize the foregoing observations in the following 3.2.1 Lemma (Chao [4, p. 489]) Let abe a one-one map of V(X) onto V(Y), and PC be the permutation matrix corresponding to Co. Then CT is an isomorphism of X onto Y if and only if A(X)P. =- PC A(Y). The lemma as stated by Chao applies to the case of undirected graphs, but the proof carries over without modification to the general case. An immediate consequence of 3.2.1 is the following 3.2.2 Corgjoy (Chao [4L, p. 490]) Let o be a permutation of V(X) onto itself, and P. be the permutation matrix corresponding to Cr. Then C is an automorphism of X if and only if A(X) commutes with Pa. Corollary 3.2.2 allows us to view the autororphism group G(X) as the group of permutation matrices which commute with A(X).

72 Suppose G is a transitive permutation group on the letters 1,2,...,n, G1 = gEG I lg 13 and the orbits of G1 are A 1 213, L2,..., Ak With each orbit ~ i of G1, we associate an nx n matrix B( C i)=(b8a) defined by b 1 if there is a g E G and xeAi such that ig = ( and xg = ci- O, otherwise It is clear that B(CA 1) is the identity matrix I, and that k B( i) = J, where J is the n X n matrix whose entries are all 1. Every row or column of B(C i) consists of exactly | tit ones for i = l,2,...,k. The algorithm for constructing digraphs with zero information content involves finding all digraphs whose automorphism group contains a given transitive group as a subgroup, and it is based on the following theorem of Schur (see, for example,Wielandt [42, p. 94]). Let G be a transitive permutation group acting on n letters regarded as a group of n X n permutation matrices, let V(G) =M = (mi), 1i, j, n; mij is in a commutative field F, and for Pa 6 G, PC M = MP, where the multiplication is the ordinary matrix multiplication3, and let 1 = 1~, /2,..., /Sk be the orbits of G1. Then V(G) is a vector space over F with B( il),.,B( ~ kL) as a basis. Using this result of Schur, Chao [4, p. 492] gives an algorithm for constructing all undirected graphs of X of n vertices whose G(X) to G where G is some transitive permutation group. The generalization to digraphs is immediate, so we state the algorithm in the general case.

73 3.2.3 Algorithm for constructing digraphs with zero information. Let G be a transitive permutation group on the letters 1,2,...,n. (1) Find the orbits Al =[l, A2''''' Ak Of 1where 2 k_- n. (2) Compute B( a i) for i = 2,3,...,k. (We can ignore B( A 1) since by our definition a digraph has no loops.) (3) Each B( C i), 2titk, determines a digraph (up to isomorphism), so construct a digraph X with A(X)=B( i). (4) Compute B( i) + B( A), i j, i,j = 2,3,...,k, and construct a digraph X with A(X) = B(Ci) + B(Aj). Repeat this process for all possible sums of 3,4...,k - 1 different B(CAi) matrices. (5) Include the null digraph of n points. As shown by Chao, this algorithm gives all digraphs X with n points whose group contains G. However, it does not necessarily give all such digraphs whose group is transitive, and, thus, it does not necessarily yield all digraphs of n points having zero information. In the case where n is a prime and G(X) is the cyclic group generated by the permutation (1,2,...,n), the algorithm does give all digraphs of n points having zero information. For completeness, we state 3.2.4 Theorem (Chao [4, p. 493]). Let p be a prime number, and G the cyclic group generated by (1 2 3...p). Then 3.2.3 gives all the digraphs X of p vertices with G(X) transitive; and, hence, the algorithm yields all the digraphs X of p vertices

74 having zero information. We illustrate the algorithm (and theorem 3.2.4) for the case n=5, where G is the cyclic group of order 5. G1 e= Ee, so Ai i: 1,2,...,5 and B(al),...,B(A5) are given by 0000000 0000[ 000 1 [001001 0100 01000 10000 00001 00010 00100 001001, 101000, 10000L, I00001, 000101 00010 00100 01000 10000 00001 0000 00L 010 LOO OOOO 01000 OOO0000 respectively. Let B.i B(Ai). Each of the Bi (2Liz5) determine the same class of digraphs (the directed cycle of length 5 shown in Figure 3.1(a)). The correspondence between the other digraphs shown in Figure 3.1 and sums of the Bi matrices is given by the following: (b) B2 + B3 B3 + B; (c ) B2 + B45 B4 + B5; (d) B2 + B5 B3 + B45 (e) B2 + B3 + B4; (f) B2 + B3 + B5, B2 + B4 + B, B3 + B4 + B5; (g) B2 + B3 + B4 + B50 (a) (b) (c) (d) (e) (f) (g) (h) Figure 3.1 Digraphs with five points having zero information The preceding algorithm and theorem 3.2.4 can be applied in -the construction of digraphs with prescribed non-zero information content. Let Pl P2,.'Pr be distinct prime numbers. Suppose we wish to construct r all digraphs X of n = fPi points having r weakly connected components i=1 Xi of Pi points (lai/r) so that Ig(X) = -- log n. That is to say, we want to find all X of the form X = X1(UX2.o.IJXr where IV(Xi)-= pio Theorem 3,214 guarantees -that for each i = 1,29...,r we can find all

75 (since Pi is prime) digraphs Xi such that G(Xi) is transitive. Hence, we can find all X of the desired form. Moreover, since the Pi are distinct (and thus Xi i Xj for i A j), each X has the desired information content since G(X) is the direct sum of the G(Xi). Now we prove a result which will be useful for treating special cases of zero information digraphs. 3.2.5 Theorem. Let X and Y be digraphs with V(X) n V(Y) = i. Then (i) Ig(X X Y) = I (X o Y) 0= if and only if I (X) = I (Y) O0 (ii) I (X U Y) = I g(X + Y) 0 O if and only if X 2 Y and I (X) = 0 Proof. (i) follows from the fact that G(X) X G(Y) < G(X K Y) and G(X) o G(Y) < G(X o Y), and the set of orbits of G(X)X G(Y) and G(X) o G(Y) is just the cartesian product of the orbits of G(X) and G(Y), respectively. Thus, if I (XXY) = 0 (I (X o Y) = 0),G(XXY)(G(X o Y) ) has exactly one orbit, which implies that G(X) and G(Y) both have just one orbit. The converse is immediate. If I (X U Y) = O (I (X + Y) = 0) and X 9 Y or I (X) # 0, then G(X U Y) (G(X + Y) ) has more than one orbit, which is impossible. The converse follows from theorem 2.2.1. A necessary condition for I (X) to be zero is that X be regular. (Recall that X is regular of degree k if id(x) = od(x) = k for all x EV(X)). That regularity is not a sufficient condition for X to have zero information is abundantly clear from the introduction to this chapter. However, if X is regular we can use A(X) to determine whether I (X) is zero. If X is a digraph with n points and adjacency matrix A(X) = (a. and if X is regular of degree k, then since od(i) = E aij and id(i) n j=1 = aji, it is clear that all the row and column sums of A(X) equal k. j=l Thus, by a well-known combinatorial result (see Ryser [31, p. 57]), there

76 k exist permutation matrices P P P such that (*) AX) Pi. Conversely, if there exist permutation matrices P1*..,Pk satisfying (*), on k (r) n (r) h= F j —POi -p k for each i, which implies that X is regular of degree k. r=l jz1 J Thus, we have the following 3.2.6 Theorem4 A digraph X is regular of degree k if and only if there k exist permutation matrices P1,...Pk such that A(X) P= Pi. i~l Now, from lemma 3.2.2, we know that cCrG(X) if and only if the permutation matrix Pa corresponding to o ccarnutes with A(X). An irrmediate consequence of this and the preceding theorem is the following 3.2.7 Theorm. Suppose X is a regular digraph of degree k with n points, k and A(X) = ZPi, where the Pi. are permutation matrices. Then i=l (i) Pi E G(X) (regarded as a group of permutation matrices) if and only if Pi.( Pj) =( PP ) Pi (ii) If for each i, Pi = Pri where P corresponds to a cycle of length n, then Ig(X) = 0. As an application of this theorem, consider the nine point regular digraph X of degree 2 given by 123456789 1 0 1010 0000 2001010000 31 O 000 010 0 0 0 3 1 0 00 01010 0 0 A(X)= 45 0O 0 0 0 0 1 0 1P(123)(456)(789) P(147)(258)(369) P P 7100 000010 9001000100

77 It is obvious that a and r ccmnute (C-tr z(159)(267)(348) -r C ) and, hence, by 3.2.7 (i) @ andt are in G(X). Since CO, T and CTq' generate a transitive subgroup of G(X), it is clear that GCX) is transitive, and, therefore, Ig(X) - O0. The digraph is shown in Figure 3.2. 7 8 -- Figure 3.2 A regular digraph of degree 2 with zero information. We cnctlude this section with sane miscellaneous results on zero information digrphs..3.2.8 Theorem. Let X be an n-point digraph which is neither ccmrplete nor totally disconnected,and suppose I (X) = 0. Then X contains a section digraph X' such that Ig(X') > 0. Proof. If X is weakly disconnected, then by theorem 3.2.5 (ii) X consists of at least two iscmorphic weakly connected comnponents. So X contains the section digraph X' consisting of a single point from one component together with a directed or undirected edge from another. Clearly, Ig(X') > 0 in either case. Now suppose X is weakly connected. If X is not symmetric, there exist x,y E V(X) such that (x,y) E E(X) but (y,x) 0 E(X). So the directed path of length one is a section digraph of X whicdh has positive information content. Finally, let X be symmretric (i.e. undirected). Then since X is regular, d(x) ~ d(y) for all x,y e V(X); and since by hypothesis XiKn

78 and XKn, 0 <d(x)< n - 1. Let [x,y] E E(X), and suppose that for every z C V(X), z* x, z* y, [x,z] and [y,z] are in E(X). This means that d(x) n - 1, which is impossible. Hence, there is a z e V(X) such that [x,z] E(X) or [y,z] + E(X), which implies that the undirected line of length two or the graph Kl U K2 is a section graph of X. Both of these graphs have positive information content, as required. An important class of zero information undirected graphs is the class of n-cubes. The n-cube C is defined inductively (Shapiro [37, p. 41) n by the relations C1 = K2 Cn = CnlxCl for n> 1 It is clear from theorem 3.2.5 (i) that I (Cn) = 0 for all n. Shapiro [37] investigates the problem of when a given type of graph can be embedded in C for some n. A graph X can be embedded in C if there is a subgraph Y n n of Cn which is isomorphic to X. One result obtained by Shapiro which is of interest in connection with the preceding theorem is that any tree (graph without cycles) with n edges (n + 1 points) can be embedded in Cn Now we note (Prins [28, p. 70]) that for any n >5, there exists a tree T with I (T) = log (n + 1). Hence, we have the following Theorem 3.2.9. (i) Ig(Cn) = 0 for every n > 1. (ii) For every n > 5, there exists a tree T with n edges which is a subgraph of Cn, such that I (T) = log (n + 1). 3.3 Conditions under which two digrps have the same information content In this section we will explore sufficient conditions for two digraphs to have permutationally isomorphic groups, and, thus, the same information content. So, first let us examine what it means for two groups to be permutationally isomorphic.

79 3.3.1 Lemma. Let G and H be penmutation groups of degree n with object sets A ~ai and B z bi respectively. Then Gp H (i.e. G is permutationally isomorphic to H) if and only if there exists a a E Sn such that Go z H, i.e. if and only if G and H are conjugate subgroups of Sn, the symmetric group of degree n. Proof. If G p H, there exists a one-one mapping f of A onto B and an isomorphism rr of G onto H such that (ag)f z af(g Tr ) for all a G A and g E G. Now it is clear that f induces a permutation C on the letters 1,2,...,n, defined by icr z j whenever a.f = b., and, similarly, each g E G can be regarded as a permutation of the letters 1,2,...,n. Hence, (aig)f z aif(g Tr ) implies that (ig)d = i a (g Tr ) for each i = 1,2,...,n, and every g E G. So we have gcr = a (g TT), and, finally, g r = lg a for each g E G, which means that G =H. Clearly, the steps in this proof car, be reversed to obtain the converse. Now let us briefly indicate some of the cornections between permutationally isomorphic groups and digraphs which have the same information content. It follows from lenmma 3.3.1 that the number t of groups H which are permutationally isomorphic to a given group G is just the order of the class of subgroups of Sn which are conjugate to G, and, as is wellknown, this number is just the index in Sn of the normalizer of G. Thus, t= [Sn:NS (G)]. Let X be an n point digraph, and for each g G Sn n let Pg be the permutation matrix corresponding to g. Then corollary 3.2.2 shows that g E G(X) if and only if pg1 A(X)P = A(X). So if g g H Zp G(X) there is a Ca E Sn such that G(X)a H, or, equivalently, if p every Ph where h E H has the form plpgp for some g E G(X). Consider the digraph Y with A(Y) = P A(X)P. Clearly, every h = clg v is in G(Y) sne(pv p )-(p A(X)p, )(plp) P ) = plpA( 1x)p

80 for every g E G(X). Conversely, if h e G(Y), then Ph (P iA(X)Pa )Ph' PlA(X)P, which implies that (P., P l Pl)A(X)(P. Ph P1) (PhP )- A(X)(P hP) z A(X), so that dc h -l E G(X). Consequently, we conclude that G(Y) z H, and that to each group H which is permutationally isanorphic to G(X) there exists at least one digraph Y with G(Y) z H. So if r is the number of distinct labelled digraphs Y with G(Y) G(X), then r b t [Sn:NS (G(X))]. Moreover, we know that the number r'of digraphs having the same information content is at least as great as r. We summarize these observations in the following 3.3.2 Remark. Let X be a (labelled) digraph of n points, t = [S nNS (G(X))], r the number of distinct (labelled) digraphs Y n with G(Y) P G(X), and r'the number of distinct (labelled) digraphs Z p~ 2 2 with Ig(Z) z Ig(X). Then t r r!2. (2n - n is the total nber of distinct (labelled) n-point digraphs.) Let X and Y be n-point digraphs, and Sn the symmetric group of degree n regarded as a group of permutation matrices. Then it is clear from the foregoing discussion that if P E G(X) when and only when Q- PQ E G(X) for sane Q E sn, then Ig(X) z Ig(Y). Moreover, to find G(X) we need onl.y solve the matrix equation M A(X) z A(X) M for all permutation matrices P = M. We will now give an algorithm for constructing the general solution M, and use it to derive conditions on A(X) which insure that G(X) p G(Y), and, thus, that I g(X) z Ig(Y). The matrix equation A M = M A1: Let A be an n x n matrix with entries in the field C For this discussion see Gantmacher [12], especially chapters VI and VIII.

81 of complex numbers. Then there exists a non-singular matrix U with entries in C which transformn A into Jordan canonical form. That is,.1 where Bij = is of order mij(l < < ni) for each 0 1 I. n. i = 1,2,. them... satisfy m.. = n, and A A2 IJ i=l j=l 1] 2" r are the distinct eigenvalues of A. Note that each Bij corresponds to m.. the elementary divisor ( A - Ai) 13 of A. Now, substituting U A U- for A in the equation A M = M A gives U A lU-1M = M U A Uf1, which implies that A(U 1M U) = (U-M U )A. Let MA = U 1M U. Then M- is an arbitrary solution to the matrix equation MAA = AMA. Hence, to find all solutions M of the original equation, we need only the matrix MA (which will be seen to depend on a fixed number of parameters) and the transforming matrix U. Gantmacher [12, p. 221] shows that MA is split into u2 blocks (u= ni M = (M ) corresponding to the splitting of the Jordan matrix X into blocks. Each i=l k-l block MX with a = t nt+j, B = nt+Q (1! i, k r, l j ni, t=O t=O 1~Q r nk, n0=O) is an mi.. X mk matrix where mij and mkt are the degraes of the elementary divisors corresponding to Bij and Bk,, respectively; M = if ki $ Xk, and MNa is a regular upper triangular matrix if X. = k. A regular upper triangular matrix T = (tij)(l i- p,l j< q) is defined as follows for each j = 1,2,...,r (r min{p,q}), tiq-j+i tj for 1~ is j; all other entries are zero, Note that the non-zero elements of each block MN are arbitrary pareneters. aS

82 The number N of such parameters in MA is the number of linearly independent solutions M; and N =, b where 6 denotes the degree of the greatest common divisor of the polynomials (-X i)m i,(2-.k)kZ for a = nt+ nt +, as before. Before determining which solutions M are permutation matrices, let us look at an example. 0 1 0 1 Let A t 1 0 1 Since A is symmetric, it is diagonalizable, and, 10 1 consequently, the elementary divisors of A are all of degree one. So, we need only find the eigenvalues of A to construct its Jordan form. The characteristic equation *( X) of A is given by $(X ) =2 (X2 _ 4). Therefore the eigenvalues of A are 0, 0, 2, -2; and the elementary divisors are X, A, X -2, X+2. Let A 0 001 Note that the Jordan form 0 0 2 0 L0 00-2 of a matrix is unique up to the order of its diagonal blocks (diagonal entries in this case). Since A has four 1 X 1 diagonal blocks B1,,..,B4, the matrix MA splits into 42 = 16 blocks MA = (MaB )4aB where each M is a 1 X 1 matrix. Thus, ab a b e 0 z Lc d 0 0, where a, b, c, d, e, f are arbitrary parameters. Lo 0o fj The (orthogonal) transforming matrix is given by -1 0 1-1 -2 0 2 0 U O - and -1 1 L 0-2 0 2] _0 1 |1 1-1 i llll to. 3.1J.-1 1-1.1 Finally, the general solution M is 2a+e+f 2b+e-f -2a+e+f -2b+e-f 2c+e-f 2dre+f -2c+e-f -2d+e+f M = U Mr U -1l 1 = - 2a+e+f -2b+e-f 2a+e+f 2b+e-f

83 Now we consider the problem of determining when a given permutation M n matrix is a solution M of AM = MA. Let M = U MA U1 = (xi)ni,j=l be the general solution of AM s MA, N the number of parameters of M, and Pz (Pij)n. the permutation matrix corresponding toe wherec is defined p z (Pij i,jsl by io = i, 1 i- n. It is clear that there exists a solution M = Pa if and only if there is an assignment of values to the N parameters of M which gives the matrix Pa. But each entry x.. of M is a linear combination of the same N parameters. So, P, commutes with A if and only if the non-homogeneous system of n2 linear equations in N( - n2) unknowns given by xik 1 if k ]ii li, k n is consistent. Thus, we have -0 otherwise' the following 3.3.3 Theorem. Let o be a permutation defined by ir = ji for i=l,2,...,n, P the permutation matrix corresponding to C, M = (x nj) the 1j i,j-1 general solution to MA(X) = A(X)M where X is an n-point digraph, and N the number of parameters of M. Then d e G(X) if and only if the nonhomogeneous system1 if k 1i, kn, of n linear 0, otherwise equations in N unknowns is consistent. In the preceding example the 4 K 4 matrix A is obviously the adjacency matrix of the symmetric cycle C4 of length 4. Consider the permutation d = (1 2 3 4). Ca determines a system xl2= 1, x23 = 1, x34 = 1, x41= 1, all other x.. = 0, of 16 equations in the 6 unknowns a, b, c, d, e, f. A simple computation shows that the system is consistent and the solution is given by a = d = 0, b = e = 1, c= f = -1. On the other hand, the permutation Z = (1 2) gives rise to an inconsistent system since 21= x43 = 2c+e-f. Hence,dEG(C4) and 4 G(C4). Returning to the problem of finding conditions on the adjacency

84 matrices of two digraphs which suffice for making their groups permutationally isomorrrphic, one might expect similarity to play a role. Unfortunately, with the exception of very restricted classes of digraphs, similarity of adjacency matrices is neither a necessary nor a sufficient condition for the groups of the digraphs to be permutationally is morphic. We will treat a special case first, and then give counterexamples to necessity and sufficiency for the general case. 3.3.4 Theorem. Let X and Y be n-point regular digraphs of degree 1. If A(X)-N A(Y) (i.e. A(X) is similar to A(Y)), then G(X) - G(Y), and, hence, Ig(X) = I (Y). Proof. Since X and Y are regular of degree 1, A(X) and A(Y) are permutation matrices. In general, if P1 and P2 are similar permutation matrices, they correspond to permutations dC and f2,' respectively, which have the same number of disjoint cycles of corresponding lengths. But this implies that C1l and C2 are conjugate elements of Sn. So, there is a cy e Sn -1 -l such that Cr 1d = d 2 and, thus, J1 P1 Pd z P2. Hence, we conclude that there is a permutation matrix P such that P 1A(X)P A(Y), which, according to lemma 3.2.1, means that X ~ Y; and, of course, this implies G(X) - G(Y), as required. ti (Y, t1 —-' 3 a s; 2. 3 X1 X1 X2 X2 Figure 3.3 Digraphs having non-similar adjacency matrices but equal groups Let X1 and X2 be as in Figure 3.3. Then A(X1) = O 1,

85 A() 0 x ] O and A(X2) z 10 O A(X2) 0o z 0 Lo 0 Q L) i 1 0 0 2O 1 The characteristic polynomials of A(X1) and A(X1) are XA( 2 -2) and (l2 _ 1), respectively; X 2(A 2 -4) and (2 _ 1)2 are the characteristic polynomials of A(X2) and A(X2), respectively. Thus, A(X1) and A(X1) are non-similar, and A(X2) and A(X2) are non-similar. But we know that G(X) E G(X) for all digraphs X. Hence, similarity of the adjacency matrices of two digraphs is not a necessary condition for their respective groups to be permutationally isomorphic. 7 5 8 6.2 54.X 7 Y 7 Figure 3.4 Digraphs having similar adjacency matrices but nonpermutationally isomorrphic groups Let X and Y be as in Figure 3.4, and let 0 denote an n x n matrix all of whose entries are zero. Then A(X) B1 and A(Y) 042 where B= 1 1 1and B1 02 B2 O4 1 L 0 0 1 l B2 iiilllo o 2 174 B2= 10 0 0 1. It is easy to show (Collatz and Sinogowitz [ 5, p. 72]) that A(X) and A(Y) both have characteristic polynomial ( + ). Since both matrices are symmetric, they are diagonalizable; therefore, they both have the same (linear) elementary divisors, which means that they are similar. It is obvious that G(X) is not permutationally isomorphic to G(Y), since their respective sets of orbits do not even correspond to the same partition of the number 8 = IV(X)I = IV(Y)1. Hence, similarity of the adjacency matrices of two digraphs is not sufficient to insure that

86 they have pnrmtationally isarphic groups. Theorem. 3.33 suggests a sufficient condition for two digraphs to have perutationaly iscarphic groups. 3.3.4 Theorem. Let X and Y be digraphs with adjacency matrices A = A(X) and B a A(Y). Suppose there exists a non-singular matrix U and a permutation matrix P such that U 1AU = A,...,A,....A A ] and U- -IBn r [B and UP 1B P U z B z= EB L,...,...,..., ]where A and B are the Jordan canonical forms of A and B, respectively, and the order of A.i is equal to that of Bij for each i and j ( 1' j Lni, li- r). Then G(X) p G(Y) and, thus, Ig(X) z Ig(Y). Proof. Let M and MB be arbitrary matrices which commute with A and B, respectively. Then MA U M U1 and ~ P U Ul-1 where M and are arbitrary matrices which cormute with A and B, respectively. It is clear from the structure of A and B that M C 5 (M B )t and M z (M' )t (t z= ni) have the same number of parameters and that the order of MaS equals that of M' a for 1'a, 8 ~ t. So, without loss of generality we can take MA: M, which gives MA = U MA U1 U M UM 1 and MB' P MA p-1. Hence, a matrix S commutes with B if and only if p-IS P commutes with A. In particular S is a permutation matrix which comrmutes with B if and only if P lS P comnutes with A. Thus, by lemma 3.3.1, G(X) p G(Y), as required. 33.3.5 Corollary. Let X and Y be symmetric digraphs. Suppose that X i and pi (1 cir) are the distinct eigenvalues of A(X) and A(Y), respectively, each Ai and i has multiplicity ni(l- i r), and A(X) A(Y) = A(Y) A(X). Then G(X) - G(Y) and, thus, Ig(X) = Ig(Y).

87 Proof. It is well-known (see Bellnan[ 1, p. 56]) that when A and B are symmretric matrices, AB BA if and only if there exists an orthogonal matrix U such that A U 1A U and B = U B U are diagonal matrices. If, moreover, there is a one-one correspondence f between the eigenvalues of A and B which preserves multiplicity, then U can be so chosen that the same correspondence f obtains between the diagonal entries of A and B. Thus, A(X) and A(Y) satisfy the hypotheses of the theorem with P equal to the identity matrix. That the condition given in 3.3.5 is not necessary for G(X) to equal G(Y), is shown by the following. Let X be an n-point undirected graph, A = A(X) and A z A(X). It is clear that A z J - A - I where J is the n x n matrix all of whose entries are one and I is the nx n identity matrix. So we have that A A A J - A2 - Aand A z J A - A2 A. Hence, A = A A if and only if A J = J A. It is easy to show (see Hoffman [19, p. 31]) that A J = J A if and only if X is regular. Therefore, we conclude that if X is not regular, A A A A A. But of course G(X) = G(X). We conclude the section with one further sufficient condition for G(X) to equal G(Y). The elementary divisors of an n x n matrix A are said to be co-prime in pairs if the degree of the greatest common divisor of any two of them is zero. It is shown by Gantmacher [12, p. 222] that any matrix M which commutes with A can be expressed as M = ~ aiAi(AO = I) t=0 if and only if the elementary divisors of A are co-prime in pairs. 3.3.6 Theorem. Let X and Y be n-point digraphs with A = A(X), B = A(Y). Suppose the elementary divisors of both A and B are co-prime in pairs, and A B = B A. Then G(X) = G(Y) and, thus, Ig(X) - Ig(Y). g g

88 Proof. If M commutes with A, M = aAi. So A B z B A implies M B z B M. Similarly, any M which commutes with B must also commute with A. In particular a permutation matrix P commutes with A if and only if it conmutes with B. Hence, G(X) = G(Y). If A is an n xn symmetric matrix, the elemnentary divisors of A are co-prime in pairs if and only if A has n distinct eigenvalues. Thus, we have 3.3.7 Corollary. Let X and Y be symmetric n-point digraphs. If both A(X) and A(Y) have n distinct eigenvalues and A(X)B(X) B(X)A(X), G(X) z G(Y) and, so I (X) = I (Y). 3.4 The information content of digraphs whose adjacency matrices have prescribed properties As indicated in the introduction to this chapter, digraphs of radically different structure (i.e. non-isomnorphic or non-homeomorphic) can have the same information content; and, conversely, digraphs of the same type (e.g. regular of degree - 3) exhibit as much diversity of information content as digraphs in general. Thus, it is clear at the outset that any classification of digraphs on the basis of information content will cut across most of the known groupings which are based on more direct graphical properties. The problem we are faced with is largely that of selecting graphical properties which are sensitive to the information measure we have defined. As shown in the preceding sections, the algebraic properties of the adjacency matrix of a digraph seem to constitute a "natural" choice in view of the connection between the adjacency matrix and the group of a digraph. Although we can only

89 scratch the surface in this thesis, it is hoped that the ideas and methods developed here will be useful in achieving a complete classification of digraphs on the basis of information content. In this section, we will first investigate the information content of digraphs whose adjacency matrices are of a given form. Then, retaining certain restrictions on the adjacency martrices, we will examine the information content of some special classes of digraphs. Finally, we will discuss the information content of the Kronecker product of digraphs. We will begin with two simple cases which illustrate the method of the preceding section. Let X be an n-point digraph whose adjacency matrix A = A(X) has the following form 0 1 al2a13...aln n A z 0 1 aL23...a2nj. Aisa strictly upper triangular matrix o 00......,O with ones on the first super-diagonal; X is an acyclic digraph which contains the (directed) path Lnl as a subgraph. Since A is strictly upper triangular with non-zero entries on the first super-diagonal, it is nilpotent of index n. (I.e. An = 0, An-1 * 0.) Hence, A has the one elementary divisor kn. This implies, in particular, that a matrix M cormmutes with A if and only if M is a polynomial inA. So, suppose A M = MA. Then M = ciAi for some scalars J= ci(le in - 1). Now, consider the matrices M' I cAi where not i=l all the ci (1~ i6n - 1) are zero. It is clear that any matrix of this form is strictly upper otiangular, and, thus, cannot be a permutation ma-trix. So, Mn c0 +N C'c0 P 0) cannot be a penrmutation miatrix. We conclude that the only permrutation matrix which corminutes with A is

90 the identity matrix I. Since the same argument applies to a digraph Y with A(Y) z AT, we have the following 3.4.1 Theorem. Let X be an n-point acyclic digraph which contains the (directed) path Ln_1 as a subgraph, and whose adjacency matrix A(X) is strictly upper (lower) triangular. Then Ig(X) = log n. Now consider a digraph X with adjacency matrix A z A(X) of the form 0 1 1 1... 1 0 0 1 1... 1 A a310 0 1... 1 ani an,n-_20 A has all ones above the main diagonal, zeros on the first sub-diagonal and arbitrary entries elsewhere. Since A(X) z J - A - I where J is the matrix all of whose entries are one and I is the identity matrix, it is clear that X satisfies the conditions of the theorem. Thus, since I (CX) I (X), we have g g 3.4.2 Corollary. Let X be an n-point digraph with V(X) = {1,2,...,n} Suppose (i,j)E E(X) ( (j,i)E E(X) ) for 1 tli<j n and (i + 1, i)4E(X) ( (i, i + 1) E(X) ) for l_~ i_ n-l. Then I (X) = log n. Another class of digraphs whose adjacency matrices are particularly easy to analyze are those X for which A(X) is a permutation matrix, i.e. regular digraphs of degree one. We have already shown (lemma 2.3.1 (ii)) that if X is a (directed) cycle of length n, Ig(X) = 0. Note that this follows immediately from the fact that AX) commutes with itself and the permuatation corresponding to A(X) is a cycle of order n, which implies that G(X) is transitive. Mbre generally, let X be an n-point regular digraph of degree one,

91 and let the permutation a corresponding to A(X) be of type [rl,r2,...,rn] where ri denotes the number of disjoint cycles of order i in the decomposition of a. It is clear that X = rlXUr2X2 U... U rnXn where Xi is a (directed) cycle of length i and riXi denotes the digraph YiU Yi2 U... U Yir with Y.ij Xi for j = 1,2,...,ri. Since G(X) 1 is the direct sum of the G(riXi) for ri A 0, we have 3.4.3 Theorem. Let X be an n-point regular digraph of degree one, and let o, the permutation corresponding to A(X), be of type [rl,r2,...,mrn]. Then I (X) = i ri log ri g 1l n n An immediate generalization of 3.4.3 is 3.4.4 Theorem. Let X be an n-point regular digraph of degree k with V(X) = {1,2,...,n }, A(X) = Pnl + pn2 +...+ pnk where P is a permutation matrix corresponding to the permutation a of type [r1,r2,...rn] and the ni(li-k) are positive integers. Then I(X) - 3log jlj g'=1 n n Proof. Since X is regular, the n. must be pairwise distinct. Moreover, since A(X) is a sum of powers of the same permutation matrix, (a,b) E E(X) if and only if aani = b for some i = 1,2,...,k. Hence, the (weak) components of X correspond to the cycles in the decomposition of a, and, as in the previous theorem, X = r X U rXU...U rnXn 1 1 1 22 n n where Xi is a (weak) component of X, from which the result follows. As noted in the preceding section, when the elementary divisors of an n x n matrix A are co-prime in pairs, A M - M A if and only if n-l M =; c.Al. Using this restriction on the adjacency matrices of 1 arbitrary regular digraphs, we obtain the following

92 3.4.5 Theorem. Let X and Y be n-point regular digraphs of degrees k and k respectively, such that rl r2 rk A = A(X) z P0 + P0 +. + P s1 s2 Sp B 5 A(Y) z Q0 + Q0 + *** + QO where P0 and Q0 are permutation matrices. Moreover, suppose P0QO z QP0,z and the elementary divisors of A are co-prime in pairs. Then Ig(Y) 6 Ig(X) with equality if the elementary divisors of B are coprime in pairs. Proof. Since the elementary divisors of A are co-prime in pairs, M A = A M if and only if n-l n-l r1 r2 rk = ciAi =' zci(P0 + P0 + + kP0 i Thus, any matrix M which commutes with A is a polynomial in P0. In particular, any permutation matrix P which commutes with A is a polynomial in P0. But P0 commnutes with Q0, so P must commute with B. Hence, G(X) 4 G(Y), which by lermm 2.2.5 implies that Ig(Y) _ Ig(X). Clearly, G(Y) can be shown to be a subgroup of G(X) by the same argument when the elementary divisors of B are co-prime in pairs. Now we turn to the case of symmetric digraphs, or, more simply, graphs. Let A be an n x n symmetric matrix with real entries. Then, as is well known, there exists an orthogonal matrix U(U1 = UT) such that A = U -A U is diagonal. Moreover, U can be chosen so that its columns are theeigenvectors of A, in which case the diagonal entries of A are just the eigenvalues of A, i.e. A is the Jordan normal form of A. Thus, in the case of an n-point graph X (whose adjacency matrix is, of course, synmetric) we need only the eigenvalues of A(X) and a set of n linearly independent eigenvectors of A(X) in order to be able to

93 construct an arbitrery matrix which comtmutes with A(X). Results relating the characteristic equation of the adjacency matrix of a graph to certain graphical properties are given in Collatz and Sinogowitz [ 5], Finck and Grohmann C 8], Finck E 7], and Sachs [36]. Although the results in these papers simplify the task of finding the eigenvalues of the adjacency matrix of a graph in special cases, they do not deal with the construction of the transfonning matrix, and, thus, are of limited applicability in the present context. We will treat the case where the adjacency matrix A = A(X) of an n-point graph X has n distinct eigenvalues. Let U C (u)ij be an orthogonal matrix whose columns are the eigenvectors of A, and let MA be an arbitrary matrix which carmites with A = U 1AU. Then 1 0~ ~Cn where the ci (1' is n) are arbitrary parameters, and any matrix M = (mij) satisfying A M - M A is given by M = UMPU 1 UM-kUT - (- Ckuikujk)n Clearly, mij = mji, so that M is symmetric. If, in particular, M is a permutation matrix, this means that M2 = I. So, in this case, every Q(# e) in G(X) (which, of course, corresponds uniquely to a permutation matrix M satisfying A M = M A) is of order two. Among other things, this implies that G(X) is abelian. The following theorems characterize the information content of a graph whose adjacency matrix has n distinct eigenvalues. 3.4.6 Theorem. Let X be an n-point graph, and suppose A = A(X) has n distinct eigenvalues. Then (i) Ig(X)> 0 ifn>2 g

94 (ii) There exist non-negative integers ni(O i* r) such that n0 2 r n + 2 2 ni z n and Ig(X) z log n + n (1 +- - ni log ni) igl n Proof. (i) follows immediately from the fact (Chao [ 3, p. 291]) that for n >2 there exists no graph whose group of automorphisms is transitive and abelian. To show (ii) we need only note that since every a (# e) in G(X) is of order two, the number of points in any orbit of G(X) is either one or a multiple of two. Letting nO be the number of orbits with one point, and 2n.i(1 i! r) the number of points in each orbit containing nmore than one point, we obtain r 2n. r g(X)= n0( log n) +nlog n log n + r 2ni(log n-log 2n.i) 0(- i=l n 2n. i[nn-o 1 i l -log n + — (1 +log2n llog ni) (1 as i1i1 required. A permutation group G with object set V is said to be semi-regular if for each x E V, Gx = {g E Glxg = x} = {e}, i.e. the group consisting of the identity alone. If a permutation group is semi-regular, every orbit has the same number of elements; moreover, it is clear that there can be no x e V such that xg = x for all g G unless G = {e}. 3.4.7 Theorem. Let X be an n-point graph. Suppose A = A(X) has n distinct eigenvalues, and G(X) is semi-regular. Then I (X) = log n if n is odd g log n - log IG(X)J if n is even Proof. Since GX) is semi-regular, n = hm where h is the number of orbits of G(X), and each orbit contains m elements. So, Ig(X)=h(m log ) log h. Now, by the previous theorem we know that either m = 2k(k al) or m = 1, and h~2(since Ig(X)>'O). It is clear that if n is odd, m = 1, for g

95 otherwise m = 2k gives n r 2hk. So, in this case I (X) = log n. For a G(X), let Ch(a) denote the character of a, i.e. Ch(a) z I{ x E V(X)I xa z x } I. It is well known (see Scott [38, p. 256]) that Z Ch(a) z h IG(X) I. Since G(X) is semi-regular, the only oa G(X) a e G(X) with non-zero character is the identity, and Ch(e) = n. Thus, Ch() = n = h IG(X)I which gives h = IG(X)I, as required. Let X be an n-point graph, and again let A - A(X) have n distinct eigenvalues. In addition to what we have already observed in this special case, we can make use of the fact that any matrix which commutes with A is a polynomial in A. (It is clear that if an n x n matrix has n distinct eigenvalues, its elementary divisors are co-prime in pairs.) Suppose A = UAU, and A = 2 where the X i (1c- i n) are [0 ex the eigenvalues of A. Moreover, suppose M is a permutation matrix satisfying M A = A M. Then n-1.1 n-1 - M E a.AL = ai(UU-)=i =i aiUA) ] i=O i=O i=0 n120 ~ ~ - O L~ ni. aiX M2 con-ls2 Furthermore, we know that M I so that ( ai,)2 = 1, and, consequently n-l. Z aiXr equals 1 or -1 for 1s< r.n. Now, let a = (a, al,...,an1)T and i=0 c = (l, c2,...cn)T be column vectors with each ci(l< i n) equal to 1 or -1. For fixed c, consider the non-homogeneous system of n linear equations in the n unknowns a0, al,... an l given by D a = c, where D is

96 the Vandermnde matrix 2 n-i D2 n-1 1 2 n2" 2 D 1 2 1n n Xn Since the X r(l r sn) are distinct, det(D) # 0, so each fixed vector c determines a system with a unique solution a. Hence, if M is a permutation matrix which commnutes with A, there exists a c such that D a z c has a n-l1 c 0 unique solution a and M z a U-1 U 2~0 U 2 n Of course, not every c will determine a system D a = c whose solution a n-li gives rise to a permutation matrix M = aiA. In fact, at most half of the possible vectors c can give permutation matrices. This is so because each a C G(X) is a product of disjoint transpositions, and each transposition contributes eigenvalues 1 and -1 to the matrix associated with a. Therefore, it is clear that if M is a permutation matrix and M A = A M, then the number of ci 1 is at least as great as the number of Ci = -1. Since the number of different vectors c is 2n,| G(X) 2nl-1 Now, we state a criterion for G(X) to be semi-regular. 3.4.8 Theorem. Let X be an n-point graph whose adjacency matrix A = A(X) has the n distinct eigenvalues Xi(l1- i~ n), and let a, c, D be as above. n-l Suppose P / I is an arbitrary permutation matrix with P I= aAlA where n i- 10 a satisfies D a - c. Then if ci = 0, G(X) is semi-regular. i=l Proof. It suffices to note that if c = O, then the character of the permutation a corresponding to P is zero. This follows from the fact that Ch(a) = tr(P) = tr(U p U) where U1 A U = A is the Jordan normal form of A.

97 But u-lp U c2., so Chi() = lci The foregoing discussion embodies an algorithm for constructing the grou) of a graph whose adjacency matrix has all distinct eigenvalues. Although frrn a canputational standpoint it is quite lengthy, it is a slight improvement over the general algorithm given in the preceding section. For completeness we state 3.4.9 Algorithm. Let X be an n-point graph whose adjacency matrix A z A(X) has the n distinct eigenvalues Xi(l< i n). (1) Choose a vector c = (cl,c2,...,cn)'wheeci 1 or ci z -l(l< i_ n) and ci > 0 (2) Solve the equation D a = c for a = (aO al..a, 1a T where D is the Vandermonde matrix given above. (3) Canpute the matrix M = aiA; if M is a permutation matrix, i1=0 then the permutation aoroesponding to M is in G(X). (4) All a G(X) are obtained by repeating steps (1) - (3) until the admissible c are exhausted. We conclude the section with a brief discussion of a product defined on digraphs, which lends itself quite naturally to a matrix interpretation. Let X and Y be digraphs. The Kronecker product of X and Y is the digraph X @ Y given by V(XOD Y) = V(X)x)V(Y) and E(X@ Y) = {(uv)((xlyl),(x2,Y2) (x1,x2) E(X) and (Y1,y2)6 E(Y)}. The Kronecker product of undirected graphs is treated in Weichsel 141]; digraphs are considered in McAndrew [26]. An equivalent definition can be given using the adjacency matrices of X and Y. Let A = A(X) = (aij)

98 and B = A(Y). Then the Kronecker product of X and Y is the digraph X ~ Y with A(X Y) = AO B, where A d B = (a iB) is the Kronecker1 (tensor, direct) product of A and B. A simple consequence of this definition is 3.4.10 Theorem. For any digraphs X and Y, I (X Y) - I (X) + Ig(Y) Proof. Let A - A(X) and B = A(Y). Suppose P and Q are permutation matrices which ccmnute with A and B, respectively. Then (P0 Q)(A@ B)(Po Q)-1 = (p~0 Q)(A~ B)(P-1 Q -1) (P A p l) & (Q B Q-1) = AO B, so P ~ Q commutes with A ~ B. Hence, every permutation a corresponding to a permutation matrix P ( Q where P and Q commute with A and B, respectively, is in G(X ~ Y). Now, we note that if P and Q correspond to permutations a 6 G(X) and T E G(Y), respectively, then P@ Q corresponds to (c,T) E G(X)x G(Y). For suppose P = (Pij) is nxn and Q = (qij) is mx m and the rows (and col umns) of P Q are numbered (i,j), 1 i n, 1 j _ m. Then the (i,j), (k,z)-th entry of P @Q is one if and only if PQk = 1 and qjQ = l, which is the case if and only if ia = k and jT = R. The result now follows frCn le1rma. 1.4.6. 1See MacDuffee [24, pp. 81 - 85] and Marcus and Minc [25, p. 8] for a discussion of the properties of the Kronecker product of matrices.

99 X: Y: X Y: Y SY C(2) () (,)(., (C,b) a)(C, Ig(Xs Y) = Ig(X) + Ig(Y) Ig(Y Y)42 Ig(Y) Figure 3.5 The information aontent of the Kronecker product of graphs. Let a and T be permutations of orders m and n respectively, corresponring to the permutation matrices P and Q. Then it is clear that the permutation wr corresponding to P 0 Q has order r = kcm(mn). If m and n are relatively prime, then r = mn. So we have 3.4.11 Theorem. Let X and Y be m and n point regular digraphs of degree one, with A - A(X) and B = A(Y), and let m and n be relatively prime. Then Ig(X~ Y) = 0. Proof. Since m and n are relatively prime, the permutation corresponding to AI B is of order. mn. Thus, by lemma 2.2.8 (ii), Ig(XZ Y) = 0. If A and B are nilpotent matrices of indices m and n, respectively, then A ~ B is nilpotent of index r _ min {m,nJ since (A 0 B)r Ar B It is also obvious that if X and Y are digraphs with strictly upper (lower) triangular adjacency matrices A = A(X) and B - A(Y), then A ( B is strictly upper (lower) triangular and X ) Y has at least two weak ccamnponents. Thus, we have 3.4.12 Theorem. Let X and Y be m and n point a'cyclic digraphs which contain the (directed) paths Lm_1 and Lnh1 respectively, as subgraphs. Suppose A(X) and B(X) ax: strictly upper (or lower) triangular. Then Ig(X ~ Y)'- Ig(X) + Ig(Y).

100 Proof. By theorem. 3.4.1. Now we observe (MacDuffee [24, p. 84]1) that the eigenvalues of AO B are precisely the products of the form X ij where Xi and.j are eigenvalues of A and B respectively. Moreover, if U- A U = A1 and -1 V BV B1, then (UV)*(A B)(U V)-i (F1 AU) (VBV) 1 Al B1. So, if A = 1A U and B = V B V are the (diagona.l) Jordan normal forms of A and B, respectively, then (U ~ V) -(A X( B)(U $ V) = ~A B is the (diagonal) Jordan normal form of A 0 B. Hence, if both A and B can be transformed into diagonal form, and we kncw the eigenvaalues and transforming matrices for both A and B, then we can immediately construct the general solution of the matrix equation M(A ~ B) = (A X B)M using the method of section 2.4. For Completeness, we state 3.4.13 Theorem. Let X and Y be digraphs with A = A(X) and B = A(Y). If the Jordan normal forms A = U A U and B = V B V of A and B are diagonal, then every a e G(X@ Y) corresponds to a permutation matrix of the form (U ~ V)MX'B(U-1 & V-1) where MA X ~ is a matrix which commutes with A 6 B.

CHAPTER IV CONCLUSION: ENTROPY MEASURES AND GRAPHICAL STRUCTURE 4.1 Introduction In this chapter we will discuss an entropy measure Ic defined with respect to a class of chromatic decompositions of a finite undirected graph. First, we will examine the behavior of this measure on arbitrary finite undirected graphs, and then specialize to particular cases. Second, we will compare Ic with Ig; finally, we will discuss the significance of the notion of graphical information content and suimarize ou results. Once again we require some definitions.l A hoormrphism of a graph X into a graph Y is a mapping 0 from V(X) into V(Y) such that whenever Ex,y] e E(X), [x,y] =- [x4,yo] 6 E(Y). An equivalent way of defining this notion is to define an elementary hcomorphism of a graph X as the identification of two non-adjacent points; then a homomorphism is just a sequence of elementary hcmomorphisms. * is called a full hommrorphism of X into Y if Exo,yo) E E(Y) implies that there exist points u,v e V(X) 1The definitions given here are largely those of Hedetniemi [17]. 101

102 such that x~ = u, y -= v4 and [u,vl] E(X). The image of X under the horomrorphism. is the graph X+, with V(X4) = {x% I x G V(X)} and E(Xq) = {[x+, y0] I[x,y] E E(X)}. Clearly, X4 C Y if 0 is a homomorphism of X into Y; moreover, X4 is a section subgraph of Y if 4 is a full homomorphism. If 0 maps V(X) onto V(Y), then 0 is called a homomorphism of X onto Y. Note that if 0 is a full homomorphism of X onto Y, then E(X)O = E(Y); if, in addition, 0 is one-one, then 0 is an isomOrphism. A homomorphism q is said to be of order n if n = IV(Xo)l, and is complete of order n if XO = K. n A coloring of a graph X is an assignment of colors to the points of X such that no two adjacent points have the same color. An n-coloring of X is a mapping f of V(X) onto the set {l,2,...,n} such that whenever [x,y] e E(X), xf J yf, i.e. a coloring of X which uses n colors. An n-coloring f is complete if for every i,j with i ~ j, there exist adjacent points such that xf = i and yf - j. A decomposition {V }k of 1 i=l the set V(X) of points X is said to be a chromatic decomposition of X, if x,y E Vi imply that [x,y] ~ E(X). Clearly, if f is an n-coloring of X, the sets {x e V(X) xf = i} for i = 1,2,...,n form a chromatic decomposition of X; conversely, a chromatic decomposition {Vi}n determines an n-coloring f. Thus, the sets V. are called i=1 color classes. The chromatic number K(X) is the smallest number n for which X has an n-coloring, or, equivalently, the smallest n for which X has a chromatic decomposition with n color classes. Note that a graph X can have more than one n-coloring (or chromatic decomposition with n color classes). X is called n-chromatic if K(X) = n. The following reearks concerning the relationship between homomorphismr

103 and n-colorings (illustrated in Figure 4.1) are necessary for the sequel. It is easy to show (Hedetniemi [17, p. 10] that a graph X has a complete n-coloring f if and only if there exists a complete hcmmorphism ~ of X onto Kn. From this it follows that if K(X) = n, then X has a complete homorrmorphism of order n; and that the smallest order of all hormomorrphisms of a graph X is just the chromatic number ic(X). Thus, it is clear that to each chromatic decomposition {V i}n of an i=l n-chromatic graph X, there corresponds a homomorphism ~ of X onto K such that each Vi is of the form {x~= u Ix e V(X)} for some u e V(Kn). 1 n C aH b d e caea02adi ed *1: a,e + a 2: a,d + d C c+ c d + d 4- coloring: 3 - coloring: fl: a,e + 1 f2: a,d + 1 b + 2 b,e + 2 c +3 c + 3 d +4 Figure 4.1 Illustrations of homomorphisms and n-colorings 4.2 The chromatic information content of a graph. Since the automorphism group of a graph X gives rise to a unique decomposition of V(X), we were able to define i (X) as the entropy of a unique finite probability scheme associated with X. As we indicated

104 above, there is, in general, no unique chromatic decomposition of a graph. So, in order to define a unique information measure which reflects the chromatic structure of a graph, we shall have to consider maximizing or minimizing the entropy function over a certain class of chromatic decompositions. For reasons which will become clear presently, we choose to minimize. 4.2.1 Definition. Let X be a graph with n points, and V = {Vih (lvii ni(V) ) be an arbitrary chromatic decomposition 1 i=l of X where h = K(X). Then the chromatic information content IC(X) of X is given by Ic(X) = I n log The principal reason for restricting the class of chromatic decompositions, over which to minimize, is convenience, since a great deal is known about the chromatic number of a. graph. Although it appears likely that IC(X) gives the minimum over all chromatic decompositions, we have not been able to prove it, and, of course, no counterexample has yet been found. The following theorem shows that in certain cases, IC(X) does give the minimum over all chromatic decompositions. 4.2.2 Theorem. Let X be a graph with n points and V {V.ik (Vil = ni(V,k) ) be an arbitrary chromatic decomposition i=l of X. Suppose X does not have a complete k-coloring for k > h = K(X). Then A ^ min k ni(V,k) ni(V,k) Ic(X) V,k { - 1log 3 11 Proof. Let f be the k-coloring corresponding to a chromatic decomposition

105 {Vi}k for k > h. Since f is not canplete, there exist i and j (i j) jzl such that [x,y] ~ E(X) for every x E Vi and y E Vj. So, without loss of generality, let i = k - 1 and j = k, and let {U}k-1 be the chrcnatic i3l decomposition given by Ui z Vi for 1 _ i c k-2 and Uk_1 = Vk1U Vk. Then the respective ntpie of the finite probability schene Pk and Pk-l asocited with {V} and {Ui}k-1 are given by itk izl k(Pk) - ni ni H(Pk) = - 1- log and H(Pkl) k-2 ni ni nkl+ k nkl+ nk log -.. log -. 1 n n n Hence, H(Pk) - H(Pk1) [nk_1 log + nk log n k kl+nk) log n ]'k-1 "k k n-i log nk-l - nk log nk +(nk_l+ nk) log (nk _ + nl)] 1 rk + l> n {nk_-[ilg (1 + n k[log (i+k-i) ] } _0. nk-1 So, for each chromatic decomposition of X with k( > K(X) ) color classes having corxesponding probability scheme Pk, there exists a chromatic decosposition with h( = K(X) ) color classes having probability scheme Ph such that H(Ph) _ H(Pk). This means that a chrcnatic decomposition of X, which gives rise to a scheme with miniiJl entropy, must have cK(X) color classes, which proves the theorem. Figure 4.2 illustrates the fact that a greph can have different chroatic decompositions with a fixed number of color classes.

106 6 V1: {a,b,e,f}, {c}, {d} V2: {a,d}, {c,e}, {b,f} Figure 4.2 Chromatic decompositions of a graph Since the minimal order of all homomorphisms of a graph X is K(X), Ic(X) can be interpreted as the amount of information needed to construct a complete homromrphism of mini.jl order, or, equivalently, as the amount of information needed to construct a K(X)-coloring. If X is taken to be a planar graph which corresponds to a map (i.e. the points of X represent territories and two points x and y are adjacent if and only if their respective territories have a cormmon frontier), then I (X) can be viewed as the amount of information needed to color the map (using as few colors as possible) so that no two bordering territories have the same color. Another closely related interpretation of Ic is in terms of the notion of independence. A set S of points of a graph X is called independent if no two points of S are adjacent in X. (Note that the color classes of a chromatic decomposition are independent sets.) The number of points of X in a maximally independent set is the independence number of X. Intuitively speaking, IC(X) is inversely related to the number of points in a maximally independent set. This is clear for the complete graph and the null graph, since Ic (K ) = log n (K(K ) = n) and Ic(K%) = O (K() = 1); and the independence numbers of Kn and R1 c n n n n~~~~~~

107 are 1 and n, respectively. Of course, the relationship is only suggestive since two graphs with the same independence number can have different chromatic information content. 4.3 Properties of the measure I In this section, we will prove some general results concerning chromatic information content, and then look at the behavior of Ic on uniquely n-colorable graphs, Kronecker product graphs, and trees. 4.3.1 Theorem. Ic(X) < log K(X) for any finite undirected graph X. Proof. This follows immediately from definition 4.2.1 using the same argument as in lemma 2.4.1. Now, we give some results which are simple consequences of theorem 4.3.1 and of known facts about the chromatic number of a graph. 4.3.1a Corollary. For a graph X and complete homomorphism, Ic(X) < Ic(X). Proof. K(X) < K(X~), and I (X0) = log K(X(), since X4 is complete. Various bounds for the chromatic number of a graph are known. It is obvious that upper bounds are directly applicable in the present context. We use one such bound in the following 4.3.b Corollary. Let X be a graph with dO = d(x). Ten x Ic(X) < log (do + 1). Proof. This follows from the fact that K(X) < do + 1. If X and Y are graphs with the same set of vertices, K(X U Y) < K(X) ~ K(Y); if V(X) n V(Y) =, then <(X U Y) = max{K(X),K (Y)}. So, we have

108 4.3.1c Corollary. Let X and Y be graphs. Then (i) Ic(X U Y) < log K(X) + log K(Y) if V(X) = V(Y) (ii) Ic(X U Y) < log (max {K(X), K(Y) } ) if V(X) n V(Y). The following relates the chruamatic information content of a graph to that of its complemrnt. 4.3.1d Corollary. Let X be a graph with n points. Then (i) IC(X) < log [n - K(X) + 1] (ii) I(X) < log [ ( 2 11 C < log - log K(X) Proof. (i) and (ii) follow from the inequalities 2nr < K(X) + K(X)' n+l and n < K(X) K(X) < ) respectively. 4.3. le Corollary. For graphs X and Y, Ic(X + Y) < log[K(X) + K(Y)] Proof. The result follows from the fact that K(X + Y) = K(X) + K(Y). Hedetniemi [17, p. 14] calls a graph X uniquely k-colorable if it has only one homomorphism of order k, i.e. if for any two honmomorphisms 1' and o2 of X onto K, and any two points x,y, x1l = Yo1 if and only n if xO2 = Y$2' Uniquely k-colorable graphs are particularly well-suited for our purposes, since if X is uniquely k-colorable, where k < n = IV(X)I, then K(X) = k and X has a unique chromatic decomposition with k color classes. Thus, if {V }k with Vii = ni. is the (unique) chromatic deil k n ni composition of a uniquely k-colorable graph X, Ic(X) = log cn 4Figure 4.3 shows some uniquely k-colorable graphs.

109 2- oolorable 3- colorable Figure 4.3 Uniquely k-colorable graphs Since the task of computing Ic (X) is considerably simplified in the case of uniquely k-colorable graphs, it is worthwhile trying to determine such graphs. Hadetniemi [17, p. 16] mentions that Kn and K - x (the graph formed by removing a point from K ) are uniquely n- and (n-l)colorable; K is uniquely 1-colorable, and all connected bipartite (2-chromatic) graphs are uniquely 2-colorable. The same author also shows that X z X1 + X2 is uniquely k-colorable if and only if X1 and X2 are, respectively, uniquely kl- and k2- colorable where k = kl + k2. 4.3,2 Theorem. Let X1 and X2 be uniquely kl- and k2- colorable graphs with m and n points, respectively. Then c( 1+X2)%j Ic(X+c 2 nm+n k m. m. -c 1 log m i-l k2 n. n. and Ic(X2) z I n log -. Then it is clear that 1=l k1 m. m. k2 n. ni c t 1 - mn1 log m+n'(Xl+X2) 3- om+n m+n m+n i=l k i=l m+n [I mi log m. + n. log ni - (m+n) log(m+n)] i=l kli k 1 logm C [ X-i log mi ni log ni i-l i=l

110 = log (m+n) - -1- (m log m + n log n - m I (Xl) - n I(X2)), from which the result follows. In particular, if X1 - X2, we have 4.3.2a Corollary. Ic(X1 + X2) = Ic(X) + 1 where X1 and X2 are uniquely k-colorable graphs isomorphic to X. Proof. It is obvious that any two isomorphic graphs have the same chromatic information content. So, setting I (X1) = Ic(X2) = Ic(X) and m = n in the theorem, we obtain the desired result. As an example, consider the path L2 of length two. I(L2) = log 3 -3 and Ic(L2 + L2) log 3 + = Ic(L2) + 1. As an additional basis for comparison with Ig, we consider the behavior of Icon the Kronecker product of two graphs. Hedetniemi [17, p. 26] points out that if X = X1 X2, then either there exist homomorphisms $1 and ~2 of X such that X ~1 = X1 and X ~2 = X2, or X1 or X2 is totally disconnected. Using this fact, he proves some results concerning K(X1 (> X2) which we summarize as follows. 4.3.3 Lenma. Let X and Y be graphs. Then (i) K (X@Y) — min { K(X), K(Y)} (ii) K (X OX) = K(X) (iii) If X Ym YV - Y, then K(XSY) = K(Y), and, hence K(Y) -K(X). An irrnediate consequence of the lenma is 4.3.4 Theorem. Let X and Y be graphs. Then (i) Ic(XsY) <log [rmin{ K (X), K (Y) }] (ii) I (XQX) -- log K(X) (iii) If X~Y yv _ Y, then IC(X@Y) -- log K(Y)

111 We conclude the section with a discussion of the chromatic information content of sorme particular kinds of trees. First, note that all trees are 2-chromatic and, thus, as indicated earlier, all connected trees are uniquely 2-colorable. Moreover, I (T)< log 2 = 1 for any tree T. 4.3.5 Theorem. Let Ln-1 be a path of length n-1 for n>. 2. 1 Then r log 2n - Tn [ (n+l) log (n+l) + (n-l) log(n-l), if n is odd I (L ) c n-l) 1 if n is even Proof. Let V(Ll) = {XlX2,...,} and E(Ll) = {[xlx2],...,[Xnlx] }. h —l.2.x. n Since Ln1l is uniquely 2-colorable, we need only produce a single 2-coloring to determine the desired chromatic decomposition. Let f be a 1 if x.f 2 coloring defined by xlf = 1, x2f = 2 and xi+lf =(2 if x.f = 1 A simple induction shows that f is always a 2-coloring, and it is n+i obvious that I {xE V(Ln ) I xf i }lequals -pn for i = 1 and ~n+iZ ~ both~n1 n+l- 1 for i = 2 when n is odd, and 2 for both i = 1 and i = 2 when n+l 2n n-1 n is even. So, when n is odd, I (Ln_) = log log 2n, c n-i 2nlog n 2n and when n is even I (Ln = 2 ( log ) = log 2 = 1, as required. A star S is an n-point connected tree with a distinguished point (of degree n - 1); all other points are of degree 1. Clearly, 1 n-i n I Sn = log n + llg nL0 since we can assign color 1 to the distinguished point and 2 to each of the other points. We consider a generalization of the star, for which we need to define the notion of distance. If x and y are connected points of a graph X, the distance p(x,y) between x and y is the number of edges in a path with initial point x and endpoint y. 4.3.6 Theorem Let St ( C X) be a star with distinguished point M, and _ _ _ _ _ _ teS.

112 let X be homeomorphic to St. Let ni = I{xeV(X) p(xO, x) = i } I for i = 0,1,2,...,k where k = max,x). If r = ni i even s -= /ni, then i odd I(X) = r_ log n- + log where n= IV(X) I c n r n S Proof. By induction on k. The cases k = 0 and k = 1 follow trivially from the preceding remarks. So, suppose the theorem holds for k=m (> 1) and the mapping f with xf e {1,2 } is the (unique) 2-coloring of X. Then if k = m+l, it is clear that the mapping f' given by xf' = xf for x C{y EV(X) p(y,x) m } and xf = { 1 if yf' = 2 and p(y,x) = m for (xx) 2 if yf' z 1 and p(y,x) m for (x,x) z m+l is the desired 2-coloring for the case k = m+l. The conclusion of the theorem follows irmmdiately. Figure 4.4 illustrates the theorem. x 6 16 10 16 Ic(X) = - + log Figure 4.4 Chromatic information content of a greph homeomorphic to a star

113 4.4 C ariso n of the two measures of graphical information As indicated in the introduction to the thesis, the principal reason for considering the measure Ic in addition to Ig is to point out the dependence of such measures on certain peculiar structural features of a graph. In one sense, we are only belaboring the obvious, since it is clear from the way an entropy measure on a graph is defined that it cannot characterize the graph' s structure completely. However, the juxtaposition of these two different measures serves a useful purpose in the sense that it prevents one from making outrageous claims about how adequately the information content of a graph reflects the complexity of a graph; and, on the positive side, it suggests the possibility of studying classes of entropy measures defined on graphs. It is fairly obvious from the preceding section that there is relatively little agreement between Ig and Ic. This, of course, follows from the fact that the symmetries (automorphisms) of a graph X are at best tenuously related to the various colorings of X. For example, the autcrphism group of a cycle of length n is transitive for any n; whereas, the chromatic number of such a graph is two or three depending on whether n is even or odd. A mnre serious source of divergence is provided by the class of trees. The chromatic number of a tree is two, so Ic(T) < 1 for any tree T. However, as mentioned earlier, for every n > 7, there exists a tree T with n points whose automorphism group consists of the identity alone, so that I g(T) = log n. Figure 4.5 presents graphs X and Y for which I g(X) < IC(X) and Ig(Y) > IC(Y).

114 I (X) =0 I (Y) = log 3 g g Ic(X) = 1 Ic(Y) = 1 Figure 4.5 Graphs on which Ig and Ic differ As one would expect, it is rather difficult to determine classes of graphs on which Ig and Ic agree. Two simple examples are furnished by null graphs and stars. Figure 4.6 exhibits two graphs on which the two measures agree. 3 4 Ig(X) = Ic(X) = I(Y) = Ic(Y) = log 5 - g c 9 g c Figure 4.6 Graphs on which Ig and Ic agree From our brief survey of the properties of Ic, it would appear that this measure is much less well-behaved with respect to graph operations than I. However, it is quite possible that the operations considered are not appropriate for the measure Ic. That is to say, the operations we chose to consider in connection with Ig are of the following kind. To each graph operation o (such as the cartesian product), there corresponds a group operation V (such as the cartesian product for groups) such that G(X o Y) < G(X) V G(Y) for any graphs X and Y. When the orbits of G(X) V G(Y) are cartesian products of orbits of G(X) and G(Y), this condition insures that every orbit of G(X o Y) is a union of orbits of

115 G(X) V G(Y). This, in turn, insures that Ig(X o Y) < Ig(X) + Ig(Y). In order to have a comparable result for the cromatic informnnation content, we would have to find an operation o on graphs which satisfies the following: if {W)t is a chromatic decomposition of X o Y with t -= (XoY), m l then each Wm is a union of sets of the form Ui x Vj whe {r Uk}h and i=l {V.}k are chromatic decompositions of X and Y, respectively, with h =K(X) and k = K(Y). The binary operations (cartesian product, composition and Kronecker product) studied earlier might be found to satisfy this condition for certain classes of graphs. In any case, specifying such operations and finding conditions which insure that I (X o Y) = IC(X)+ Ic(Y) are certainly interesting problems for further study. 4.5 Summary What we have attempted to accomplish in this thesis is the development and exploration of some tools for measuring the structural complexity of a particular mathematical object. The basic idea in our approach to this problem consists in constructing a finite probability scheme from a decomposition of the set of points of the object in question. As we have seen in the case of the measure I defined relative to the autog morphism group of a graph, the entropy of such a finite probability scheme provides a compact analytic device for a partial characterization of the relative complexity of an object. The major portion of the work was devoted to a systematic study of the measure Ig in order to demonstrate the usefulness of the concept of structural information in classifying graphs according to their relative complexity. In Chapter I we discussed the elementary properties of the

116 measure I and characterized the information content of a class of g product graphs. In Chapter II we enlarged the class of graphs under consideration to include directed graphs. In so doing, we generalized some results concerning the automorphism group of an undirected graph to the group of a digraph, and then showed that most of the properties of I observed for undirected graphs, carry over to digraphs. In addition, we gave a construction for producing digraphs having information content equal to the entropy of an arbitrary partition of a given positive integer. Finally, we extended I to a measure I on infinite g g undirected graphs by defining an infinite graph in terms of a sequence of finite graphs. In Chapter III we developed a technique for studying the automorphism group (and, thus, the information content) of a digraph, based on the algebraic properties of its adjacency matrix. We gave an algorithmfor constructing digraphs with zero information content, and studied the properties of such digraphs. Moreover, we presented an algorithm for constructing the automorphism group of a digraph and used it to determine sufficient conditions for two digraphs to have the same information content; and we investigated the information content of digraphs whose adjacency matrices have prescribed properties. In this concluding chapter, we have discussed an entropy measure Ic defined relative to a class of chromatic decompositions of a graph, c and compared it with the previous measure. Perhaps the most significant fact to emerge in this study is the (mathematical) feasibility of using the entropy function to characterize the structure of an object. More general objects than graphs can be

117 studied from this point of view. For example, suppose an object X is defined as a system X < U; E1, E2,...Ek > where U is a non-empty finite set and each Ei is a binary relation on U. If X = <U; El,...Ek> and Y = < V; F1, F2,...,Fk > are two such obejcts, we can define a homomrphism of X into Y as a mapping 0 of U into V such that for every x,y E U, (x,y) E Ei implies that (x,y)o = (xO,yO) e Fi for each i z 1,2,...k. A shmorrrphism $ which is a one-one mapping of U onto V can then be called an isomorphism of X onto Y; and if U = V, it is reasonable to call $ an automorphism of X. As in the case of graphs, it is easily verified that the set of all autonorphisms of an object X forms a group under the usual composition of mappings. If 0 is a hcmromorphism of X onto Y, it is clear that the sets given by {x E UI xO zy} for some y e V form a decomposition of the set U. Moreover, the orbits of the group of the object X form a decomposition of U. Thus, just as we did for graphs, we can define an information measure on such an object by taking the entropy of a finite probability scheme constructed from the decomposition given by its group; or we can define a measure relative to a class of decompositions corresponding to a class of hcmnoorphisms. In any case, it is feasible to develop the notion of structurel information content for a variety of mathematical objects.

BIBLIOGRAPHY 1. R. Bellman, Introduction to Matrix Analysis, New York, 1960. 2. C. Berge, Theory of Graphs and its Applications, London, 1962. 3. C.-Y. Chao, On a Theorem of Sabidussi, Proc. Amer. Math. Soc. 15 (1964), pp. 291-292. 4. C.-Y. Chao, On Groups and Graphs, Trans.. Amer. Math. Soc. 118, (1965), pp. 488-497. 5. L. Collatz and U. Sinogowitz, Spektren endlicher Graphen, Abh. Math. Seam. Univ. Hamburg 21 (1957), pp. 63-77. 6. R. M. Fano, Transmission of Information, Cambridge, Mass., 1961. 7, H. J. Finck, Vollst'ndiges Produkt, chromatische Zahl und charakteristisches Polynom regulMrer Graphen II, Wiss. Z. TeS Hochsch Ilmenau 11 (1965), pp. 81-87. 8. H. J. Finck and G. Grohmann, Vollst'andiges Produkt, chrmatische Zahl und charakteristisches Polynom regulrer Graphen I, Wiss. Z. Techn. Hochsch. Ilmenau 11 (1965), pp. 1-3. 9. R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938), pp. 239-250. 10. R. Frucht, On the Groups of Repeated Graphs, Bull. Amer. Math. Soc. 55 (1949), pp. 418-420. 11. R. Frucht, Graphs of Degree 3 with Given Abstract Group, Canad. J. Math. 1 (1949), pp. 365-378. 12. F. R. Gantmacher, The Theory of Matrices, Vol. I (English Translation), New York, 1959. 13. E. N. Gilbert, Enumeration of Labelled Graphs, Canad. J. Math. 8 (1956), pp. 405-411. 14. M. Hall, The Theory of Groups, New York, 1959. 15. F. Harary, On the Group of the Composition of Two Graphs, Duke Math. J. 26 (1959), pp. 29-34. 16. F. Harary, R. Z. Norman and D. Cartwright, Structural Models, New York, 1965 118

119 17. S. Hedetniemi, Homororphisms of Graphs and Automata, Technical Report 03105-44-T, ORA, The University of Michigan, 1966. 18. R. L. Hemminger, On the Group of a Directed Graph, Canad. J. Math. 18 (1966), pp. 211-220. 19. A. J. Hoffman, On the Polynomial of a Graph, Amer. Math. Monthly 70 (1963), pp. 30-36. 20. I. N. Kagncq Linear Graphs of Degree < 6 and their Groups, Amer. J. Math. 68 (1946), pp. 505-520. CorTections: Amer. J. Math. 69 (1947), p. 872. Amer. J. Math. 77 (1955), p. 392. 21. G. Karreman, Topological Information Content and Chemical Reactions, Bull. Math. Biophys. 17 (1955), pp. 279-285. 22. A. I. Khinchin, Mathematical Foundations of Inforpation Theory, New York, 1957. 23. D. Konig, Theorie der Endlichen und Unendlichen Graphen, New York, 1950. 24. C. C. Mac Duffee, Theory of Matrices, New York, 1946. 25. M. Marcus and H. Mine, A Survey of Matrix Theory and Matrix Inequalities, Boston, 1964. 26. M. H. McAndrew, On the Product of Directed Graphs, Proc. Amer. Math. Soc. 14 (1963), pp. 600-606. 27. 0. Ore, Theory of Graphs, Amer. Math. Soc. Publ., Vol. 38, Providence, 1962. 28. G. Prins, The Automorphism Group of a Tree, Docto-ral Dissertation, University of Michigan, 1957. 29. N. Rashevsky, Life, Information Theory, and Topology, Bull. Math. Biophys. 17 (1955), pp. 229-235. 30. W. E. Roth, On Direct Product Matrices, Bull. Amer. Math. Soc. 40 (1934), pp. 461-468. 31. H. J. Ryser, Combinatorial Mathematics, New York, 1963. 32. G. Sabidussi, Graphs with Given Group and Given Graph-Theoretical Properties, Canado J. Math. 9 (1957), pp. 515-525. 33. G. Sabidussi, The Composition of Graphs, Duke Math. J. 26 (1959), pp. 693-696. 34. G. Sabidussi, Graph Multiplication, Math. Z. 72 (1960), pp. 446-457.

120 901 5 03483 158 35. G. Sabidussi, Graphs with Given Infinite Group, Monatsch. Math. 64 (1960), pp. 64-67. 36. H. Sachs, Uber Teiler, Faktoren und charakteristische Polynome von Graphen I, Wiss. Z. Techn. Hochsch. Ilmenau 12 (1966), pp.7-12. 37. H. S. Shapiro, The Embedding of Graphs in Cubes and the Design of Sequential Relay Circuits, Unpublished Bell Telephone Laboratory Memorandum, July, 1953. 38. W. R. Scott, Group Theory, Englewood Cliffs, New Jersey, 1964. 39. E. Trucco, A Note on the Information Content of Graphs, Bull. Math. Biophys. 18 (1956), pp. 129-135. 40. E. Trucco, On the Information Content of Graphs: Compound Symbols; Different States for each Point, Bull. Math. Biophys. 18 (1956), pp. 237-253. 41. P. Weichsel, The Kronecker Product of Graphs, Proc. Amero Math. Soc. 13 (1962), pp. 47-52. 42. H. Wielandt, Finite Perntation /ouPs, New York, 1964. 43. A. A. Zykov, On Some Properties of Linear Complexes, Amer. Math. Soc. Transl. 1952, No. 79.