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<e.V, (x,y) fe E, then x and y a r e a d j a c e n t . I f p,qe V, x= (P#q) <=_ E, p and g are i n c i d e n t t o x. A graph as d e f i n e d here i s f i n i t e , u n d i r e c t e d , and has no l o o p s or m u l t i p l e edges. T h i s r e s t r i c t i o n t o u n d i r e c t e d graphs i s s i g n i f i c a n t , s i n c e our a l g o r i t h m uses a r e s u l t (Theorem 2.1) which i s v a l i d o n l y f o r symmetric m a t r i c e s , and t h e r e f o r e h o l d s o n l y f o r t h e a d j a c e n c y m a t r i x of an u n d i r e c t e d graph. The complement G o f a graph G i s t h e graph whose s e t o f v e r t i c e s I s V(G) and whose s e t of edges i s t h e s e t o f a l l edges between nodes of V (G) which a r e not i n E (G) . I: INTRODUCTION 3 A sub_3rap_h H=H(V«,E«) of a graph G(V,E)is a graph such that V V and E» i s a subset of E whose elements are incident to vertices i n V . The decree of a vertex i s the number of l i n e s incident with i t . A graph i s regular i f a l l i t s vertices have the same degree. Two graphs G and H are isomorghic (G-H) i f there e x i s t s a one to one correspondence P between t h e i r vertices s.t. x,y £ 7(G), (x,y) t E:(cs:) i f and only i f (P (x) ,P (y) ) €. E (H) .. An invariant of a graph G i s a number associated with G which i s the same for any graph isomorphic to G. A complete set of invariants determines a graph up to isomorphism. No "decent" (Harary,[ 15 ]) complete set of invariants i s known, but p a r t i a l sets are used i n several h e u r i s t i c programs f o r finding graph isomorphism, for example Sussenguth [28] and Unger [31] , whose programs are described i n the next Chapter. A waljs of a graph G i s an alternating seguence of points and l i n e s , beginning and ending with points, in which each l i n e i s incident with the two points immediately preceding and following i t . I t Is a £ath i f a l l points are d i s t i n c t . I f the path i s closed, i t i s a c j c l e . The length of a path i s the I : INTRODUCTION 4 number of l i n e s i n i t . Two points i n a graph are connected i f there e x i s t s a path between them. A graph G i s connected i f every two points are connected. A M£§££M SLR^Ek consists of a f i n i t e set V of points together with a c o l l e c t i o n of pairs of d i s t i n c t points of V. Such a pair (u,v) i s c a l l e d an arc (or a directed l i n e ) . Point u i s said to be adjacent to point v, v i s adjacent from u. The in-degree of a point u i s the number of points adjacent to i t , i t s out-degree i s the number of points adjacent from i t . A tree i s a connected graph with no cycles. A graph i s £lanar i f i t can be drawn in the plane so that no two edges i n t e r s e c t . A face of a planar graph i s a region defined by Its embedding on the plane. A graph i s labeled i f i t s points are distinguished by names. We w i l l use the set {1,2,...,n} to label the verti c e s of graphs. A labeled graph on n points [1,...,n} can be represented by i t s adjacency matrix A= (a^ .) , where A i s an nxn o matrix with I : INTRODUCTION 5 1 i f (i , j ) £ E(G) (.0 otherwise. A 1-1 mapping from a f i n i t e set onto i t s e l f i s c a l l e d a jgermutation. A - permutation <T on n elements can be represented by an nxn permutation matrix P =(?,•} with o 1 i f P(i)=j 0 otherwise. We w i l l r e f e r to a permutation <r and i t s corresponding permutation matrix P^ - i n d i f f e r e n t l y as a permutation. If we l a b e l the vertices of two graphs G and H with elements of the same set {1,2,...,n} then G and H are isomorphic i f and only i f there e x i s t s a permutation <r on the set {1,2,...,»} that maps adjacent nodes x-,x. of G onto adjacent o nodes y ^ ,ySc^ of H. & n automorphism of a graph G i s an isomorphism of G onto i t s e l f . The automorphisms of G form a group, P{G), known as the S.rou£ of G. The automorphism Bartitioning, of G i s the c o l l e c t i o n of or b i t s of i t s automorphism group. I f the only automorphism of a graph G i s the i d e n t i t y , G i s an i d e n t i t y 2£apjhi. Two points u and v of a graph G are sim i l a r i f ^ G^r^G) such that v=GT(u), A graph i s t r a n s i t i v e (or fioint simmetric) i f every two points are s i m i l a r , that i s , i f i t s group acts t r a n s i t i v e l y on i t s point set. I I : GRAPH ISOMORPHISM 6 2.1 IntroSuetion Graphs occur in a variety of applications (chemistry, e l e c t r i c a l engineering, computer science, etc.)* and there have been many attempts to find decent algorithms for detecting graph isomorphism. Cook [ 6 ] has shown that no polynomial algorithm exists for the subgraph isomorphism problem, i . e . f o r determining whether a graph G i s isomorphic to a subgraph of a graph H. It i s s t i l l an open guestion whether a polynomial algorithm exists f o r the graph isomorphism problem. However, e f f i c i e n t algorithms have been found for certa i n types of graphs, and Corneil's algorithm i s e f f i c i e n t for a l l but a r e s t r i c t e d class of graphs. There exists of course a simple solution to the problem, namely, i f G and H are labeled graphs on n nodes, simply rel a b e l the nodes of G and check for equality with H. Since the number of possible relabelings of G i s n!, the number of permutations on n elements, one might have to repeat t h i s step n! times. This w i l l c e r t a i n l y be the case i f the graphs are not isomorphic and may be the case even i f they are isomorphic, for example i f G — H i s an i d e n t i t y graph. Thus t h i s method i s c l e a r l y impractical. 2.2 Heuristic methods The -brute force approach described above t r i e s to match a node i n the f i r s t graph to each of the nodes of the second I I : GRAPH ISOMORPHISM 7 graph. One can try i n various ways to l i m i t the set of nodes in H that a node of G can be mapped into, since i f G i s isomorphic to H, the nodes of G which have some property must map onto nodes of H with the same property. Sussenguth [28] and Unger £31 ] have proposed algorithms to do t h i s . Sussenguth proposes an algorithm for matching chemical structures, that i s , graphs which have d i f f e r e n t kinds of vertices and edges, representing respectively the d i f f e r e n t atoms and the bonds between them. The problem i s usually simpler i n t h i s case than i t would be for unlabeled graphs, since more information i s present. The algorithm i s as follows: pairs of corresponding sets of nodes from the two graphs are generated by using the following functions on the nodes: node value (i.e.,atom type), edge value (type of bond), vertex degree, least number of edges on a cycle from a vertex to i t s e l f ( i f no cycle exists).The sets obtained are checked for agreement of c a r d i n a l i t y , since the subsets of nodes having some property must have the same number of elements for the two graphs, i f these are isomorphic. Since nodes can be matched only i f they have the same value for a l l the functions considered, i f function f y i e l d s the set S c V (G), and corresponding to i t the set S*CV(H), and function f, y i e l d s the sets Sd and S*, then the nodes in the intersection of S c V ( G ) and S^ c V (G) must correspond to the nodes i n the intersection of S* and S*, and the nodes not i n the i n t e r s e c t i o n of the sets must also correspond. Therefore the sets obtained by the functions defined on the nodes are intersected and refined as I I : GRAPH ISOMORPHISM 8 much as possible. If the c a r d i n a l i t y r e s t r i c t i o n i s met, we obtain a p a r t i t i o n of the nodes of G into subsets which are mapped onto subsets of nodes of H. To create new sets, one next looks at the set of nodes adjacent to the nodes of some set S , and matches It to the set of nodes adjacent to the elements of the corresponding set S*. The sets generated are used to r e f i n e the p a r t i t i o n obtained before. When no more refinements are possible, but some set has more than one element, an a r b i t r a r y assignment for some node in the set i s made, and again sets are generated by looking at the adjacent nodes, and so on. I f a contradiction i s reached, the program backtracks and picks another node, i f possible, u n t i l either an isomorphism i s found, or no choices are l e f t , i n which case the graphs are not isomorphic. The program can be s l i g h t l y modified to check for subgraph isomorphism, by changing the requirement that sets be mapped to sets of equal c a r d i n a l i t y to the requirement that they be mapped to sets of equal or greater c a r d i n a l i t y . The algorithm was tested over a thousand times with graphs of 50 points, The time to compute a complete isomorphism averaged about 7 sec. For graphs of about 30 points, t h i s time averaged about 2 sec. Determining that two graphs were not isomorphic was, i n 8515 of the cases, less than 0.5 msec. No backtracking was ever required. Since the functions used to generate sets are very simple, i t i s clear that t h i s i s due large l y to the greater amount of information present i n chemical structures, as opposed to graphs, I I : GRAPH ISOMORPHISM 9 linger [31] proposed a much more sophisticated algorithm to test directed graphs for isomorphism which uses the same approach. I n i t i a l l y , the nodes of the graphs are paired without d i s t i n c t i o n - any node of G can be mapped to any node of H. The algorithm then evaluates some function on the nodes, and uses the r e s u l t i n g p a r t i t i o n of the nodes to refine the p a r t i t i o n previously obtained, or to reach a contradiction. The nodal functions used are the following: in-degree, out-degree, number of nodes that can be reached from node I along a path of length k, k=1,...,n, a function which i s equal to 1 i f node i i s on a cycle of length k, k=1,...,n, and variations of these. The p a r t i t i o n i s then refined by computing a function on the nodes of a set that takes in t o account to which sets of the p a r t i t i o n the nodes adjacent to them belong, u n t i l no further refinement i s obtained. If the nodes are partitioned into small enough sets, a l l possible matchings are t r i e d i n order and the graphs compared d i r e c t l y for isomorphism. If the number of possible choices i s too large, an arbi t r a r y assignment of a node i s made, and the consequences of the assignment explored. I f a contradiction i s reached, the program backtracks, u n t i l no choices are l e f t , i n which case the graphs are not isomorphic, or u n t i l an isomorphism i s found. The program was reasonably fast i n most cases. I t ran for 12 minutes without producing a solution when comparing a pair of 16 nodes graphs of the "worst" type. This program uses a large number of functions to l i m i t the number of possible matchings, I I : 'GRAPH ISOMORPHISM 10 as w e l l a s t e c h n i q u e s now p r o p o s e d by w o r k e r s i n A r t i f i c i a l I n t e l l i g e n c e t o e l i m i n a t e u n n e c e s s a r y b a c k t r a c k i n g (Mackworth,[ 21 ]) , so t h a t i t i s u n l i k e l y t h a t i t c a n be g r e a t l y i m p r o v e d . 2.3 C o r n e l l ' s a l g o r i t h m C o r n e l l [ 7 , 8 ] has p r o p o s e d an a l g o r i t h m f o r d e t e c t i n g g r a p h i s o m o r p h i s m which i s e f f i c i e n t ( o f t h e o r d e r o f n 5 a t worst) f o r a l l g r a p h s which do n o t c o n t a i n a t r a n s i t i v e 2 - s t r o n g l y r e g u l a r s u b g r a p h . A g r a p h i s 2 - s t r o n g l y r e g u l a r i f any two a d j a c e n t v e r t i c e s a r e b o t h a d j a c e n t t o a c o n s t a n t number o f v e r t i c e s , and b o t h non a d j a c e n t t o a c o n s t a n t number o f v e r t i c e s , and s i m i l a r l y f o r any two non a d j a c e n t v e r t i c e s . The a l g o r i t h m d e r i v e s , f o r e a c h o f t h e g r a p h s , two u n i q u e g r a p h s , t h e r e p r e s e n t a t i v e g r a p h , which i s homomorphic t o t h e g i v e n g r a p h , and t h e r e o r d e r e d g r a p h , which i s c o n s t r u c t e d f r o m t h e r e p r e s e n t a t i v e g r aph and i s i s o m o r p h i c t o t h e g i v e n g r a p h . I t i s c o n j e c t u r e d t h a t t h e r e p r e s e n t a t i v e g r a p h s e x h i b i t t h e a u t o m o r p h i s m p a r t i t i o n i n g o f t h e g i v e n g r a p h s . F o r two g r a p h s t o be i s o m o r p h i c , t h e i r r e p r e s e n t a t i v e g r a p h s must be i d e n t i c a l , s i n c e t h e y a r e u n i g u e l y l a b e l e d . I f t h e g r a p h s a r e t r e e s , t h e c o n v e r s e i s a l s o t r u e . I t f o l l o w s f r o m t h e c o n j e c t u r e t h a t i n g e n e r a l i f t h e r e p r e s e n t a t i v e g r a p h s a r e i d e n t i c a l , t h e g i v e n g r a p h s a r e i s o m o r p h i c . The r e o r d e r e d g r a p h s g i v e a s u f f i c i e n t c o n d i t i o n f o r i s o m o r p h i s m : i f t h e r e o r d e r e d g r a p h s a r e i d e n t i c a l , t h e g i v e n g r a p h s a r e i s o m o r p h i c . I I : GRAPH ISOMORPHISM 11 The procedure derives the representative and the reordered graph f o r each of the given graphs. If the representative graphs are not i d e n t i c a l , the graphs are not isomorphic. If the reordered graphs are i d e n t i c a l , the graphs are isomorphic and an isomorphism i s exhibited. If the representative graphs are i d e n t i c a l , but the reordered graphs are d i f f e r e n t , a counterexample to the conjecture has been found, and some other method has to be used to determine whether the graphs are isomorphic. The pa r t i t i o n i n g algorithm used to obtain the representative and the reordered graphs depends d i r e c t l y on the connectivity structure of the graphs; and i t i s i n t u i t i v e l y c l e a r that graphs which are 2-strongly regular graphs, and thus have a high degree of symmetry w i l l present a problem. A modification of the algorithm w i l l work for graphs which contain a t r a n s i t i v e h-strongly regular subgraph, h<n, but the computation i s then of the order of n^K Except for th i s s p e c i a l case, the algorithm i s the most e f f i c i e n t general purpose graph isomorphism algorithm known. In p a r t i c u l a r , for isomorphic random graphs, the processing time was of the order of ri1- , and i t seems to be e f f i c i e n t i n general for graphs encountered i n applications. 2.4 Algorithms f o r sp e c i a l graphs Planar graphs are a class of graphs for which several e f f i c i e n t isomorphism algorithms have been developed. Trees are I I : GRAPH ISOMORPHISM 12 a s p e c i a l case of planar graphs for which a p a r t i c u l a r l y simple algorithm ex i s t s , since trees can be put into a canonical form. A few additional d e f i n i t i o n s are needed at this point. A rooted tree Is one with a distinguished point c a l l e d i t s root. A graph i s k-tuply connected i f i t contains at l e a s t k+1 nodes and i t i s not transformed i n f o an unconnected graph by the deletion of less than k nodes. An algorithm f o r ordering the edges of a tree which has been used by various authors (Edmonds [10], Busacker and Saaty [3], Scoins [27] and others) i s described i n d e t a i l by Hopcroft and Tarjan [18]. The algorithm i s as follows: f i r s t a unique root i s found. This i s done by eliminating a l l vertices of degree one from the tree, and repeating t h i s step u n t i l either a single vertex (the root) i s l e f t , or a single edge i s l e f t . In the l a t t e r case, a vertex i s added i n the middle of the edge to create a unique root. Then the vertices at each l e v e l are ordered, s t a r t i n g with those farthest away from the root. The leaves at the deepest l e v e l are f i r s t assigned a value (the same value f o r a l l of them). Once the vertices at l e v e l k have been assigned values, the vertices at l e v e l k-1 are ordered lexicographically on the l i s t of values of their sons. Thus trees can be put into a canonical form, and therefore to compare two trees for isomorphism i t i s s u f f i c i e n t to compare their canonical forms for i d e n t i t y . This algorithm i s l i n e a r i n the number of nodes i n the trees. I I : GRAPH ISOMORPHISM 13 Whitney [34] showed that planar t r i p l y connected graphs have an embedding in the plane which i s unigue up to p a r i t y , and that planar t r i p l y connected graphs are isomorphic i f and only i f cycles can be mapped to cycles. Weinberg [32,33] was the f i r s t to propose an e f f i c i e n t algorithm for isomorphism of planar t r i p l y connected graphs. The algorithm i s based on the t r a v e r s a l of an Euler path, that i s , a path which traverses every edge exactly once. For each edge of the graph, the graph i s traversed s t a r t i n g with t h i s edge, i n the clockwise and counter clockwise d i r e c t i o n , and a vector code i s generated for the t r a v e r s a l . I f the graph has b edges, 2b vectors of length 2b+1 are obtained. The same process i s repeated with the mirror image embedding of the graph. Thus a 4b x (2b+1) code matrix i s generated. The graphs are isomorphic i f and only i f t h e i r code matrices are egual. Since the number of edges in a planar graph s a t i s f i e s b < 3n-6, where n i s the number of v e r t i c e s , i t i s clear that the algorithm i s polynomial i n the number of ve r t i c e s , and i t i s in fact of order Hopcroft and Tarjan [ 17-] improved on t h i s result when they presented an algorithm for isomorphism of planar t r i p l y connected graphs whose complexity i s of order n log n. A planar embedding i s constructed for the f i r s t graph, and the two possible embeddings are constructed for the second graph. For each edge e, treated as two directed edges, a number I I : GRAPH ISOMORPHISM X (e) i s computed so that \(e,) = ^ (e J i f f the number of edges on the face to the right (left) of e( i s equal to the number of edges on the face to the r i g h t x (left) of e l f and the degrees of the heads (tai l s ) of e, and e A are the same. Edges ex and e^ are said to be distinguishable i f there exist edges es , e^, a primary path p( from e, to e 3 and a corresponding primary path p z from e L to e + such that \(e j)#\(e^). Otherwise, e, and e, are said to be ind i s t i g u i s h a b l e . A primary path i s one in which the follower of each edge i s the edge to i t s immediate right or immediate l e f t (in the plane embedding), It i s shown that there exists an isomorphism of G onto H mapping ex onto e^ i f f e x and e t are indistinguishable. To fin d such an isomorphism, therefore, the edges of the graphs are partitioned so that edges are i n the same set i f f they are indistinguishable. The par t i t i o n i n g algorithm i s of the order of n log n, and the embeddings i n the plane can be constructed in time proportional to the number of edges i n the graph, therefore l i n e a r i n the number of nodes of the graph, so that the algorithm i s of the order of n log n. This algorithm was incorporated by Hopcroft and Tarjan [18] into an algorithm to f i n d an isomorphism between any two planar graphs. In t h i s algorithm, the graphs are divided into connected components, which are divided into biconnected components, and further sub-divided i n t o t r i p l y connected components. The connectivity structure of the graph i s represented by a tree. The t r i p l y connected components are I I : GRAPH ISOMORPHISM 15 compared for isomorphism using the algorithm described above, and the connectivity tree reduced, with an isomorphism code replacing the t r i p l y connected components. Other substructures of the tree are s i m i l a r l y reduced, u n t i l each connected component i s reduced to a single vertex with an attached isomorphism code. The codes for the components of each graph are then sorted and compared for equality. The graphs are isomorphic i f f the respective codes are equal. Here again the main part of the algorithm i s pa r t i t i o n i n g the t r i p l y connected components into equivalence classes, which requires time of the order of v loq v, where v i s the t o t a l number of vertices i n the o r i g i n a l graphs, and the algorithm i s therefore of order v log v. Hopcroft and Wong [19] have since devised an algorithm f o r the isomorphism of planar graphs which i s l i n e a r i n the number of vertices of the graphs. From the previous discussion, i t i s clear that i t i s enough to r e s t r i c t attention to t r i p l y connected planar graphs. Given a fixed embedding of such a graph, the algorithm associates labels with vertices and edges, and reduces the graph by replacing labeled subgraphs by other labeled subgraphs whose labels encode t h e i r o r i g i n , u n t i l no further reductions are possible. One i s then l e f t with one of the f i v e regular polyhedral graphs or with a t r i v i a l graph of one vertex, and to test for isomorphism i t i s s u f f i c i e n t to check for equality of these reduced graphs. The algorithm (which, i n the paper mentioned, i s not proved to be correct) i s I I : GRAPH ISOMORPHISM 16 shown to have a running time l i n e a r i n the number of v e r t i c e s , but the constant factor i s large, so that for small values of n t h i s method i s not superior to the previous one. It i s hoped that further work i n the same di r e c t i o n w i l l y i e l d a more e f f i c i e n t l i n e a r algorithm for planar graphs. 2.5 Using the Spectrum of a Graph Another approach involves the use of algebraic properties of the adjacency matrix of a graph. At a meeting of the American Mathematical Society, Harary (as r e c a l l e d i n Harary, King, Mowshowitz and Read,[ 16 ]) hazarded the conjecture that a graph might be characterized by i t s spectrum, even though i t i s clear that c h a r a c t e r i s t i c polynomials do not i n general uniquely characterize matrices, since s i m i l a r matrices have the same polynomial. This i s however not the case, and the conjecture was refuted on the spot. Se next present examples of non -isomorphic cospectral graphs. C o l l a t z and Sinogowitz [5] give a l i s t of the c h a r a c t e r i s t i c polynomials of trees with 6,7 and 8 points, which contains the smallest example of cospectral trees (Fig 2.5.1). Harary et a l [16] give an example of a smallest pair of cospectral trees with i d e n t i c a l degree p a r t i t i o n i n g (Fig 2.5.2) as well as examples of smallest cospectral graphs and smallest cospectral connected graphs . I I : GRAPH ISOMORPHISM 17 • t ! Fig 2.5.2 i Mowshowitz [23] presents a method due to A.J.Hoffman for constructing, given any positive integer k, k non-isomorphic connected Lregular cospectral graphs, as well as a method for constructing i n f i n i t e l y many pairs of cospectral trees. Schwenk [26] has shown that, asymptotically, almost a l l trees have; cospectral mates. This behaviour becomes apparent only for trees with a f a i r l y large number of points, which i explains why i t could have been conjectured that graphs can be I i I I : GRAPH ISOMORPHISM 18 distinguished by t h e i r spectra. Schwenk further conjectures that almost every graph has a cospectral mate, even though the asymptotic structure of graphs i s very d i f f e r e n t from that of trees. Since the c h a r a c t e r i s t i c polynomial of a graph i s not s u f f i c i e n t to determine isomorphism. Turner [30] has considered generalized matrix functions that could be used. He found, however, that the adjacency matrices of two graphs have the same generalized c h a r a c t e r i s t i c polynomial i f and only i f the graphs have the same number of dissections of c e r t a i n types, and t h i s i s not an invariant of a graph. He exhibits a pair of non-isomorphic generalized cospectral trees on 12 points as well as a pair of non-isomorphic generalized cospectral connected graphs which are not trees. Mowshowitz {personal communication) has suggested using the additional information given by the eigenvectors of the graphs to determine isomorphism of cospectral graphs. An algorithm f o r detecting graph isomorphism i n t h i s manner i s given i n chapter 4 of t h i s thesis. A short description of the method follows. Let A be the adjacency matrix of a graph G, B the adjacency matrix of a graph H. Then (Chao,4) G and H are isomorphic i f f there exists a permutation matrix P such that p'rAP= B I I : GRAPH ISOMORPHISM 19 Let \,...,\\,. be the d i s t i n c t eigenvalues of A, yv an eigevector of B corresponding to X^. I f G and H are isomorphic, we have P'AP = B Byo = XcYc for i = 1,...,k (p" tAP)y ;= \y c A(Pyt) = \(Py.) Thus any eigenvector of A corresponding to X- i s a permutation of some eigenvector of B corresponding to X^ , t where the permutation s p e c i f i e s an isomorphism between the graphs. We next show that the converse i s also true. THEOREM 2.1 Let G, H be cospectral graphs with k d i s t i n c t eigenvalues. Let P be a permutation matrix such that every eigenvector x of G belonging to ^ ,i=1,...,k, i s the permutation by P of some eigenvector y of H belonging to ^ . Then P i s an isomorphism from G to H. Proof. Let D be the diagonal matrix with d = \ . Then B=QDQT , where Q=[ y t ,y^ , .. . ,y^ ], i . e . , column i of Q i s an eigenvector corresponding to X- . Si m i l a r l y , A=RDRT , where R=[ x ( , x^,. . . , xw ] Since x^Py.^VA, R=[ Py( ,Py^ ,... ,Py^ ]=PQ. Thus A=RDRT = PQD(PQ)X I I : GRAPH ISOMORPHISM 20 = P (QDQT) PT =PBPT that i s , P i s an ismorphism between G and H. The proposed algorithm uses t h i s r e l a t i o n i n the obvious manner: the eigenvectors of two cospectral graphs are compared in order to f i n d a permutation P, i f i t e x i s t s , s.t. each eigenvector of A, when permuted by P, i s an eigenvector of B. If no such matrix can be obtained, the graphs are not isomorphic. I l l : THE SPECTRUM OF GRAPHS 21 3.1 Introduction The set of a l l the eigenvalues of the adjacency matrix of a graph i s known as the spectrum of the graph. In t h i s chapter, we f i r s t review some of the research on the spectra of graphs. This deals mainly with the following problems: (i) how to f i n d the c h a r a c t e r i s t i c polynomial of a graph d i r e c t l y from the graph (ii ) finding classes of graphs which are characterized by their spectra and ( i i i ) using the spectra of graphs to solve combinatorial problems. We are mainly interested i n (I) and ( i i ) , and the relevant results are presented in the next section. We then review re s u l t s from matrix theory which apply to adjacency matrices of graphs, and numerical methods used to compute the eigenvalues and eigenvectors of a sguare symmetric matrix. 3.2 Research on the Spectrum of a Graph The e a r l i e s t work on t h i s subject i s that of Co l l a t z and Sinogowitz [5]. This paper contains a l i s t of the spectra of connected graphs of up to fi v e vertices, and of trees of up to eight vertices. It also includes the f i r s t published example of cospectral graphs. A geometric interpretation for the f i r s t few c o e f f i c i e n t s of the ch a r a c t e r i s t i c polynomial of G, 9 (x)= ( -1)^;* , i s given, as well as e x p l i c i t formulae for the eigenvalues of some special I l l - THE SPECTRUM OF GRAPHS 22 graphs, and t h e i r eigenvectors. Let G be the complete graph. Then <|) (X) = (n- 1 - A ) { - X - l ) ^ ; for \=n~1, the corresponding eigenvector i s x( = (1, ... ,1) ; for \=-1, i=2,..., n x^ i s arb i t r a r y as long as ^ x^=0. Let G be a path. Then V=2cosv>>, 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,<r) and i v +1^ + .., +i r -k. Let D be a digraph of order n. Then for 1v<k£n, the k-th I l l : THE SPECTRUM OF GRAPHS 23 c o e f f i c i e n t a^ of the c h a r a c t e r i s t i c polynomial of A (D) i s given by at=7[i?(-1) f 5 ({ i v , i 1 # ... ,i r } ), where the summation i s taken over a l l rank r p a r t i t i o n s { i , i ^ , i r }• (1^r^k) of k , and ao=1. In an undirected graph, i f for a given p a r t i t i o n ( i , i ^ , . . . , i r ) of k we l e t f1 i f 1<Ci <2 g ( i ) = ( 2 , i f i >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<Cn the k-th c o e f f i c i e n t a of the c h a r a c t e r i s t i c polynomial of A (G) i s given by a^= ^ [rT(-1)' f & ( ( i,»i,,...ii r}) where the summation extends over a l l rank r p a r t i t i o n s { i ) # i ,...,i r} (Kr^k) of k, and a o = 1. In p a r t i c u l a r , f or an undirected graph without loops, a0=1, a,=0 and a i s egual to the number of edges. 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 can also be computed using a recurrence formula, and an e x p l i c i t formula i s given for paths, trees homeomorphic to stars, and l i n e stars. A l i s t of a l l trees of up to 10 points with the c o e f f i c i e n t s of t h e i r c h a r a c t e r i s t i c polynomial i s given, which corrects some errors i n the l i s t given i n [5] . Harary, King, Mowshowitz and Read [16] give e x p l i c i t expressions for the c h a r a c t e r i s t i c polynomial of the n-cu.be Q I l l ; THE SPECTRUM OF GRAPHS 24 <b(Q (\-{n-2k))1*' and the complete t - p a r t i t e graph K (n , , n 1 # ., .n^) <^(K(n ,n l,.,.,n t)) = l ( 1 - r ) s ( (n l ,n i , . . . ,n)V >" 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 1<i<6, there exists j t *1$l\<6# s.t. = -yc(^, j. * j ^ f o r i#k. Thus i t i s possible to find a matching between x xand yt . This matching yields a p a r t i a l permutation from the nodes of G onto the nodes of H IV: THE EIGENVECTOR CONNECTION 35 P*: 1->2, 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 = <p*> = < 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 <r= j , . , s. e Sj. . Let Pt be a permutation r e f i n i n g P. then P ^ P , =*,--J;P i s also a refinement of P*, since only permutes elements of s o , for a l l I. Since P* i s a proper p a r t i a l permutation, we have P^ AP, = B P^ AP T = B («P, ) T A(«P T )= B /A<T=P, BP! =A f eT(G) . We next show how the group of a graph can be constructed i f a l l the maximal proper p a r t i a l permutations from i t to an isomorphic graph (or to I t s e l f ) are known. THEOREM 4.2.2. Let G, H be isomorphic graphs. Let P( *,...,P„* IV: THE EIGENVECTOR CONNECTION be a l l the maximal proper p a r t i a l permutations from G to H. Let < P * > 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 •* >, <re f (G) . If P , , P z are isomorphisms from G to H, then P,T AP, = P"X AP^, p xp; AP, Vl =A, therefore P, P,7 «- <p (G) . (i i ) Let x e f (G), Q an isomorphism from G to H. Then there exists an R s.t. xQ = R x = RQT. Since a l l isomorphisms are refinements of Po*'s (because of the maximality of the P j * ' s ) , we have Q = « , • • • <rxp. t E. =s,-JUPi whereat <P • *>,?;t <P^ *> X = RQT =Si-S~2- 6 < <P * >,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^* >,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 1<Pt*>j. Thus the t o t a l number of isomorphisms i s k|<PL*>|, The number of automorphisms i n <<P-*>,P;P^ >, i fi x e d , j=1,...,k i s also k|<P;*>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* =<j> , 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* (<J) • Order r i n { r J . E l s e , return R* = . IV: THE EIGENVECTOR CONNECTION 51 Step H. Set p=p\ (p f\ g) ,P* (p) =P* (p)\ (P* (p) n Q* (<3)) , order p i n {p.l.Set q=p\(qAP),Q*(g)=Q*(q)\ (P*(P)a Q*(g)) , order g i n [q J . Go to Step 2. AIG2II1SI Jfel : obtain the next permutation of r elements partitioned into k sets. The Algorithm i s i n the form of a recursive procedure, and we assume an algorithm for generating permutations on a set, next-permutation,(such as IPERM, written at the OBC Computing Center) i s given. Procedure next-perm-set (k) If k=1 then next-permutation of set 1 else I f a l l permutations on k-1 sets have been generated, reset sets 1, 2, ...,k-1 to their o r i g i n a l state, next-permutation of set k else next-perm-set (k-1). ALGORITHM J c l : obtain the next combination of k out of n elements partitioned into r sets, where a fixed number of elements, f ( j ) , i s taken from set j , for a l l j . An algorithm for generating combinations of i elements of a set, next-combination, (for example, algorithm 382 of the CACM) i s assumed given. Procedure next-comb-set (k) If k=1 then next combination of f(1) elements of set 1 else IV: THE EIGENVECTOR CONNECTION 52 i f a l l combinations on k-1 sets have been generated, reset the combinations of f ( j ) elements of set j , j=1,...,k-1, to t h e i r o r i g i n a l state, next-combination of f(k) elements of set k. Else next-comb-set (k-1) . Let G and H be cospectral connected graphs on n points,with d i s t i n c t eigenvalues. Let X,. .. ^ b e t h e i r eigenvalues, ordered by increasing value. Let x ,...,xnbe the eigenvectors of G corresponding to^', y ,...,y be the eigenvectors of H corresponding to^,.../•«. ALGORITHM I: finding a l l isomorphisms between two cospectral graphs with a l l d i s t i n c t eigenvalues. The Algorithm compares x. with y c , i=1,...,n, s t a r t i n g with the eigenvectors corresponding to the smallest eigenvalue, to find a po s i t i v e and/or negative maximal p a r t i a l permutation that maps x ^ onto y^. The p a r t i a l permutation (s) obtained i s (are) intersected with those obtained by comparing X: to y , j < i . The Algorithm yields a l l the maximal proper p a r t i a l permutations from G to H. Step 3 deals with a special case, namely when x^ and y- have only two non zero components, and these have opposite signs and equal absolute value. In t h i s case we can obtain both a positive and a negative p a r t i a l permutation that map x • onto y; , but neither would be maximal. We therefore introduce a spe c i a l test (cf. Ex 4.1.3), so that the p a r t i a l IV: THE EIGENVECTOR CONNECTION 53 permutation we get i s indeed maximal. Step 1. Set i=1. Set m=1. Set P = (1,...,n) -> (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* = <j£ and R* = <j6 , stop, no isomorphism i s possible. IV; THE EIGENVECTOR CONNECTION 54 Step 7. Set j = 1 Step 8 . If P ( J ) * A Q * # y$ , set P ( j ) * + = P ( j ) * ^ Q * i f P { j ) * ^ R* * <p, set P ( j ) * - = P ( j ) * n R*. Step 9 . Set 3 = 3 + 1 . I f j < m, go to Step 8 . Step 10. Arrange the d i s t i n c t non empty elements of P(j)*+, P(j)*~# j=1,...,m into a new l i s t of possible p a r t i a l permutation, P (1) *, .. . ,P (s) *. Step 11 .Set m = s . If m = 0 , stop, no isomorphism i s possible. Step 12. Set i = i • 1.If i<n, go to Step 2. Else, the algorithm ends, y i e l d i n g a l l the maximal proper p a r t i a l permutations from G to H, P (1) *,... ,P (m) *. ALGORITHM I I : comparing two cospectral graphs for isomorphism, Let G and H be cospectral connected graphs on n points. Let^,.,.,\be t h e i r d i s t i n c t eigenvalues, ordered by increasing m u l t i p l i c i t y , and by increasing value for d i s t i n c t eigenvalues of egual m u l t i p l i c i t y . Let x ,...,x be the eigenvectors of G corresponding t o \ . . . , \ , IV: THE EIGENVECTOR CONNECTION 55 y , ...,y be the eigenvectors of H corresponding to^>,...,\. 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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Use of the spectrum in graph isomorphism
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Use of the spectrum in graph isomorphism Gelbart, Rachel 1976
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Use of the spectrum in graph isomorphism |
Creator |
Gelbart, Rachel |
Publisher | University of British Columbia |
Date Issued | 1976 |
Description | The following is a study of the use of the eigenvalues and eigenvectors of the adjacency matrices of graphs to determine graph isomorphism. Two randomly chosen graphs will in general have different eigenvalues, and comparing the eigenvalues provides a first filter when checking for isomorphism. If the graphs are cospectral, we propose an algorithm that compares their eigenvectors in order to find an isomorphism between them, if any exists. The algorithm involves backtracking, and it is therefore difficult to evaluate its performance. It was fast for all pairs of graphs we compared, except one. For graphs whose eigenvalues are all simple we present an efficient algorithm to generate the group of a graph. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-02-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051789 |
URI | http://hdl.handle.net/2429/20065 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1976_A6_7 G44.pdf [ 4.34MB ]
- Metadata
- JSON: 831-1.0051789.json
- JSON-LD: 831-1.0051789-ld.json
- RDF/XML (Pretty): 831-1.0051789-rdf.xml
- RDF/JSON: 831-1.0051789-rdf.json
- Turtle: 831-1.0051789-turtle.txt
- N-Triples: 831-1.0051789-rdf-ntriples.txt
- Original Record: 831-1.0051789-source.json
- Full Text
- 831-1.0051789-fulltext.txt
- Citation
- 831-1.0051789.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051789/manifest