USE OF THE SPECTRUM IN GRAPH ISOMORPHISM by Rachel Gelbart B.A., Tel Aviv University, 1972 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in the Department of Computer Science We accept t h i s thesis as comforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA February 1976 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced deg ree at the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r ee t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r ag ree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y pu rpo se s may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Depa rtment The U n i v e r s i t y o f B r i t i s h Co l umb i a 2075 Wesbrook Place Vancouver, Canada V6T 1W5 i i ABSTRACT The following i s a study of the use of the eigenvalues and eigenvectors of the adjacency matrices of graphs to determine graph isomorphism. Two randomly chosen graphs w i l l i n general have d i f f e r e n t eigenvalues, and comparing the eigenvalues provides a f i r s t f i l t e r when checking for isomorphism. If the graphs are cospectral, we propose an algorithm that compares t h e i r eigenvectors i n order to fi n d an isomorphism between them, i f any exists. The algorithm involves backtracking, and i t i s therefore d i f f i c u l t to evaluate i t s performance. It was fast for a l l pairs of graphs we compared, except one. For graphs whose eigenvalues are a l l simple we present an e f f i c i e n t algorithm to generate the group of a graph. I i i TABLE OF CONTENTS CHAPTER 1 INTRODUCTION , 1 1.1 Defin i t i o n s and Notation 2 CHAPTER II GRAPH ISOMORPHISM 5 2.1 Introduction 6 2.2 Heuristic methods 6 2.3 Cornell's algorithm 10 2.4 Algorithms for special graphs 11 CHAPTER I I I THE SPECTRUM OF GRAPHS 21 3.1 Introduction 21 3.2 Research on the spectrum of a graph ..................... 21 3.3 Algebraic properties 27 3.4 Computation of eigenvalues and eigenvectors 30 £HAE£ER IV THE EIGENVECTOR CONNECTION 32 4.1 I n t u i t i v e description of the algorithm 32 4.2 Connection with the group of the graph 43 4.3 Formal description of the Algorithm 50 4.4 Order of the computation ................................ 58 4.5 Conclusion 64 BIBLIOGRAPHY 65 APPENDIX A Examples of cospectral graphs .................... 69 APPENDIX B A nasty pair of cospectral graphs 77 i v LIST OF FIGURES FIGURE PAGE 2.5.1 Smallest cospectral graphs 17 2.5.2 Smallest cospectral connected graphs 17 4.1.1 Two cospectral isomorphic graphs 33 4.1.2 Smallest cospectral non-isomorphic trees 36 4.1.3 An 8-point graph with simple eigenvalues 37 4.1.4 Two cospectral isomorphic graphs 41 4.2.1 A 4-point graph 46 4.5.1 A 5-point graph with simple eigenvalues 59 V ACKVOVLEDGHENT I would l i k e to thank Dr._ Abbe Mowshowitz f o r sugges t i n g t h i s t o p i c and f o r h i s c a r e f u l e d i t i n g of the t h e s i s . I would a l s o l i k e to thank my f r i e n d s , p a r t i c u l a r l y G. I. McCalla, f o r t h e i r h e l p , and my husband f o r h i s encouragement throughout my years i n sc h o o l . F i n a n c i a l T r a n s p o r t a t i o n Science. a s s i s t a n c e Development was g r a t e f u l l y r e c e i v e d from the Agency and the Department of Computer I: INTRODUCTION 1 This thesis discusses a method for the detection of isomorphism between graphs that uses the eigenvalues and eigenvectors of the adjacency matrices of the graphs. The method i s general purpose - i t can be used f o r a l l types of undirected graphs. The basic idea i s to map eigenvectors of the f i r s t graph onto eigenvectors of the second graph i n order to f i n d an Isomorphism, i f any e x i s t s . For graphs whose adjacency matrices have a l l d i s t i n c t eigenvalues we present a method fo r finding the group of the graph, although i t i s hard to evaluate the performance of t h i s algorithm, because tentative solutions may be generated at an early stage and l a t e r rejected, the examples we have looked at suggest that the number of computation steps needed to f i n d the group of the graph i n t h i s case i s bounded above by a polynomial i n the order of the group. For graphs whose eigenvalues are not simple, we present an algorithm to f i n d one isomorphism ( i f any exists) between the two graphs. Here again i t i s d i f f i c u l t to give a general estimate of the number of computation steps required by the algorithm, since a large amount of backtracking may be necessary. This however was the case for only one of the pairs of graphs we tested (see appendix B). Most of the relevant d e f i n i t i o n s are presented i n the next section, the rest are introduced as necessary in the following Chapters. In Chapter I I , di f f e r e n t algorithms for graph isomorphism are reviewed. Chapter I I I presents research on the spectrum of graphs which i s relevant to our algorithm. In Chapter IV the algorithm i s described, and i t s r e l a t i o n with the I : INTRODUCTION 2 group of t h e graph i s d i s c u s s e d . S e v e r a l examples i l l u s t r a t i n g the a l g o r i t h m s a r e g i v e n i n Appendix A and Appendix B* 1.1 D e f i n i t i o n s and N o t a t i o n The d e f i n i t i o n s and n o t a t i o n used here are l a r g e l y those of Harary [ 15 ]. A graph G=G(V,E) c o n s i s t s of a f i n i t e non-empty s e t V=V (G) t o g e t h e r w i t h a s e t E=E (G) o f unordered p a i r s o f d i s t i n c t elements of V, The elements o f V are c a l l e d nodes (or p o i n t s o r v e r t i c e s ) of G, t h e elements o f E a r e c a l l e d l i n e s (or edg,es) o f G. I f x,y>, where 1=1,...,n; the corresponding eigenvector i s x^ =sin i ^ 1=1,...,n. Let G be a cycle. Then V = 2 cos <£• , where 6; =2^,for i=1,...,n; the corresponding eigenvectors are x'*=cos ( k ^ ) , xk^=sin ( k C ) . The eigenvalues of a path are simple, the eigenvalues of a cycle are double, except for i=n and i=n/2 i f n i s even. Co l l a t z and Sinogowitz also show that q q 4 q where \„ i s the index of the graph ( i . e . , i t s maximal eigenvalue), g ,q , q respectively the minimum, average and maximal degree of a vertex. Equality holds i f the graph i s regular. Mowshowitz [231 generalizes these observations, giving a general formula for the c o e f f i c i e n t s of the c h a r a c t e r i s t i c polynomial of a graph In terms of i t s subgraphs. For an arb i t r a r y digraph H of order k, l e t f ([ ]) denote the number of c o l l e c t i o n s of d i s j o i n t directed cycles i n H of lengths i v , i ^ ,... , i A , where 1^1 (1£j,y2, and define f {{ i , , i i # . . . . , i r}) as above but f o r undirected cycles (and l i n e s ) , we obtain: Let G be a graph of order n. Then for 1^ k" t where s (n, f n^ _,. .. ,nt) denotes the sum of the products r at a time of the numbers n , n ,...,n, and S =1. As a c o r o l l a r y we obtain the c h a r a c t e r i s t i c polynomial of the complete b i p a r t i t e graph K^ „ and of the star K ^ = Xh"( Xz-n) . Turner [29] has considered graphs with a prime number of points which are point symmetric. A starred polygon i s a graph G=(V,E) whose verti c e s may be labeled i n such a way that (v. ,v ) e F i f f (v ,v. . ) t E , for k=1,... , J V j - 1, where the subscripts are taken modulo jV|. Turner shows that a connected graph with a prime number of points p i s point symmetric i f f i t i s a starred polygon, and he further shows that these graphs are characterized by t h e i r spectrum, that i s , two point symmetric graphs with a prime number of points are isomorphic i f f they have the same eigenvalues. I f the vertices of a starred polygon are labeled v to v i n the clockwise d i r e c t i o n , the adjacency matrix of the graph i s a c i r c u l a n t ,that i s , a matrix in which each row afte r the f i r s t one i s obtained from the preceding one by s h i f t i n g i t c y c l i c a l l y one position to the ri g h t . I l l : THE SPECTRUM OF GRAPHS 25 Elpas and Turner [11] generalize t h i s r e s u l t , showing that i f two c i r c u l a n t matrices ft and B of prime order p, p>2, with r a t i o n a l entries have the same eigenvalues, then there exists a permutation matrix P s.t. B=P1AP. It follows immediately that two directed graphs having a prime number of vertices and c i r c u l a n t adjacency matrices are isomorphic i f f they have the same eigenvalues. The next results are quoted from Cvetkovic [9], who presents a comprehensive survey of the spectra of graphs and their use i n d i f f e r e n t combinatorial problems. I f a graph i s regular of degree r, to each eigenvalue \ ( \;>r) with m u l t i p l i c i t y p^ there corresponds i n the spectrum of G the eigenvalue whose m u l t i p l i c i t y i s also p^. It i s clear that two graphs G and H are isomorphic i f f t h e i r complements are isomorphic. Thus one might be tempted, i f the eigenvalues of G have high m u l t i p l i c i t y , to look at the spectrum of G instead. The following theorem shows that t h i s w i l l not make any s i g n i f i c a n t difference 3.2.1,. If the spectrum of G contains eigenvalue with m u l t i p l i c i t y p>1 then the spectrum of the complement G contains the eigenvalue -\-1 with m u l t i p l i c i t y p s.t. p-1£p^p+1. The spectrum characterizes a l l those graphs determined by the number of vertices and the number of edges, since these numbers are determined by the spectra. Thus graphs without edges, graphs with one edge and t h e i r complements are I l l : THE SPECTRUM OF GRAPHS 26 c h a r a c t e r i z e d by t h e i r s p e c t r a . R e g u l a r graphs of degree 1 and n-2 are determined by t h e i r s p e c t r a , s i n c e t h e r e e x i s t s o n l y one r e g u l a r graph of degree 1 on n p o i n t s , and t h e s p e c t r a o f r e g u l a r graphs and t h e i r complement a r e m u t u a l l y d e t e r m i n e d . F i n c k [ 1 3 ] has shown t h a t r e g u l a r graphs o f degree 2 (and t h e r e f o r e a l s o n-3) are c h a r a c t e r i z e d by t h e i r s p e c t r a . The l i n e grajah o f a graph G, L (G) , i s a graph whose p o i n t s a r e t h e l i n e s of G, w i t h two p o i n t s i n L(G) a d j a c e n t whenever the c o r r e s p o n d i n g l i n e s of G a r e . L i n e graphs o f some s p e c i a l g r a p h s , as w e l l as graphs which are d i r e c t sums of complete graphs a r e c h a r a c t e r i z e d by t h e i r s p e c t r a . Sachs [ 2 5 ] showed t h a t t h e c h a r a c t e r i s t i c p o l y n o m i a l o f t h e l i n e graph L (G) of a where m i s t h e number of v e r t i c e s of G. THEOREM 3.2.2. A graph c o n t a i n i n g a t l e a s t one edge i s b i p a r t i t e i f i t s spectrum, t a k e n as a s e t of p o i n t s on t h e number a x i s , i s symmetric w i t h r e s p e c t t o t h e z e r o p o i n t . THEOREM 3.2,3, A connected graph, c o n t a i n i n g a t l e a s t one edge, w i t h i n d e x 2, i s b i p a r t i t e i f f -2 i s i n i t s spectrum. I t i s e a s i l y seen by d i r e c t s u b s t i t u t i o n t h a t t h e e i g e n v e c t o r s of a b i p a r t i t e graph c o r r e s p o n d i n g t o - \; can be o b t a i n e d from the e i g e n v e c t o r c o r r e s p o n d i n g t o \- by m u l t i p l y i n g t h e components c o r r e s p o n d i n g t o one s e t o f edges by - 1 . r e g u l a r graph G o f degree r s a t i s f i e s I l l : THE SPECTRUM OF GRAPHS 27 THEOREM 3.2.4. I f G i s a connected graph with diameter D, and G has m d i s t i n c t eigenvalues, then m^ .D+1. THEOREM 3.2.5. Let {\=r,...,\} be the spectrum of G, where r i s the index of G. G i s regular i f f 1/nX\=r (*) If (*) holds and r has m u l t i p l i c i t y p, the graph has p components. THEOREM 3.2.6. If the index of G has m u l t i p l i c i t y p and a positive eigenvector corresponding to i t , G has p components. Some of the above results are proved from s t r u c t u r a l properties of the graphs, others follow from properties of the adjacency matrix. 3.3 Algebraic properties The adjacency matrix of an undirected graph i s a symmetric matrix of O's and 1*s, with a zero diagonal. Such matrices have several important properties. We l i s t here several r e s u l t s that are relevant to our algorithm. For proofs, see for example [2]{ theorems 1-4) and [14]( theorems 5-8). THEOREM 3.3.1. The eigenvalues and eigenvectors of a r e a l symmetric matrix are a l l r e a l . I l l : THE SPECTRUM OF GRAPHS 28 THEOREM 3.3.2. The eigenvectors associated with d i s t i n c t eigenvalues of a re a l symmetric matrix are mutually orthogonal. 3.3.3. If \ i s an eigenvalue of m u l t i p l i c i t y k of a real symmetric matrix, then associated with \ i s an eigenvector space of dimension k. THEOREM 3.3.4. The sum of the eigenvalues of a matrix A i s egual to the trace of A, that i s , 5LNv=,^ac- , In p a r t i c u l a r , i f A i s the matrix of a graph without loops, 2_V=0. A matrix A i s c a l l e d son-negative i f a l l i t s elements are non-negative. A square matrix A i s c a l l e d reducible i f there Is a - °"l permutation that puts i t i n the form A=\J:>1, where B , D are square matrices. Otherwise A i s ca l l e d i r r e d u c i b l e . I t i s easy to see that the adjacency matrix of a graph G i s ir r e d u c i b l e i f f G i s connected. Since these are the graphs we are mainly interested In the following theorem i s of great importance. 2*3.5. (Frobenius)An i r r e d u c i b l e non-negative matrix A always has a positive eigenvalue r that i s a simple root of the ch a r a c t e r i s t i c equation. The moduli of a l l the other eigenvalues does not exceed r. To the maximal eigenvalue r I l l : THE SPECTRUM OF CRAPBS 29 t h e r e c o r r e s p o n d s an e i g e n v e c t o r w i t h p o s i t i v e c o o r d i n a t e s ( o f t e n r e f e r r e d t o as t h e P e r r o n v e c t o r ) . Moreover, i f A has h e i g e n v a l u e s of modulus r , then t h e s e a r e a l l d i s t i n c t , and a r e r o o t s o f t h e e g u a t i o n * - r =0. •v, THEOREM 3.3.6. L e t s-= Z a. 1=1,2,...,n , s=min s., S-max - - - - - v, „ («_Ctv, s^. For an i r r e d u c i b l e n o n - n e g a t i v e m a t r i x A, s ^ r ^ S , and e q u a l i t y h o l d s o n l y i f s=S, i . e . , o n l y when a l l the row sums a r e e g u a l . I n p a r t i c u l a r , i f A i s the a d j a c e n c y m a t r i x o f a graph G, r<:n-1, and f o r a l l i , - ( n - I J ^ V ^ u - l . I f G i s r e g u l a r of degree k, r=k, and f o r a l l i , -k^\<:.k. THEOREM 3.3.7. An i r r e d u c i b l e n o n - n e g a t i v e m a t r i x A cannot have two l i n e a r l y independent n o n - n e g a t i v e e i g e n v e c t o r s . A m a t r i x i s s t o c h a s t i c i f a l l i t s row sums are e q u a l t o 1. THEOREM 3,3.8. A no n - n e g a t i v e m a t r i x A i s s t o c h a s t i c i f f i t s maximal e i g e n v a l u e i s 1, and i t has t h e e i g e n v e c t o r (1,1,..., 1) c o r r e s p o n d i n g t o the e i g e n v a l u e 1. COROLLARY 3.8A I f A i s t h e ad j a c e n c y m a t r i x o f a r e g u l a r graph of degree k, i t s maximal e i g e n v a l u e i s k and an e i g e n v e c t o r c o r r e s p o n d i n g t o i t i s (1, 1,.. ., 1). I l l : THE SPECTRUM OF GRAPHS 30 Symmetric matrices then have nice properties: the eigenvalues and eigenvectors are a l l r e a l , the eigenvector space i s n-dimensional, eigenvectors associated with d i s t i n c t eigenvalues are orthogonal, etc. This ensures the existence of stable and e f f i c i e n t numerical algorithms f o r computing their eigenvalues and eigenvectors. Since we are concerned with matrices which are adjacency matrices of graphs, we could f i n d the c h a r a c t e r i s t i c polynomial using one of the formulae of the preceding section, but as these i n general involve looking at a l l the subgraphs of a graph , they are not e f f i c i e n t . 3.4 Computation of eigenvalues and eigenvectors Eigenvalues and eigenvectors of square matrices are usually computed using i t e r a t i v e methods, rather than by solving the ch a r a c t e r i s t i c eguation. Several such methods exist (see for example Wilkinson, [35]), and l i b r a r i e s usually provide standard routines for finding eigenvalues and eigenvectors of symmetric matrices. The routine we used f i r s t transforms the given matrix to a s i m i l a r t r i d i a g o n a l matrix, using Householder's algorithm, and then finds the eigenvalues and eigenvectors (of the o r i g i n a l matrix) using the QR algorithm. A f u l l description of the algorithm, as well as ALGOL programs implementing i t , can be found i n Martin, et a l [ 2 1 ] and Bowdler, et a l [ 1 ] . A l l the computations were done in double precision (on an IBM 370/168), and the results were always sa t i s f a c t o r y . It i s possible that one might run into problems with matrices having pathologically I l l : THE SPECTRUM OF GRAPHS 31 close eigenvalues, but t h i s was never the case with the examples we t r i e d . I f G i s not connected, i t s adjacency matrix i s reducible, and can be put i n the form A= e> o I t i s c l e a r that the eigenvalues of A consist of the eigenvalues of B and those of C. If x= fx"} x1* . .. , x) i s an eigenvector of B corresponding to ^ ; , then u= (x',\x1?.. . ,x^0,... ,0) i s an eigenvector of A corresponding to 'V . Similarly, i f y= (y, y,... , y) i s an eigenvector of C corresponding to ^,then v= (0, ..., 0, y,.... ,y) i s an eigenvector of A corresponding to X ;. . The computation time for finding the eigenvalues and eigenvectors of a symmetric matrix i s of order n , where n i s the dimension of the matrix. Thus i t i s c l e a r l y i n e f f i c i e n t to compute the eigenvalues of a reducible matrix d i r e c t l y from the matrix. The computation time and the error w i l l be much smaller i f the spectrum Is computed separately for the non-zero blocks B and C. That i s , when computing the eigenvalues of a non-connected graph, i t i s best to compute separately the eigenvalues of each connected component. This of course i s the case with most algorithms f o r graph isomorphism: i f the computation time Is a non-linear function of the number of vertices, i t i s worthwile, i f possible, to decompose the problem into one of matching a number of smaller graphs for isomorphism. Thus, although our algorithm can be used for connected or disconnected graphs, i t i s best when comparing disconnected graphs to test t h e i r connected components for Isomorphism. IV: THE EIGENVECTOR CONNECTION 32 4.1 I n t u i t i v e Description of the Algorithm We have seen i n Section 2.5 that i f each eigenvector of a graph G i s a permutation of some eigenvector of a cospectral graph H corresponding to the same eigenvalue, then G i s isomorphic to H. We want to look at the eigenvectors of G and H and use them to f i n d such a permutation. For example, consider the graphs in Fig 4.1.1. The eigenvalues and eigenvectors of the graphs were computed using a standard l i b r a r y routine. The graphs are cospectral, and we want to find out whether they are isomorphic or not. F i r s t note that a l l the eigenvalues i n t h i s case are simple. The routine used to compute the spectrum yields orthonormalized vectors, and we therefore know that i f the graphs are isomorphic there e x i s t s a permutation matrix P s.t. x ; = Py-t or x- = -Py; , i = 1,. .. , n ( i f the vectors were not normalized, we would have to f i n d constants c,; , not necessarily +1 or -1, s.t. x-= c-Py.. This can e a s i l y be done, for example by comparing the largest components of x and y ). We need the following d e f i n i t i o n s at t h i s point: Let S=(X /•••#s tJ, T= {t( , . . . , t j be p a r t i t i o n s of {1,...,n} . & fiartial £§rmutation P* i s a 1-1 mapping from S to T s.t. elements are mapped to elements of egual c a r d i n a l i t y . 17: THE EIGENVECTOR CONNECTION EIGENVALUES -1.8513 -1.3504 -0.5600 0.0000 1.0561 2.7056 EIGENVECTORS 0.2619 -0.2355 -0.6754 0.0 -0.6414 -0.0920 0.0662 0.7137 -0.3959 0.0 0.2555 -0.5140 -0.3792 -0.3849 -0.1210 0.7071 0.1719 -0.4048 0.6358 -0.1939 0.4636 0.0 -0.0740 -0.5812 -0.3792 -0.3849 -0.1210 -0.7071 0.1719 -0.4048 -0.4849 0.3180 0.3782 0.0 -0.6774 -0.2488 EIGENVALUES -1.8513 -1.3504 -0.5600 0.0000 1.0561 2.7056 EIGENVECTOBS 0.4849 -0.3180 -0.2619 0.2355 -0.0662 -0.7137 0.3792 0.3849 -0.6358 0.1939 0.3792 0.3849 0.3782 0.0000 -0.6774 -0.2488 •0.6754 -0.0000 -0.6414 -0.0920 •0.3959 -0.0000 0.2555 -0.5140 -0.1210 0.7071 0.1719-0.4048 0.4636 0.0000 -0.0740 -0.5812 -0.1210 -0.7071 0.1719 -0.4048 Figure 4.1.1 Two Cospectral Isomorphic Graphs IV: THE EIGENVECTOR CONNECTION 34 We w i l l informally r e f e r to a mapping from a p a r t i t i o n of the nodes of a graph G (labeled 1,...,n) to a p a r t i t i o n of the nodes of a graph H (si m i l a r l y labeled) as a p a r t i a l permutation from G to H. We w i l l refer to a p a r t i a l permutation whose domain consists of only singletons as a permutation. Let S, S',T,T* be p a r t i t i o n s of {"!,... n), P*: S->T, Q*; S'->T' be p a r t i a l permutations. I f f o r each s' in S 1 there i s an s i n S such that s' s and Q*(s')c P* (s) , Q* Is said to refine P*, and P* i s said to contain Q*. A p a r t i a l permutation P* i s maximal with respect to some property i f i t i s not contained in any p a r t i a l permutation Q* with the same property. A p a r t i a l permutation P* from the nodes of a graph G to the nodes of a graph H Is said to be proper i f every permutation P r e f i n i n g i t i s an isomorphism from G to H. By Theorem 2.1, a p a r t i a l permutation P* s.t. every permutation P r e f i n i n g i t maps each eigenvector of G onto an eigenvector of H corresponding to the same eigenvalue i s a proper p a r t i a l permutation. We now return to the graphs of Fig 4.1.1. Comparing the components of x, and y^ , we see that for each 12, 2->3, (3,5) -> (4,6), 4->5, 6->1 Considering now the remaining eigenvectors, we see that none of them gives additional insight as to how to match the two nodes (3,5) of G to the two nodes (4,6) of H, while a l l of them s a t i s f y x; = Py- or x = -Py^,i = 2,,..,6 , P r e f i n i n g P* Therefore, by Theorem 2.1, any p a r t i t i o n r e f i n i n g P* s p e c i f i e s an isomorphism. The graphs in Fig 4.1.2 form another pair of cospectral graphs. These are the smallest cospectral non-isomorphic trees, already mentioned in Section 2.5. Comparing X( and y( , It i s immediately clear that no matching between t h e i r components i s possible, since the components of x have 4 d i s t i n c t values (and only 2 d i s t i n c t absolute values) , while the components of y, have 5 d i s t i n c t values (5 d i s t i n c t absolute values). Thus there can exist no P s.t. x = Py_ or x,= -Py, therefore no P s.t. PTAP = B, and the graphs are not isomorphic. Consider now the graph i n Fig 4.1.3, which we want to map onto i t s e l f . IV: THE EIGENVECTOR CONNECTION 36 EIGENVALUES -2.3028 -1.3028 1.3028 2.3028 -0.0000 -0.0000 -0.0000 -0.0000 EIGENVECTORS 0.2454 -0.3263 -0.3263 0.2454 -0.3263 -0.3263 0.2454 -0.3263 -0.3263 -0.5651 0.4250 -0.4250 0.5651 0.4250 0.4250 -0.2454 -0.3263 0.3263 -0.2454 -0.3263 0.3263 -0.2454 -0.3263 0.3263 0.2454 0.2454 0.2454 0.5651 0.5651 0.0 0.0 0.0 0.0 0.0 0.2454 -0.8157 0.24 54 0.4396 0. 2454 0.3760 0.7887 -0.2113 -0.2113 0.7887 -0.5774 -0.5774 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0. 0 0.0 367 0.6880 -0.7247 < I ,4 , < > 7 EIGENVALUES -2.3028 -1.3028 1.3028 2.3028 -0.0000 -0.0000 -0.0000 -0.0000 EIGENVECTORS 0.2939 -0.1573 -0.1573 -0.2939 -0.1667 0.2939 -0.1573 -0.1573 -0.2939 -0.1667 -0.6768 0.2049 -0.2049 -0.6768 0.0000 0.2939 -0.1573 -0.1573 -0.2939 -0.1667 0.3829 0.3622 0.3622 -0.3829 0.6667 0.2939 -0.1573 -0.1573 -0.2939 -0.1667 -0.8333 -0.1667 -0.1667 -0.2049 -0.6768 0.6768 -0.2049 -0.0000 0.0 0.0 0.0 0.0890 0.5195 0.5195 -0.0890 -0.6667 0.0 0.0 0.0 0.1667 -0.1667 0.8333 0.1667 0.8333 -0.1667 0.0 0.0 0.0 0.5000 -0.5000 -0.5000 0.0 0.0 0.0 Figure 4. 1.2 Smallest Cospectral Non-Isomorphic Trees IV: THE EIGENVECTOR CONNECTION EIGENVALUES -2.4560 -1.6180 -0.9229 -0.0000 EIGENVECTORS -0.3829 0.0 0.7350 0.0 -0.0355-0.6015-0.4289 0.0 0.5058 0.3717 0.0897 0.0 -0.4119 0.0 -0.1945 -0.7071 0.5058 -0.3717 0.0897 0.0 -0.0355 0.6015 -0.4289 0.0 -0.4119 0.0 -0.1945 0.7071 0.6180 1.0650 3.3139 0.0 -0.3717 •0.6015 0.0 0.6015 0.3717 0.0 0.2820 0.4057 •0.2556 •0.4799 -0.2556 0.4057 •0.4799 0.4 833 0.3875 0.4133 0.2494 0.4133 0.3875 0.2494 Figure 4.1.3 A< 7-point Graph IV: THE EIGENVECTOR CONNECTION 38 Comparing x, and y , we see that there i s one maximal p a r t i a l permutation that maps the elements of x onto the elements of y P*: 1 -> 1, (2,6) -> (2,6), (3,5) -> (3,5), (4,7) -> (4,7) If we now try to match x* and y t ,we obtain 2 p a r t i a l permutations, H *: (1,4,7) -> (1,4,7), 2 -> 2, 6 -> 6, 3 -> 3, 5 -> 5 R *: (1,4,7) -> (1,4,7), 2 -> 6, 6 -> 2, 3 -> 5, 5 -> 3 Since x^=xf=^', we have R 4* s a t i s f i e s : V'R r e f i n i n g i t , x x= Ry^ . Rt* s a t i s f i e s : ^R r e f i n i n g i t , x^= -Ry^ . Se w i l l refer to a permutation of the f i r s t kind as positive with respect to x, and a permutation of the second kind as negative with respect to x. To obtain a p a r t i a l permutation which w i l l map x ^ n t o y, and x^onto yx , we refine P* using R v * and R yielding P v* and P x* P^*: 1 -> 1, 2 -> 2, 3 -> 3, (4,7) •-> (4,7), 5 -> 5, 6 -> 6 P,*: 1 -> 1, 2 -> 6, 3 -> 5, (4,7) -> (4,7), 5 -> 3, 6 -> 2 Comparing x^ and ys , we see that any refinement of Pr * and of P^* w i l l map xs onto y B. Comparing x' and y^, we obtain 2 p a r t i a l permutations, one positive and one negative, but these are of no use i n r e f i n i n g Pv * and P^*,since t h i s only means that the set (4,7) can be broken up i n two ways, which i s clear. Comparing x 5 and y s, we obtain 2 p a r t i a l permutations, one positive and one negative, which are egual to Pv * and P^* respectively, Comparing xt and y, , we obtain a p a r t i a l permutation which IV: THE EIGENVECTOR CONNECTION 39 contains Vt* and Pv*. Comparing x^and Y7 * H® obtain again a p a r t i a l permutation which contains P, * and Pt*, and thus cannot be used to refine them further. I t i s clear that the two p a r t i a l permutations which we obtained, P t* and P^*, are the only maximal proper p a r t i a l permutations mapping the graph onto i t s e l f , and therefore the set of permutations r e f i n i n g them comprises the automorphism group of the graph. In the above examples, the eigenvectors compared belonged to eigenvalues of m u l t i p l i c i t y one. The comparison in t h i s case i s very simple. The si t u a t i o n i s considerably more complicated when we look at eigenvectors belonging to eigenvalues of m u l t i p l i c i t y greater than one. In t h i s case, we no longer have only two possible mappings between corresponding eigenvectors of G and H, and i t i s therefore hopeless to try and f i n d a l l the isomorphisms from G to H by t h i s method. We try to f i n d one isomorphism by finding one mapping between corresponding eigenvectors, and backing up i f our choice was wrong. Let \ be an eigenvalue of G and H of m u l t i p l i c i t y 2. I f G and H are isomorphic, we know that x i s the permutation of some eigenvector of H belonging to V, . Thus we only know that there exists a ( , a z, and a permutation matrix P s.t, x (= a.Py, + a tPy. In order to find a^and a^, we solve a set of 2 li n e a r equations of the form IV: THE EIGENVECTOR CONNECTION 40 av yv + a iy 1= x, for l#m, l,m &{1,... ,n) (D a, r+ a x £ ^ x ^ for j#k, j,ke (1 #.., ,n}. u n t i l we fi n d a and a that s a t i s f y (1) and (2) x, = a ^ y , + a^Py^ The k vectors that span the vector space associated with an eigenvalue of m u l t i p l i c i t y k form a matrix [ v s ,... , v t ] of column-rank k, since they are l i n e a r l y independent, and therefore also of row-rank k. Thus a system such as (1) which i s l i n e a r l y independent can always be found by trying a l l possible values for I and m. If G and H are isomorphic, then by varying 1 and m over a l l combinations of {1,.,.,n} and varying j and k over a l l combinations of and over a l l permutations of these combinations, we w i l l f i n d a l l solutions s.t. both (1) and (2) hold, yielding candidates P for the isomorphism. For example, consider the graphs in Fig 4.1.4. Comparing the eigenvectors associated with ^-, we f i n d that x, = -Py. , where P*= (1,2,3) -> (1,2,5), (4,6,8) -> (3,4,6) (5,7) -> (7,8) for every permutation P r e f i n i n g P*. We next try to solve a li n e a r system of one eguation, where the elements of x tand y,. are chosen according to P*. Choosing x'J and and solving x'J^ay^ and then comparing x^ to ay^ , we obtain IV: THE EIGENVECTOR CONNECTION 41 EIGENVALUES -2.5616 -0.0000 1.5616 3.0000 -1.6180 -1.6180 0.6180 0.6180 EIGENVECTORS -0.0903 0.0 -0.0903 0.0 -0.0903 0.0 0.4121 0.0 -0.4827 -0.7071 0.4121 0.0 -0.4827 0.7071 0.4121 0.0 EIGENVALUES -2.5616 -0.0000 0.44 74 0.4474 0.44 74 -0. 1962 •0. 3769 -0. 1962 •0.3769 -0.1962 •0.3536 •0.3536 -0. 3536 •0.3536 •0.3536 •0.3536 •0.3 536 •0.3536 -0.6841 0.2382 0.4459 •0. 2756 0.0 -0. 1472 0.0 0.4228 0.1199 •0.6524 0.5325 •0.3291 0.0 0.4032 0.0 •0.0741 1.5616 3.0000 -0.0003 •0.3719 0.3716 0.6013 0.0 •0.6017 0.0 0.0004 0.4 293 •0. 2144 •0.2149 •0.3477 0.0 •0.3469 0.0 0.6946 -1.6180 0.6180 0.6180 EIGENVECTORS 0.0903 -0.0000 0.0903 -0.0000 -0.4121 0.0000 -0.4121 0.0000 0.0903 -0.0000 -0.4121 0.0000 0.4827 0.7071 0.4827 -0.7071 0 0.4474 0.4474 1962 0.1962 0.44 74 0.1962 0.3769 0.3769 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3473 0.3473 •0.2146 -0.2146 •0.6946 0.4293 •0.0000 0.0000 0.6015 •0.6015 0.3717 •0.3717 0.0000 •0.0000 -0.0000 0.0 0.3717 -0.3717 -0.6015 0.6015 0.0000 0.0000 0.0000 0.0 •0.2146 •0.2146 •0.3473 •0.3473 0.4293 0.6946 0.0000 •0.0000 Figure 4.1.4 Two Cospectral Isomorphic Graphs IV: THE EIGENVECTOR CONNECTION 42 P l*:(1 2 3)->(1 2 5) , (4 6 8) -> (3 4 6),5->8,7->7 This p a r t i a l permutation w i l l also map xi to , and x,,. to y^ .. He next try to map x. to a l i n e a r combination of y and y t. In order to find the constants, we try to solve the equations since these have to correspond i f our p a r t i a l permutation contains a proper permutation. The l i n e a r system obtained, however, i s not l i n e a r l y Independent, and we therefore have to try another choice. Solving and comparing x s to a, y5 + a i y t , we obtain Px*:1->5,2->1,3->2,4->3,5->8,6->4,7->7,8->6. He now have a p a r t i a l permutation from G to H which maps the fi v e f i r s t eigenvectors of G onto the corresponding eigenvectors of H. Since P^ * i s i n fact a permutation, i t cannot be refined any further. At t h i s point, we can either check the graphs d i r e c t l y to see whether i t i s an isomorphism, or compare the next three eigenvectors to ensure that P^* i s a proper p a r t i a l permutation. Either way, we w i l l f i n d i t i s indeed an isomorphism from G to H. 4.2 Connection with the Group of the Graph He next look at the r e l a t i o n between our algorithm and the group of the graph. IV: THE EIGENVECTOR CONNECTION 43 LEMMA 4.2.j!.Let G and H be isomorphic graphs.Let P* be a maximal proper p a r t i a l permutation from the nodes of G to the nodes of H, S= [s x ,... ,s,J i t s domain, T= {f ^ ,.. . , t^} i t s range, P*(s.)=t;, V i . Denote by Ss. the symmetric group on S; = {a,, ,... ,a,; } (that i s , the group consisting of a l l permutations of the elements of the set s-, regarded as permutation matrices). Then the group V = = < s ,S^ ,...,SS > i s a subgroup of ^ (G). Proof \ i s c l e a r l y a group. Se show each element of I i s an automorphism of G. Let re- P . There exi s t -P, ,..., ^ such that denote the group of permutations induced by P-*, as i n n T Lemma 4.2.1. Then i (G) = < < P,* >, P•P > ,where P i s some permutation r e f i n i n g Pw*. ££22f (i) By Lemma 4.2.1, i f « " t < P •* >, ,?;t X = RQT =Si-S~2- 6 <

,P;PT >. For example, we show how to obtain the group of the graph in Fig 4.2.1. Matching xv and yv , we obtain two maximal p a r t i a l permutations P*:(1,3) -> (1,3), (2,4) -> (2,4) Q*: (1,3) -> (2,4) , (2,4) -> (1,3) Comparing x. and y_ does not y i e l d a refinement of P* or I?: THE EIGENVECTOR CONNECTION 45 Q*. Clea r l y , for every permutation P r e f i n i n g P* or Q*, and for every x belonging to \ , there i s a y belonging to X3 s.t. x = Py , so that P* and Q* are maximal proper p a r t i a l permutations. Taking P = (1) , (2) , (3) , (4) ,Q = { 1 2 3 4) (the c y c l i c permutation on four elements), we have, by Theorem 4.2.2, P (G) = < (1 3) , (2 4) , (1 2 3 4) >. THEOREM 4.2.3. Let P*: S->T, Q*: S'->T' be two d i s t i n c t maximal proper p a r t i a l permutations from a graph G to an isomorphic graph H. Then S=S». Proof Let P*,Q* be maximal p a r t i a l permutations from G to H. Without loss of generality, l e t us assume P*: 1 ->1 , 2 ->2 ,... Q*: (1 ,2 )->{3 ,4 ),... Let P be a permutation r e f i n i n g P* and Q1,Q2 be permutations r e f i n i n g Q*.s.t. Q1{1)=3 , Q1(2)=4 Q2(1)=4 , Q2(2)=3, Q2TQ1 i s an automorphism of H. Now l e t P»=PQ2 Q1, P'(1 )=PQ2^ Q1 (1 )=2, P' (2 )=PQ2^ Q1 (2 ) =1, and IV: THE EIGENVECTOR CONNECTION 46 EIGENVALUES -2.0000 2.0000 -0.0000 -0.0000 EIGENVECTORS -0.5000 0.5000 -0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.0 0.7071 0.0 -0.7071 0.7071 0.0 -0.7071 0.0 4 4 Figure 4.2.1 A 4-point Graph IV: THE EIGENVECTOR CONNECTION 47 Thus the p a r t i a l permutation H*=d-.2-)-xi ,2 ) . * t ^ i A ~ n ^ i s a proper p a r t i a l permutation containing P*, contradicting the maximality of P*. COROLLARY 4.2.3A, I f G Is isomorphic to H and P,*,...,PV* are a l l the maximal proper p a r t i a l permutations from G to H, then P(G) •= < ,P- >, i fixed , 1-£j£n. Proof. The number of automorphisms of G i s egual to the number of isomorphisms from G to an isomorphic graph H. A l l the maximal proper p a r t i a l permutations from G to H induce the same p a r t i t i o n on the nodes of G, therefore each gives r i s e to the same number of Isomorphisms, namely 1j. Thus the t o t a l number of isomorphisms i s k||, The number of automorphisms i n <,P;P^ >, i fi x e d , j=1,...,k i s also k|J. Since P CP^P ;P^ i f j#k, a l l the elements of «P v*>,P lP^ r > are d i s t i n c t , and therefore t h i s i s a l l the group of G. COROLLARY 4.2.3B. If there exists a unique maximal proper p a r t i a l permutation P* from a graph G to an isomorphic graph H, then ^ (G) = < P* >, and the automorphism p a r t i t i o n i n g of G i s the domain of P* (similarly for H) . Proof. This follows d i r e c t l y from theorem 4.2.2, since PP T = I. IV: THE EIGENVECTOR CONNECTION 48 COROLLARY 4.2.3C. Let G, H be isomorphic graphs. Let P, *,...,P k* be a l l the maximal proper p a r t i a l permutations from G to H. Let P,*: s, -> t , , s ^ -> t c . Let 0. = \J P. * P.*"'(S: ) , U\ =\J P. *P . (s L ) . Then the automorphism par t i t i o n i n g of G i s {0C, ,U C i ,... ,u\ }. £I2°I' Clearly, the elements of U-:^ , m=1,»..,lj belong to the same set of the automorphism p a r t i t i o n i n g , and the sets in {0^ ,...,U- } have a non-empty in t e r s e c t i o n , or are equal, by Theorem 4.2.3. THEOREM 4.2.4. Let G, H be isomorphic graphs with a l l d i s t i n c t eigenvalues. Then the sets i n the domain of any maximal proper p a r t i a l permutation contain at most two elements. Proof By Theorem 4.2.2, i f P* i s a maximal proper p a r t i a l permutation and P* sends s= (a v ,a t,... ,a^) into t= (bi ,... ^ b^ ) , then S^ffG). Mowshowitz [22] has shown that i f a graph has a l l d i s t i n c t eigenvalues, every element of i t s group has order 2, and we therefore must have k<[2. 4.3 Formal Description of the Algorithm We have seen i n the preceding section that our method can IV: THE EIGENVECTOR CONNECTION 49 be used, depending on the graphs we are dealing with, to f i n d one isomorphism between two graphs, or to f i n d a l l isomorphisms between them. We present here two versions of the algorithm. The f i r s t , algorithm I, y i e l d s a l l the isomorphisms between two cospectral graphs whose eigenvalues are a l l d i s t i n c t , and i s meant to be used mostly to obtain the group of a graph with a l l d i s t i n c t eigenvalues, since when comparing two graphs for isomorphism one i s usually not interested i n finding a l l the isomorphisms. Algorithm I i s e s s e n t i a l l y a breadth-first search: the eigenvectors of G and B corresponding to eigenvalue i (i=1 , . . .,n) are compared to y i e l d 0, 1 or 2 maximal p a r t i a l permutations which map one onto the other. The p a r t i a l permutations obtained at each stage are intersected with a l l those obtained previously, and the r e s u l t i n g p a r t i a l permutations are the next candidates for proper p a r t i a l permutations. The p a r t i a l permutations obtained after a l l eigenvectors have been compared are proper, that i s , a l l the permutations they contain are isomorphisms from G to H. The second version, Algorithm I I , yields one p a r t i a l permutation between the two graphs. I t i s a dept h - f i r s t search: the eigenvectors belonging to eigenvalue i (i=1,...,k) are compared, one p a r t i a l permutation i s found, and i t i s intersected with the p a r t i a l permutation obtained previously. I f the i n t e r s e c t i o n i s empty, the algorithm t r i e s the next possible choice for a p a r t i a l permutation. If none i s found, i t backs up to the next choice for the preceding eigenvalue, etc. IV: THE EIGENVECTOR CONNECTION 50 Both versions make use of Algorithm (a) to f i n d the intersec t i o n of two p a r t i a l permutations. Algorithm II also uses Algorithms (b) and (c) to obtain the next combination and next permutation of indices to be used when setting up a system of l i n e a r equations as r e s t r i c t e d by a p a r t i a l permutation P*. ALGORITHM Ja}_: findinq the interse c t i o n of two p a r t i a l permutations. Given two p a r t i a l permutations, P* and Q*, the Algorithm finds a maximal p a r t i a l permutation R* s.t. R* i s contained i n P* and i n Q*, i . e . R* = P*H Q*. Let P* = p -> 1,..., p -> 1. Q* = g -> m,...,q -> m. The members of the elements of the p a r t i t i o n s are ordered by ascending value, the elements of the pa r t i t i o n s are ordered by ascending value of t h e i r f i r s t element. The p a r t i a l permutation returned by the Algorithm i s i n the form R* = r - > n , r e - > n. Step 1. Set R* =4 Step, 2. I f p* = vj) , Q* = , return R*. Else set p=pt , q=q. Delete p from {p^ },delete q from {q^ } . Step 3. I f c a r d i n a l i t y (p n g) = c a r d i n a l i t y (P* (p) r\ Q* (g) ) then set r=po,q , set n=R* (r) =P* (p) c\ Q* ( (1,...,n) Step 2. Sort the components of x^ i n sorted (x ) , the components of.y. i n sorted (y ). i i i vC\ (\-~\ Step 3. If x-=a, x; =-a, x =0, t* j , k and ^ 1 l - " ! JL =a, y^=-a, y =0, t*l,m, then set Q* = (j,k) -> (l,m), (a,.,.,a) -> (b.,...,b), a^#j,k, b,.*l,m. Set R*= , go to Step 7. Step 4. I f sorted (x ^ ) = sorted (y^ ), f i n d a maximal p a r t i a l permutation Q* such that Qx/= y c , for a l l permutations Q r e f i n i n g Q* (by matching maximal sets of components of equal value). Else, set Q* = Step 5. I f sorted (x t ) = -reverse (sorted (y^)) , fi n d a maximal p a r t i a l permutation R* such that Rx^ = -y t , f o r a l l permutations R r e f i n i n g R*. Else, set R* = ^ . Step 6. If Q* = ,...,\. Denote the m u l t i p l i c i t y of \ , i=1,...,t by ra (i) . The Algorithm t r i e s to match an eigenvector x of G corresponding to "X ; with a l i n e a r combination of the eigenvectors of H corresponding to V; . To solve the l i n e a r system involved, a set of rows of [ y- , ...,y. ] i s chosen, which 1 W o gives the c o e f f i c i e n t s of the system, and a set of components of x- i s chosen, which gives the right hand side of the system. The choice i s r e s t r i c t e d by the current p a r t i a l permutation.i denotes the current eigenvalue, PAR the current p a r t i a l permutation. The sets in PAR are ordered as i n Algorithm (a). SLE denotes the system of l i n e a r equations set up with elements of the eigenvectors of H corresponding to i , RHS i t s right-hand side, set up with elements of the f i r s t eigenvector of G corresponding to i . Step 1 set 1=1 set PAR (i) = (1 , ..., n) -> (1,. . . ,n) Step 2 i f i>t, go to Step 15 Step 3 get next combination of m(i) indices for the l i n a r system, as r e s t r i c t e d by PAR (i) {i.e., choose the f i r s t m (i) indices of y from the union of the smallest sets of PAR that contains m (i) elements, then m(i)+1 elements, m(i)+2, etc. ) . I f no choice i s l e f t , go to Step 12, else choose indices for elements of x that correspond to the indices chosen for y, as indicated by PAR. IV: THE EIGENVECTOR CONNECTION 56 Step 4 set up SIE with the chosen elements of [y. ,...,y. ]. Step 5 set up RHS with the chosen elements of x. Step 6 i f RHS i s the zero vector, go to Step 14 Step 7 solve the l i n e a r system. I f no solution e x i s t s , go to Step 3. Step 8 compare order(x^) and the li n e a r combination of y 's obtained to f i n d a p a r t i a l permutation MPP that maps one onto the other. Set flag{i)=1. Go to Step 10. Step 9 compare order(x) and the l i n e a r combination of y*s to find a negative p a r t i a l permutation MPP that maps one onto the other. Set f l a g ( i ) = 2. Step 10 i f MPP^p^get TEHP=PAR(i) <^ MPP (using Algorithm (a)) i f HPP=0 or TEMP=pr go to Step 13 Step 11 i=i+1 Step 12 PAR(i)=TEHP go to Step 2 Step 13 i=i-1 i f i=0, f a i l Step 14 i f flag(i)=1 go to Step 9. If f l a g ( i ) = 2 set flag(i)=0. Step 15 get next permutation of RHS (using Algorithm (b)). If none e x i s t s , go to Step 16. Else go to Step 7. Step 16 get next combination of indices f o r RHS (using Algorithm (c)). If none e x i s t s , go to Step 11. Else go to Step 6. Step 17 check whether TEMP contains an isomorphism get next permutation contained i n TEMP (using Algorithm TV: THE EIGENVECTOR CONNECTION 57 (b)). I f none e x i s t s , go to Step 15. Else check whether the current permutation i s an isomorphism. I f i t i s , stop,else, go to Step 17 4.4 Order of the computation I t i s very d i f f i c u l t to give a good estimate of the order of the computation f o r either Algorithm I or Algorithm I I , as i s the case in general for h e u r i s t i c algorithms. The obvious bounds are in general f a r too pessimistic. Let G be a graph on n nodes whose eigenvalues are a l l d i s t i n c t . I f we use algorithm I to f i n d i t s group, we may i n p r i n c i p l e obtain two maximal p a r t i a l permutations f o r each eigenvalue, and i f each of these yielded a new p a r t i a l permutation when intersected with those obtained previously, we would obtain , f o r eigenvalue k, 2 d i s t i n c t maximal p a r t i a l permutations mapping the f i r s t k eigenvectors of G to themselves. In p a r t i c u l a r , we would end up with 2 ^ proper maximal p a r t i a l permutations, yi e l d i n g at le a s t 2K automorphisms. Such a computation would obviously not be e f f i c i e n t . Mowshowitz [24] has shown that the order of the group of a graph whose eigenvalues are a l l d i s t i n c t i s at most 2 . Thus i t i s c l e a r l y impossible to obtain 2 d i s t i n c t maximal proper p a r t i a l permutations. IV: THE EIGENVECTOR CONNECTION EIGENVALUES -2.1774 -1.0000 0.0000 0.3216 2.8558 EIGENVECTORS 0.5244 -0.0000 0.7071 0.1312 -0.4558 0.5244 0.0000-0.7071 0.1312-0.4558 -0.3301 -0.7071 -0.0000 -0.3870 -0.4912 -0.3301 0.7071 0.0000 -0.3870 -0.4912 -0.4817 0.0000 0.0000 0.8161 -0.3192 P*: (1,2)->(1,2), (3,4) ->(3,4) , 5->5 P (G)= <{1,2) , (3,4) , (5) > Figure H'.-5.'\ A 5-point Graph with Simple Eigenvalues IV: THE EIGENVECTOR CONNECTION 59 in f a c t , since our algorithm yields generators for f (G), rather than a l l the elements of i"1 (G) ( i . e . , p a r t i a l permutations rather than permutations), even 2 i s in general too high a bound. For example, the graph of Fig 4.5.1 (used as an example by Mowshowitz) has 4 automorphisms, but our algorithm yields only one p a r t i a l permutation which generates the group. Thus, i n practice, the number of maximal proper p a r t i a l permutations obtained i s often far les s than the order of the group. Mapping one eigenvector onto the other involves computation of order n log n (since i t consists of ordering the vectors and comparing them, and ordering the r e s u l t i n g p a r t i a l permutation). S i m i l a r l y , intersecting two p a r t i a l permutations can be done in a number of steps of order n x. Thus as long as the number of p a r t i a l permutations i s small, the computation w i l l be e f f i c i e n t . In a l l the examples we t r i e d , the number of p a r t i a l CM*) permutations generated was f a r smaller than 2 , and even though p a r t i a l permutations may be generated at some stage which are l a t e r rejected, the computation was fast in a l l cases. We next look at the computation involved in Algorithm I I . Let X be an eigenvalue of m u l t i p l i c i t y k. We f i r s t have to f i n d a system of k l i n e a r equations which i s l i n e a r l y independent (Step 3), In the worst case, to set up the l i n e a r system, we w i l l be choosing k out of n elements, and therefore might have to try ^ systems. Solving the system i s of the order of 1} , so that altogether we might need o( i ) steps to f i n d a system which has a solution. Usually, however, the choices for the l i n e a r system w i l l be f a r more r e s t r i c t e d , as IV: THE EIGENVECTOR CONNECTION 60 soon as a n o n - t r i v i a l p a r t i a l p e r m u t a t i o n I s o b t a i n e d . I n p r a c t i c e , a l i n e a r l y independent system i s o f t e n found i m m e d i a t e l y . I n o r d e r t o f i n d a mapping of the e i g e n v e c t o r s , we then compare s o r t (x) t o s o r t (21 a y . ) , where x, y- b e l o n g t o ^ . I f t h i s does not y i e l d a mapping, or i f t h e p a r t i a l p e r m u t a t i o n o b t a i n e d does not agree w i t h t h e one o b t a i n e d p r e v i o u s l y , we t r y t o s o l v e the same system a g a i n w i t h a d i f f e r e n t o r d e r i n g o f i t s r i g h t hand s i d e . I f t h e system uses 1^ elements of i s e t s o f the c u r r e n t p a r t i a l p e r m u t a t i o n , the number of p o s s i b l e p e m u t a t i o n s i s i v 1 !. For each such c h o i c e , we s o l v e the system a g a i n . Only back s u b s t i t u t i o n i s n e c e s s a r y , t h e r e f o r e i f we have t o t r y a l l p e r m u t a t i o n s , t h e c o m p u t a t i o n i s of o r d e r \ , T\ 1 !k . I f no p e r m u t a t i o n o f the r i g h t - h a n d - s i d e o f the V-1 l i n e a r system y i e l d s a s o l u t i o n , we next t r y t o use a d i f f e r e n t c o m b i n a t i o n of elements of x. assume the system uses 1-elements o f i s e t s of the c u r r e n t p a r t i a l p e r m u t a t i o n , where s e t i has C : e l e m e n t s . Then t h e r e a r e p o s s i b l e ways of c h o o s i n g the 1^ e l e m e n t s , f o r each j , and t h e r e f o r e we have T TC,^ p o s s i b l e c o m b i n a t i o n s o f elements of x f o r the r i g h t hand V-' * s i d e of our system o f e g u a t i o n s . F o r each o f t h e s e c o m b i n a t i o n s , we have t o t r y a l l t h e p o s s i b l e p e r m u t a t i o n s of the chosen elements. We t h e r e f o r e may have t o t r y and s o l v e the system w i t h d i f f e r e n t r i g h t hand s i d e s , a t worst *vt^k!. T h i s i s f o r example t h e case w i t h t h e c o s p e c t r a l graphs of Appendix I I . The o n l y e i g e n v a l u e of m u l t i p l i c i t y one does not y i e l d a n o n - t r i v i a l p a r t i a l p e r m u t a t i o n , s i n c e the graph i s IV: THE EIGENVECTOR CONNECTION 61 r e g u l a r . The next eigenvalue has m u l t i p l i c i t y t h r e e . Since the graphs are not isomorphic, we r e p e a t e d l y back up to the second r o o t , i n an attempt to f i n d a mapping between the e i g e n v e c t o r s t h a t can a l s o be used with the f o l l o w i n g r o o t s . For the second r o o t , t h e r e are (^ -^ V\ p o s s i b l e c h o i c e s f o r a r i g h t hand s i d e , once a l i n e a r l y independent system has been found. Each of these has t o be t r i e d b efore r e t u r n i n g the answer t h a t the graphs are not isomorphic, a f t e r about 20 seconds. T h i s example, however, i s a case of a worst p o s s i b l e graph f o r our a l g o r i t h m . In a l l other examples we t r i e d , i f the graphs were c o s p e c t r a l but not isomorphic, t h i s was d i s c o v e r e d very r a p i d l y , with v i r t u a l l y no b a c k t r a c k i n g . S i m i l a r l y , f o r isomorphic graphs, an answer (that i s , a permutation s p e c i f y i n g the isomorphism) was u s u a l l y returned with l i t t l e b a c k t r a c k i n g . For graphs whose eigenvalues have low m u l t i p l i c i t i e s , and p a r t i c u l a r l y f o r graphs whose eigenvalues are a l l d i s t i n c t the a l g o r i t h m was found to be very e f f i c i e n t , t h a t i s , very l i t t l e backing up was r e q u i r e d . The a l g o r i t h m i s a l s o very e f f i c i e n t i f the group of the graph i s l a r g e . For example, the complete graph on n p o i n t s has two d i s t i n c t e i g e n v a l u e s , of m u l t i p l i c i t y 1 and n-1 r e s p e c t i v e l y . Comparing the e i g e n v e c t o r s belonging to the f i r s t e i g e n v a l u e w i l l not r e f i n e the i n i t i a l p a r t i a l permutation (1,...,n)-> (1,... ,n) , s i n c e the graph i s r e g u l a r . However, comparing the e i g e n v e c t o r s belonging to the second eigenvalue w i l l y i e l d a s o l u t i o n immediately. Thus the e f f i c i e n c y of the a l g o r i t h m seems d i r e c t l y r e l a t e d to the group of the graphs. Note t h a t a l g o r i t h m s t h a t t r y to d i s t i n g u i s h IV: THE EIGENVECTOR CONNECTION 62 between nodes by looking at t h e i r a t t r i b u t e s would have d i f f i c u l t y i n matching two complete graphs. The e f f i c i e n c y of our algorithm then seems to depend mainly on two factors: the m u l t i p l i c i t y of the eigenvalues, and the richness of the group of the graph. The relationship between these two factors i s poorly understood by the author, and therefore nothing more w i l l be said on the subject. 4.5 Conclusion We have discussed.in t h i s thesis the use of the eigenvalues and eigenvectors of the adjacency matrices of cospectral graphs in finding graph isomorphism. We presented two basic algorithms, e s s e n t i a l l y a breadth f i r s t and a depth f i r s t search, which use t h i s method. In both cases, various devices can be used to speed up the computation. For example, i f at any point a permutation i s obtained, i t i s useless to keep trying to refine i t , instead one should check d i r e c t l y for isomorphism. Si m i l a r l y i f a p a r t i a l permutation i s obtained which contains only a small number of permutations, etc. We intend to look in more d e t a i l at various strategies for minimizing backtracking in our algorithms. For example, i t might be worthwhile (this can only be ascertained by extensive testing) to f i r s t check whether there e x i s t s a mapping of the f i r s t eigenvector of G belonging to \ t to a lin e a r combination of the eigenvectors of H belonging to \ , f o r each i , before trying to f i n d one mapping which works for a l l i (cf. Mack worth £20]). IV: THE EIGENVECTOR CONNECTION 63 Algorithm II i s very e f f i c i e n t when dealing with graphs with simple eigenvalues. The reason i s that i n t h i s case there can be only 2 mappings of the vectors ( i f they are normalized), while i f the eigenvalue has m u l t i p l i c i t y k, we may have to try up to l e^k! mappings. One way to retain the e f f i c i e n c y of the algorithm in the case where the eigenvalues are not simple would be to derive the eigenvectors i n such a way that i f P^ AP = B then x ^ = P y ^ for i=1,,..,n, i . e . , use an algorithm for computing the eigenvectors of a matrix which i s invariant under permutations. It i s not clear whether t h i s i s possible, but i f such an algorithm could be found, and be as e f f i c i e n t and as accurate as those currently used, we would be well on our way to finding an e f f i c i e n t general purpose graph isomorphism algorithm. BIBLIOGRAPHY 64 1. BOWD1ER, H.; MARTIN, R. S.; REINSCH, C. ; WILKINSON, J.H. The QS and QL algorithms for symmetric matrices. Numerische Mathematik, JH (1968), pp. 293-306. 2. , BIRKHOFF, G.; MAC LANE, S, A survey, of modern algebra. Macmillan, New York, 1953. 3. BUSACKER, E. G.; SAATY, T. L . j F i n i t e Graphs and Networks, McGraw-hill, 1965. 4. CHAO, C.Y. On, groups and graphs. Proc. Amer. Math. Soc. 118 (1965) , 488-497. 5. COLLATZ, L.; SINOGOWITZ, 0. Spektren endlicher graphen, Abh. Math Sem. Univ. Hamburg 21 (1957), 63-77. 6. COOK, S. A. The complexity of theorem-proving Thesis, i Univerprocedures. Proc. Of t h i r d annual ACM sjjmDosium on theorY of computing, Shaker Heights, Ohio, 1971. 7. CORN EIL, D. G. Graph isomorphism. Ph.D. Thesis, University of Toronto, Dept. Of Computer Science, 1968. 8. CORNEIL, D. G. ; GOTLIEB, C. C. An e f f i c i e n t algorithm for graph isomorphism. J. A. C. M., 17 #1 (1970), pp. 51-64. 9. CVETKOVIC, D. M. Graphs and t h e i r spectra. Ph.D. Thesis, University of Beograd, Faculty of E l e c t r i c a l Engineering, 1971. 10. EDMONDS, J. Paths, trees and flowers. Can. J. of Math.,11 (1965) pp. 449-467. 11.,ELPAS, B.; TURNER, J. Graphs with c i r c u l a n t adjacency matrices. J . of Comb. Theory, 9 (1970), pp. 297-307 12. FISHER, M. E. On hearing the shape of a drum, J . of BIBLIOGRAPHY 65 Comb. Theory, 1 (1966), pp. 105-125 1.3. FINCK, H.-J. Vollstandiges produkt, chromatische zahl und characteristisches polynom regularer graphen I. Wiss. Z. Techn. , Hochsch. Ilmenau J.J, (1965) pp. 81-87. 14. GANTMACHER, F. R. The Theory of Matf-iSes, Vol. II (English t r a n s l a t i o n ) , Chelsea, New York, 1959. 15. HARARY, F. Graph Theory, Addison-Wesley, Reading, 1969. 16. HARARY, P.; KING, C.; MOWSHOWITZ, A.; READ, R. C. Cospectral graphs and digraphs. B u l l . London Math. Soc., 3 (1971) , pp. 321-328. 17.,HOPCROFT, J. E.; TARJAN, R. E. A V log v algorithm for isomorphism of tricpnnected planar graphs. J.C.S.S., 7 (1973) pp. 323-331. 18. HOPCROFT, J. E.; TARJAN, R. E. Isomorphism of planar graphs (working paper). In Complexity of Computer Commutation, ed. By R. E. M i l l e r and J . W. Thatcher, Plenum Press, New York, 1972. 19. HOPCROFT, J. E.; WONG, J. K. Linear time algorithm f o r isomorphism of planar graphs. In Proc. Of the 6th annual ACM symposium on the theory of computing. S e a t t l e , 1974. 20. MACKWORTH, A. K, Consistency in networks of rel a t i o n s . Technical report 75-3, Dept. Of Computer Science, UBC, 1975. 21. MARTIN, R. S.; REINSCH, C.; WILKINSON, J. H. Householder's t r i d i a g o n a l i z a t i o n of a symmetric matrix. Numerische Mathematik 11, (1968) pp. 181-195. 22. MOWSHOWITZ, A. The group of a graph whose adjacency matrix BIBLIOGRAPHY 6 6 has a l l d i s t i n c t eigenvalues. In Proof Tjscjinigu^s^ i n Graph Theory, ed. By F. Harary, Academic Press Inc., New York, 1 9 7 2 . 2 3 . MOWSHOWITZ, A. The c h a r a c t e r i s t i c polynomial of a graph. J . of Comb. Theory, 1 2 ( 1 9 7 2 ) , pp. 1 7 7 - 1 9 3 . 2 4 . MOWSHOWITZ, A. The adjacency matrix and the group of a graph. In new Directions i n GrajDh Theory, Academic Press Inc., New York and London, 1 9 7 3 . 2 5 . SACHS, H. Uber t e l l e r , faktoren und characteristlsche polynome von graphen. Wiss, z. Techn. Hochsch. IImenau, J 3 ( 1 9 6 7 ) pp. 4 0 5 - 4 1 2 . 2 6 . SCHWENK, A. J . Almost a l l trees are cospectral. In new Directions i n the Theory of Graphs, ed. Bh F. Harary, academic Press Inc., New York and London, 1 9 7 3 . 2 7 . SCOINS, H.T. Placing trees i n lexicographic order. In Machine Intelligence 3 , ed. By D. Michie, American Elsevier Publishing Company, Inc., 1 9 6 8 . 2 8 . SUSSENGUTH, E. H. A graph-theoretic algorithm for matching chemical structures. J . Of Chem. Doc.,5 ( 1 9 6 5 ) , pp. 3 6 - 4 3 . 2 9 . TURNER, J . Point-symmetric graphs with a prime number of points. J . Of Comb. Theorey, 3 ( 1 9 6 7 ) pp. 1 3 6 - 1 4 5 . 3 0 . TURNER, J . Generalized matrix functions, and the graph isomorphism problem. SIAM J . Of A ^ J J I , Math., .16 ( 1 9 6 8 ) , pp. 5 2 0 - 5 2 6 . 3 1 . UNGER, S. H. GIT - a h e u r i s t i c program f o r testing pairs of directed l i n e graphs for isomorphism. C.A.C.M.,7 ( 1 9 6 4 ) BIBLIOGRAPHY 67 pp. 26-34. 32. WEINBERG, L. A simple and e f f i c i e n t algorithm f o r determining isomorphism of planar t r i p l y connected graphs. IEEE Trans. On C i r c . Theory,J3 (1966) pp. 142-148. 33. WEINBERG, L. On the maximum order of the automorphism group of a planar t r i p l y connected graph. SI AM J. Of Apjp.1. Math., (1966) pp. 729-738. 34. WHITNEY, H. Congruent graphs and the connectivity of graphs. Amer. J. of Math.,54 (1932) pp. 150-168. 35. WILKINSON J. H. The Algebraic Eigenvalue Problem, Oxford University Press, London, 1965. APPENDIX A Examples of Cospectral Graphs 68 EIGENVALUES -2.0840 -1.5718 -1.0000 -0.4317 0.0 EIGENVALUES 2.0840 0.4317 1.0000 1.5718 EIGENVECTORS -0.1919 -0.3626 0.0 -0.2858 -0.1919 -0.3626 0.0 -0.2858 0.3999 0.5699 0.0 0.1234 -0.4496 -0.1707 0.0 0.5184 0.5371 -0.3017 0.0 -0.3472 -0.3348 0.3224 -0.5000 -0.1842 0.1607-0.2051 0.5000 0.4267 -0.3348 0.3224 0.50C0 -0.1842 0.1607 -0.2051 -0.5000 0.4267 EIGENVECTORS 0.1919 0.1919 0.3999 0.4496 0.5371 0.334 8 0. 1607 0.3348 0.1607 0.7071 0.2858 0.0 -0. 3626 0.7071 0.2858 0.0 -0.3626 0.0 0.1234 0.0 -0.5699 0.0 -0.5184 0.0 -0.1707 0.0 -0.34 72 0.0 0.3017 0.0 0.1842 0.5000 0.3224 0,0 0.4267 0.5000 0.2051 0.0 0.1842 -0.5000 0.3224 0,0 0.4267 -0.5000 0.2051 (1) Smallest Cospectral Trees with I d e n t i c a l Degree Pa r t i t i o n i n g {[16]) APPENDIX A Examples of Cospectral Graphs 69 EIGENVALUES -2.0840 -1.5718 -1.0000 -0.4317 0.0 0.4317 1.0000 1.5718 EIGENVALUES 2.0840 EIGENVECTORS -0.2367 -0.2280 -0.3536 -0.1303 0.7071 -0.2367 -0.2280 -0.3536 -0.1303 -0.7071 0.4934 0.3584 0.3536 0.0562 -0.0000 -0.5547-0.1073 0.3536 0.2363 0.0000 0.2662 0.0683 -0.3536 -0.5473 0.0000 0.3964 -0.2580 -0.3536 0.3890 -0.0000 -0.2714 0.5128 -0.00G0 -0.4042 -0.0000 0.1692 -0.5481 0.3536 -0.2145 0.0000 -0.0812 0.3487 -0.3536 0.4968 0.0000 -0.1303 -0.3536 0.2280 -0.1303 -0. 3536 0. 2280 -0.0562 -0. 3 536 0.3584 0.23 63 0.3536 0. 1073 0.5473 0. 3536 0.0683 -0.3890 0. 3 536 -0.2580 -0.4042 -0. 0000 -0.5128 0.2145 -0. 3536 -0.5481 0.4968 -0. 3536 -0. 3487 EIGENVECTCBS 0.2367 0.2367 0.4934 0.5547 0.266 2 0.3964 0.2714 0.1692 0.0812 (1) smallest Cospectral Trees with I d e n t i c a l Degree Pa r t i t i o n i n g ([16]) APPENDIX A Examples of Cospectral Graphs EIGENVALUES -2.0000 2.0000 0.0 EIGENVECTORS 0.0 0. 0 0.0 0.0 0. 0 0.0 1.0000 -0.5000 0.5000 0. 0 0.7071 0.0 0.5000 0.5000 0. 7071 0.0 0.0 -0.5000 0.5000 0. 0 -0.7071 0.0 0.5000 0.5000 -0. 7071 0.0 0.0 • EIGENVALUES -2.0000 2.0000 0.0 EIGENVECTORS 0.0 0.0 0.7071 -0.3536 -0.3 536 -0.3536 -0.3536 0.7071 0.0 0.3536 0.7887 0.3536 -0.5774 0.0 0.0 0.2113 -0.2887 0.5774 -0.2887 0.3536 -0.2113 -0.7887 -0.2887 0.3536 0.0 0.0 0.8660 (2) Smallest Cospectral Graphs {[16]) APPENDIX A Examples of Cospectral Graphs EIGENVALUES -1.9032 0.1939 1.0000 2.7093 -1.0000 -1.0000 EIGENVECTORS 0.2603 0.2136 0.2603 0.2136 -0.7558 -0.1721 0.2603 0.2136 0.2603 0.2136 0.3971 -0.8877 *6 -0.5000 -0.50 00 0.0 0.5000 0.5000 0.0 -0.3696 -0.3696 -0.6318 -0.3696 -0.3696 -0.2332 0.3386 -0.3386 0. 0 -0.6208 0.6208 0.0 0.6208 -0.6208 0.0 0.3386 -0.3386 0.0 EIGENVALUES -1.9032 0.1939 1.0000 2.7093 -1.0000 -1.0000 EIGENVECTORS 0.2808 0.6277 -0.5344 0.1217 0.3682 -0.3020 0.3682 -0.3020 -0.5344 0.2808 0.5000 -0.1649 -0.5000 0.0000 0.5000 -0.4467 0.5000 0.0 0.0000 -0.5227 -0.0000 -0.7071 0.0000 -0.5227 0.0000 0.7071 0.1217 -0.5000 -0.4467 -0.5000' 0.0 0.6277 -0.5000 -0.1649 0.5000 0.0 (3) Smallest Cospectral Connected Graphs ([16]) APPENDIX A Examples of Cospectral Graphs 72 EIGENVALUES -2.2725 -1.7320 -1.4924 -0.7801 0.7801 1.4924 1.7320 2.2725 EIGENVALUES -0.0000 -0.0000 -0.0000 -0.0000 EIGENVECTORS 0.1 180 0.2887 -0.2738 -0.13 50 -0. 1350 0.2738 0.2887 -0.1180 0.1 180 0.2887 -0.2738 -0. 1350 -0. 1350 0.2738 0.2887 -0.1180 -0.2681 -0.5000 0.4087 0. 1053 -0. 1053 0.4087 0.5000 -0.2681 0.373 4 0.2887 -0.0622 0. 1879 0. 1879 0.0622 0.2887 -0.3734 -0.5803 0.0 -0.3158 -0. 2519 0. 2519 -0.3158 0.0 -0.5803 0.2554 0.0 0.2116 0. 3229 0. 3229 -0.2116 0.0 -0.2554 0.3167 0.0 0.3841 -0. 5022 -0. 5022 -0.3841 0.0 -0.3167 -0.1394 0.0 -0.2574 0.6437 -0. 6437 -0.2574 0.0 -0.1394 0.3734 -0.2887 -0.0622 0. 1879 0. 1 879 0.0622 -0.2887 -0.3734 -0.2681 0.5000 0.4087 0. 1053 -0. 1053 0.4087 -0.5000 -0.2681 0.1 180 -0.2887 -0.2738 -0. 1350 -0. 13 50 0.2738 -0.2887 -0.1180 0. 1 180 -0.2887 -0.2738 -0. 1350 -0. 13 50 0.2738 -0.2887 -0.1180 EIGENVECTORS -0.0996 0.7071 0. 1261 -0.3053 -0.0996 -0.7071 0. 1261 -0.3053 0.0 0.0 0.0 0.0 0. 1992 0.0 -0.2522 0.6107 0.0 0.0 0.0 0.0 0.2865 0.0 -0.23 57 -0.6586 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -0.4857 0.0 0.4878 0.0479 0.0 0.0 0.0 0.0 0.7451 0.0 0.2521 0.0170 -0.2594 0.0 -0.7400 -0.0650 8 (4) Non-isomorphic Generalized Cospectral Trees (£30J) APPENDIX A Examples of Cospectral Graphs 73 EIGENVALUES -2.2725 -1.7320 -1.4924 -0.7801 0.7801 1.4924 1.7320 2.2725 EIGENVALUES -0.0000 -0.0000-0.0000 -0.0000 EIGENVECTORS 0. 2337 0.2041 0. 1758 -0.1986 -0..1986 0.1758 -0. 2041 0.2337 0. 2337 0.2041 0. 1758 -0.1986 -0.1986 0.1758 -0. 2041 0.2337 0. 2337 0.2041 0. 1758 -0.1986 -0. 1986 0.1758 -0.2041 0.2337 -0 . 5312 -0.3536 - 0 . 2624 0.1550 -0.1550 0.2624 -0 . 3536 0.5312 0. 5059 -0.0000 -0.1359 0.4750 0.4750 -0.1359 0. 0000 0.5059 -0 . 3 255 0.3536 - 0 . 0268 -0.3543 0.3543 0.0268 0. 3536 0.3255 0. 2 33 7 -0.6124 0. 1758 -0.1986 -0.1986 0, 1758 0. 6124 0.2337 - 0 . 1029 0.3536 -0. 1178 0.2546 -0.2546 0.1178 0. 3536 0.1029 -0 . 102 9 0.3536 -0 . 1178 0.2546 -0.2546 0. 1178 0.3536 0.1029 -0 . 2930 0.0000 0. 4919 -0.1713 0.1713 -0.4919 0. 0000 0.2930 0. 159 9 -0.0000 -0 . 5982 -0.3414 -0.3414 -0.5982 0. 0000 0.1599 - 0 . 0704 0.0000 0. 4009 0.4376 -0.4376 -0.4009 0. 0000 0.0704 EIGENVECTORS -0.0000 0.4082 0. 7054 - 0 . 0485 -0.0000 0.4082 -0.7054 0. 0485 0.0000 -0.8165 0. 0000 -0 . 0000 0.0000 -0.0000 0. 0000 0. 0000 0.0000 -0.0000 0.0 - 0 . 0000 0.0000 -0.0000 0. 0367 0. 5 333 -0.0000 0.0000 0. 0000 0. 0000 0.7071 0.0000 - 0 . 0183 -0. 2666 -0.7071 0.0000 - 0 . 0183 -0 . 2666 -0.0000 0.0000 -o . 0367 -0 . 5333 -0.0000 0.0000 0. 0 0.0000 0.0000 -0.0000 0. 0367 0. 5333 (4) Non-isomorphic Generalized cospectral Trees (£30]) APPENDIX A Examples of Cospectral Graphs 74 EIGENVALUES -2.7152 -1.2758 -1.0000 1.0000 1.2758 2.7152 -0.0000-0.0000 EIGENVALUES -0.0000 EIGENVECTORS -0.1674 -0.4246 0.0 0.0 0.4246 0.1674 0. 7071 -0.0474 -0.1674 -0.4246 0.0 0.0 0.4246 0.1674 -0. 7071 -0.0474 0.454 4 0.5418 0.0 0.0 0.5418 0.4544 0. 0 0. 0 -0.4495 0.0790 0.0 0.0 -0.0790 0.4495 0. 0 -0.6501 0.3831 -0.3213 0.5000 0.5000 -0.3213 0.3831 0. 0 0.0 -0.1411 0.2518 -0.5000 0.5000 -0.2518 0.1411 0. 0 -0.0949 -0.4495 0.0790 0.0 0.0 -0.0790 0.4495 0. 0 0.7449 0.3831 -0.3213 -0.5000 -0.5000 -0.3213 0.3831 0. 0 0.0 -0.141 1 0.2518 0.5000 -0.5000 -0.2518 0.1411 0. 0 -0.0949 EIGENVECTORS 0.2848 0.2848 0.0 -0.4010 0.0 0.5695 -0.1685 0.0 0.5695 (5) Non-Isomorphic Generalized cospectral Connected Graphs ([30]) APPENDIX A Examples of Cospectral Graphs 75 EIGENVALUES -2.7152 -1.2758 -1.0000 1.0000 1.2758 2.7152-0.0000 -0.0000 EIGENVALUES -0.0000 EIGENVECTORS -0.1781 -0.0998 -0.5000 0.5000 0.0998 -0.1781 -0.1291 0.2610 0.4835 0.1273 0.5000 0.5000 0.1273 -0.4835 -0.0000 -0.0000 -0.3562 -0.1995 0.0000 -0.0000 0.1995 -0.3562 -0.2582 -0.7746 0.4835 0.1273 -0.5000 -0.5000 0.1273 -0.4835 0.0000 -0.0000 -0.1781 -0.0998 0.5000 -0.5000 0.0998-0.1781 -0.1291 0.2610 -0.3562 -0.1995 0.00G0 0.0000 0.1995 -0.3562 -0.2582 0.5136 -0.4225 0.3364 -0.0000 0.0000 -0.3364 -0.4225 0.6455 -0.0000 0.1800-0.6838 0.0000 0.0000 -0.6838 -0.1800 0.0000 0.0000 -0.0663 0.5360 0.0000 0.0000 -0.5360 -0.0663 -0.6455 0.0000 EIGENVECTORS 0.576 1 -0.0000 0.0038 0.0000 0.5761 -0.5799 0.0000 -0.0000 -0.0000 (5) Non-Isomorphic Generalized Cospectral Connected Graphs {[30]) APPENDIX B A Nasty Pair of Cospectral Graphs 76 EIGENVALUES 4.0000 -0.0000 -0.0000 -0.0000 2.0000 2.0000 2.0000 -2.0000 EIGENVALUES -2.0000 -2.0000 -2.0000 -2.0000 EIGENVECTORS -0. 2887 -0. 0184 -0. 0071 -0.4996 0.0 0.50 00 0.0 0. 1899 -0. 2887 0. 4907 -0. 0943 -0.0167 0.3402 0.2500 -0.2679 -0.0461 -0. 2887 0. 0940 0. 4910 -0.0104 0.3660 0.2500 0.2314 -0.1438 -0. 2887 -0. 4907 0. 0943 0.0167 -0.3660 0.2500 -0.2314 -0.0664 -0. 2887 0. 0 184 0. 0071 0.4996 -0.0258 0.0 -0.4 993 -0.2479 -0. 2887 0. 0940 0. 4 910 -0.0104 -0.3660 -0.2500 -0.2314 0.3142 -0. 2887 -0. 0940 -0. 4910 0.0104 -0.3402 0.2500 0.2679 -0.1235 -0. 2887 0. 0184 0. 0071 0.4996 0.0258 0.0 0.4993 -0.2018 -0. 2887 0. 4907 -0. 0943 -0.0167 -0.3402 -0.2500 0.2679 0.3253 -0. 2887 -0. 0940 -0. 4910 0.0104 0.34 02 -0.2500 -0.2679 0.2940 -0. 2887 -0. 4907 0. 0943 0.0167 0.3 660 -0.2500 0.2314 0.3455 -0. 2887 -0.0184 -0. 0071 -0.4996 0.0 -0.5000 0.0 -0.6 3 95 EIGENVECTORS 0. 4448 -0.1093 0. 0370 0.4116 0. 1023 -0.0531 0. 1257 -0.6208 -0.5472 0.1623 -0. 1627 0.2092 0. 0003 0.5506 -0. 0653 -0.3238 0. 0135 -0.1021 0. 3853 0.4429 -0. 013 8 -0.4485 -0. 3199 -0. 1192 -0. 4451 -0.4413 0. 0284 -0.0 878 0. 5167 -0.0072 -0. 3284 -0.0328 -0. 0716 0.4485 0. 3000 0.1207 -0. 1159 0.1551 -0,5110 0.1779 0. 0305 -0.1551 0. 4911 -0.1764 0. 0854 0.0 0. 0199 -0.0015 Non-isomorphic Cospectral Graphs APPENDIX E A Nasty p a i r of cospectral Graphs 77 EIGENVALUES 4.0000 -0.0000 -0.0000 -0.0000 2.0000 2.0000 2.0000 -2.0000 EIGENVALUES -2.0000 -2.0000 -2,0000 -2.0000 EIGENVECTORS -0. 2887 0. 0000 -0. 0000 -0. 5000 -0.2167 -0.3749 0.2500 -0.0855 -0. 2887 0. 0000 0. 0000 -0. 5000 0.4257 -0.0793 0.2500 -0.0979 -0.2887 0. 0000 -0. 0000 0. 5000 -0.2167 -0.3749 0.2500 -0.0872 -0. 2887 0. 0000 -0. 0000 0. 5000 0.4257 -0.0793 0.2500 -0.0962 -0. 2887 -0. 0000 0. 5000 0. 0000 -0.2167 -0.3749 -0.2500 0.3435 -0. 2887 0. 0000 -0. 5000 -0. 0000 -0.4257 0.0793 0.2500 0.0125 -0. 2887 -0. 0000 0. 5000 0. 0000 0.2167 0.3749 0.2500 0.0232 -0. 2887 0. 0000 -0. 5000 -0. 0000 0.4257 -0.0793 -0.2500 0.3542 -0. 2887 -0. 5000 -0. 0000 -0. 0000 -0.2090 0.4542 0.0000 -0.3066 -0. 2887 0. 5000 -0. 0000 -0.0000 -0.2090 0.4542 -0.0000 0.4 54 3 -0. 2887 -0. 5000 -0. 0000 0. 0000 -0.0000 -0.0000 -0.5000 0.1233 -0. 2887 0. 5000 0. 0000 0. 0000 0.0000 -0.0000 -0.5000 -0.6376 EIGENVECTORS 0. 0087 0.6092 0. 1929 0.0313 -0. 308 3 -0.5577 -0. 0012 0.0 307 -0. 0699 -0.2127 0. 1084 0.5892 -0. 2297 0.2641 0. 0834 -0.5272 0. 2460 -0.2924 0. 0475 -0.3878 0. 1149 -0.1555 -0.5406 -0.2948 0, 353 3 0.1896 -0. 4310 0.2638 0. 4844 0.0527 0. 1571 0.1707 0. 1928 -0.1337 0. 5088 -0.0936 -0.3614 0.0482 0.2711 0.0626 -0. 4924 0.1851 -0. 3170 0.1556 0. 0617 0.0032 -0. 0793 -0.0006 Non-isomorphic Cospectral