UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the minimal polynomial and authomorpism group of a graph Ng, Fat-Kwong Louis 1978

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1978_A6_7 N49.pdf [ 6.13MB ]
Metadata
JSON: 831-1.0094269.json
JSON-LD: 831-1.0094269-ld.json
RDF/XML (Pretty): 831-1.0094269-rdf.xml
RDF/JSON: 831-1.0094269-rdf.json
Turtle: 831-1.0094269-turtle.txt
N-Triples: 831-1.0094269-rdf-ntriples.txt
Original Record: 831-1.0094269-source.json
Full Text
831-1.0094269-fulltext.txt
Citation
831-1.0094269.ris

Full Text

ON THE MINIMAL POLYNOMIAL AND AUTOMORPHISM GROUP OF A GRAPH by FAT—KWONG LOUIS ^ NG B.A., U n i v e r s i t y o f Hong Kong, 1975 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES (Department of Mathematics and I n s t i t u t e of Applied Mathematics and S t a t i s t i c s ) We accept t h i s t h e s i s as conforming to the r e g u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1978 © Fat-Kwong L o u i s Ng, 1978 In presenting th i s thesis in pa r t i a l fu l f i lment of the requirements for an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree that the L ibrary sha l l make it f ree ly ava i l ab le for reference and study. I further agree that permission for extensive copying of th is thesis for scho lar ly purposes may be granted by the Head of my Department or by his representat ives. It is understood that copying or pub l i ca t ion of th is thes is for f inanc ia l gain sha l l not be allowed without my writ ten pe rm i ss ion . Department of Mathematics  The Univers i ty of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date A P r i l 28, 1978. i i A BSTJ ACT T h i s t h e s i s d i s c u s s e s t h e use o f 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 and m i n i m a l p o l y n o m i a l o f t h e a d j a c e n c y m a t r i x o f a g r a p h t o c h a r a c t e r i z e i t s a u t o m o r p h i s m g r o u p . We f i r s t c o n s i d e r t h e r e d u c i b i l i t y o f t h e m i n i m a l p o l y n o m i a l o f a g r a p h and s e e how t h i s r e f l e c t s t h e p r o p e r t i e s o f t h e g r a p h a n d i t s a u t o m o r p h i s m g r o u p . Then we s t u d y t h e r e l a t i o n s h i p b e t w e e n t h e number o f o r b i t s o f a s u b g r o u p o f t h e a u t o m o r p h i s m g r o u p o f a g r a p h and t h e f a c t o r i z a t i o n o f i t s c h a r a c t e r i s t i c p o l y n o m i a l . F i n a l l y we p r e s e n t an a l g o r i t h m t o d e t e r m i n e 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 a g r a p h u s i n g i t s c h a r a c t e r i s t i c p o l y n o m i a l . M o s t o f t h e r e s u l t s can a l s o b e e x t e n d e d t o d i r e c t e d g r a p h s a n d t o g r a p h s w i t h p a r a l l e l e d g e s and l o o p s . . . i i i TABLE OF CONTESTS I . INTRODUCTION 1 1.1 B a s i c D e f i n i t i o n s and Notations ... 1 1.2 Basic P r o p e r t i e s of the Automorphism Group ......... 8 1 • 3 M o Vet tx on •••••*••• •••»•••**•••••••••••*•••••«•«•••;' 12 1.4 Statement of Problems ..............................14 1.5 L i t e r a t u r e Review 14 I I . MINIMAL POLYNOMIAL OF THE ADJACENCY MATRIX ........... 21 2.1 I r r e d u c i b l e Minimal Polynomial ..................... 22 2.2 Reducible Minimal Polynomial 27 I I I . ADJACENCY MATRIX AND AUTOMORPHISM GROUP 45 3.1 Spectrum of a Graph . 45 3.2 C h a r a c t e r i s t i c Polynomial and Automorphism Group of a Graph ... 56 3.3 Graphs with L a b e l s ................ ........ ..... ..... . 69 IV. EXTENSIONS AND APPLICATIONS .......................... 73 4. 1 Digraphs .........-................................ ,73 4.2 Non-simple Graphs ....77 4.3 The Graph Isomorphism Problem ...................... 78 4.4 A l g o r i t h m i c C o n s i d e r a t i o n s ........................ . 79 m5 Conelusi on • • * • • • • • • • • « • * * • • • * t •••• •••** ••••« • • * 85 B i b l i o g r a p h y . 87 Appendix ................ . 92 i v LIST OF FIGOSES FIGURE PAGE 1.1: A P a i r o f C o s p e c t r a l G r a p h s 20 2.1: A T r e e o f D i a m e t e r 3 ................................. 37 2.2: S u b d i v i s i o n G r a p h o f K , 4 40 2.3: An I n t e g r a l C o m p o s i t e G r a p h .......................... 42 2.4: Two More I n t e g r a l G r a p h s 42 3.1: G r a p h s w i t h I n d e x 2 47 3.2: A G r a p h w i t h Symmetry ................................ 55 3.3: K, 4 and A s s o c i a t e d O r b i t — d i g r a p h o f <(25) , (34) > .... 59 3.4: The P a t h on F i v e V e r t i c e s ............................ 62 4.1: An I d e n t i t y D i g r a p h W i t h I r r e d u c i b l 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 and I t s C o n v e r s e 76 ACKNOWLEDGMENT I would l i k e t o thank Dr. Abbe Pfowshowitz f o r suggesting 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 t o thank Dr. R. A. Restrepo f o r h i s help throughout the p r e p a r a t i o n o f the t h e s i s . 1 I . INTRODUCTION In t h i s t h e s i s we w i l l examine the r e l a t i o n s h i p between the automorphism group of a graph G and the minimal and c h a r a c t e r i s t i c polynomials of G. In Chapter I we w i l l present d e f i n i t i o n s and r e s u l t s t h a t are r e l a t e d to the problems t o be s t u d i e d throughout t h i s t h e s i s . In Chapter I I , we w i l l c o n s i d e r the problem of using the minimal polynomial of the adjacency matrix to c h a r a c t e r i z e the graph and i t s automorphism group. Chapter I I I i s devoted to examining the s t r u c t u r e of a graph and i t s automorphism group i n terms of v a r i o u s p r o p e r t i e s of the adjacency matrix. Chapter IV deal s with e x t e n s i o n s and a p p l i c a t i o n s o f r e s u l t s obtained i n the p r e v i o u s c h a p t e r s . A l g o r i t h m i c c o n s i d e r a t i o n s w i l l a l s o be i n c l u d e d . 1.1 Basic,,, D e f i n i t i o n s and Notations Some b a s i c graph t h e o r e t i c concepts w i l l be given i n t h i s s e c t i o n . Notation i n t r o d u c e d i n the d e f i n i t i o n s w i l l be used c o n s i s t e n t l y throughout t h i s t h e s i s . D e f i n i t i o n 1.1 ft grajah G of order n i s an ordered p a i r G = (V (G) f E (G)) c o n s i s t i n g of a nonempty f i n i t e s e t V(G), whose elements are c a l l e d v e r t i c e s ( p o i n t s ) , and a s e t E (G) , whose elements are c a l l e d edjges, such t h a t each e € E(G) i s i d e n t i f i e d with an unordered p a i r (u, v) of 2 d i s t i n c t v e r t i c e s u, v t V (G) . f e say t h a t the edge e•= (u, v) j o i n s the v e r t i c e s u and v. V{G) w i l l be c a l l e d the v e r t e x s e t and E (G) the edge-; s e t , The number of elements |V(G)J i n V(G) w i l l be denoted by n. In g e n e r a l , we w i l l use v, , v a , . ,. , vOT to represent the n v e r t i c e s i n V(G); sometimes only the s u b s c r i p t s w i l l be used when no c o n f u s i o n w i l l a r i s e . I f an ordered p a i r (u, v) i s used to i d e n t i f y an edge e e E(G) , then G i s c a l l e d a di<JE§B!j and e = (u, v) a l i n e {or arc) from u t o v. PjeJ! i n i t i o Si_ia.2 The term graph i s sometimes used i n a more g e n e r a l sense, i . e . " l o o p s " and " p a r a l l e l edges" are allowed. More p r e c i s e l y a g e n e r a l graph i s a t r i p l e G = (V (G) , E(G), Y )^ where V{G) i s a nonempty s e t of v e r t i c e s , E (G) ( d i s j o i n t from V(G)) i s a nonempty s e t of edggs, and I 5 i s an i n c i d e n c e . f u n c t i o n t h a t a s s o c i a t e s with each edge of G an unordered p a i r of v e r t i c e s of G. An edge e = (u, v) i s c a l l e d a loop i f u = v. Two edges e, and ez are s a i d t o be p a r a l l e l i f ) = ^ Q ( e 2 ) ' Thus a graph i n the sense of D e f i n i t i o n 1.1 i s a g e n e r a l graph with no l o o p s and no p a r a l l e l edges. He w i l l sometimes use the a d j e c t i v e "simple" t o d i s t i n g u i s h graphs from general graphs. 3 •Def i n i t i g n 1 . .3 Two v e r t i c e s u, v € V(G) are s a i d t o be adjacent, denoted by u adj v, i f (u, v) € E(G). The degree of a vertex v, denoted by deg v, i s d e f i n e d as the number of v e r t i c e s a d j a c e n t t o i t ; and a graph i s s a i d t o be It-regular (or r e g u l a r of_degree k) i f every vertex has degree k. From the adjacency r e l a t i o n we can d e f i n e the adjacency ^ f u n c t i o n 3 on V(G) x V (G) to [0, 1} as f o l l o w s : r1 i f u adj v, *-0 otherwise. D e f i n i t i o n 1. 4 For any u, w € V(G), a path of l e n g t h p from u to w i s a sequence o f d i s t i n c t v e r t i c e s v„, v, , ... , v p such t h a t v„ = u, Vp = w and vl_l adj v L f o r i = 1, 2, p. ft path from u to u w i l l be c a l l e d a c y c l e . D e f i n i t i o n 1.5 A graph G i s s a i d to be connected i f f o r any p a i r of v e r t i c e s u, v e 7(G) t h e r e e x i s t s a path from u to v. ,. D e f i n i t i o n 1.6 Let G be a graph with vertex s e t V (G) = {v, , v z , . .., v„}. Then the matrix A(G) = f a t i ] 4 where a L- = 9 ( v c , V;) i s c a l l e d the adjacency matrix of G. a « - - — D e f i n i t i o n 1.7 The c h a r a c t e r i s t i c ; (jn inimal|; golynofflial of a graph G with adjacency matrix A(G) i s the c h a r a c t e r i s t i c (minimal) polynomial of A(G), and w i l l be denoted by f (G) (p(G) f o r the minimal po l y n o m i a l ) . The c h a r a c t e r i s t i c r o o t s (or eigenvalues) of a graph are taken t o be the c h a r a c t e r i s t i c r o o t s of A (G). P e f ij5iii2IL_ i1 i -8 The index of a graph G, denoted by r = r { G ) , i s d e f i n e d t o be the l a r g e s t c h a r a c t e r i s t i c r o o t of G., D e f i n i t i o n 1.9 Two graphs G, = (V(G,), E(G,)) and G 2 = ( V ( G 2 ) , E{G 2)) are s a i d to be isomorphic, denoted by G, £ G 2, i f t h e r e e x i s t s a b i j e c t i o n f» c a l l e d an isomorphism, from V(G,) to V(G 2) such t h a t (u, , u z) 6 E (G, ) i f f {?>,), T(u 2)) E ( G 2 ) . Def inition_1 i_1.0 ( c f . . [ 16, p. 161 ]) & n automorphism of a graph G i s a permutation o f the vertex s e t V(G) which preserves adjacency. Thus an automorphism of a graph G i s an isomorphism of G onto i t s e l f . 5 We note that the s e t of a l l automorphisms of a graph G forms a group under the u s u a l o p e r a t i o n of permutation m u l t i p l i c a t i o n . T h i s group of permutations i s the automorphism group P(G) o f G and each subgroup of r<G) w i l l be c a l l e d a group.of automorphisms. ' D e f i n i t i o n 1. 1,1 A graph G, = ff{G,),- E(G,)) i s a subgraph of G = (V(G), E (G)) i f V(G,) C ¥(G) and E(G () C E (G) . G( i s an i n d u c e d s u b g r a p h i f e = <u, v) e E(G) such t h a t u, v 6 V{G,) i m p l i e s e 6 E(G,). For any subset S C V(G), the induced subgraph with vert e x s e t V(G)\S w i l l be denoted by G - S. When S i s the s i n g l e t o n set (s) the n o t a t i o n G - s w i l l be employed. D e f i n i t i o n 1.12 A subgraph G, of a graph G i s c a l l e d a- component of G i f i t i s a maximal connected subgraph of G. Def i n i t i o n1 . 1 3 Let G = (V(G) , E(G)) be a graph. Then i t s complement, denoted by G, i s the graph G = (V{G), 1(G)) where e = (u, v) e E(G) whenever u # v and e I E(G). 6 D e f i n i t i o n 1..TJJ The simple graph of order n i n which every two d i s t i n c t v e r t i c e s are adjacent i s c a l l e d the complete graph on n v e r t i c e s . I t w i l l be denoted by K„. I t s complement K„, i n which a l l v e r t i c e s are non-adjacent, i s c a l l e d t h e v o i d graph (or empty graphV on n v e r t i c e s . D e f i n i t i o n 1.15 A graph G i s b i p a r t i t e i f the v e r t i c e s of G can be p a r t i t o n e d i n t o two s e t s V, and V z such t h a t v, i s adjacent t o v 2 i m p l i e s fv, €•••¥,• and v a * vv ] or fv, c v a and v 2 e v, ]. t D e f i n i t i o n 1 9 16 A S i c l e C„ on n v e r t i c e s i s a connected, 2 - r e g u l a r graph. D e f i n i t i o n 1.17 ft s u b d i v i s i o n of an edge (u, v) r e f e r s to the replacement of an edge |u, v) by two edges (u, w), (v, w) where w i s a new vertex i n the graph. D g f i s i i i o n _ 1 J L 1 8 Two graphs G,, G 2 are s a i d t o be homeomorphic i f t h e r e e x i s t s Gj such t h a t G, and G 2 can be o b t a i n e d from G 3 by a sequence o f s u b d i v i s i o n s o f edges. 7 D e f i n i t i o n 1.19 The chromatic number 0({G) of a graph G i s d e f i n e d as the minimum number o f c o l o r s t h a t i s r e q u i r e d t o c o l o r the v e r t i c e s of G so t h a t no two adjacent v e r t i c e s have the same c o l o r . l?ff=S=£ion_1. 20 (See [ 2, p.421) A v e r t e x cut of a graph G i s a subset V* of V{G) such t h a t G - ?' i s disconnected, ft k - v e r t e x c u t i s a vertex cut of k elements. I f G has at l e a s t one p a i r of d i s t i n c t nonadjacent v e r t i c e s , the c o n n e c t i v i t y K(G) of G i s the minimum k f o r which G has a k-vertex c u t ; otherwise, we d e f i n e /C(G) to be |V(G)| - 1. The f o l l o w i n g n o t a t i o n w i l l a l s o be used c o n s i s t e n t l y throughout t h i s t h e s i s : (b, , b z , ... , by,) ' w i l l be used t o denote an n—vector with b, , bz, b„ as the c o o r d i n a t e s . < *  az ' • • • • » • < r»n> w i l l denote the group of permutations generated by the permutations e w i l l be used to denote the i d e n t i t y permutation and fe} the t r i v i a l permutation group c o n t a i n i n g o n l y the i d e n t i t y permutation. For any group H, |HJ w i l l be used t o denote the order of H. D„ w i l l be used t o denote the d i h e d r a l group on n 8 elements and S„ the symmetric group on n elements. For any matrix B, f(B) w i l l be used t o denote the c h a r a c t e r i s t i c p o l y nomial o f B and p(B) the minimal polynomial of B. I„ w i l l be used t o denote the i d e n t i t y matrix of order n. When the order i s c l e a r from the c o n t e x t , the s u b s c r i p t w i l l be omitted. 1.2 Basic., Proper t i e s ..of the^^utomgrphigm^gronp In t h i s s e c t i o n we d i s c u s s b a s i c p r o p e r t i e s of the automorphism group of a graph. / The f o l l o w i n g three well-known r e s u l t s are obvious from the r e l e v a n t d e f i n i t i o n s . Theprem_1.1 Let <r be a permutation on the v e r t i c e s of a graph G and Pg. i t s corresponding permutation matrix. Then <r i s an automorphism of G i f f er\ = AP^, where A = A <G). Theorem 1.2 rm = r e 5 ) . Theorem_J^3 where i s the symmetric group on n elements. 9 D e f i n i t i o n ; , 1.21 Two v e r t i c e s x r y € V(G) o f a graph G are s a i d t o be §JBl|ar f denoted by x ~ y, i f t h e r e e x i s t s at l e a s t one automorphism of G mapping x to y. D e f i n i t i o n _ - l i 2 2 The automprghism^Bartitjoning of a graph G i s a p a r t i t i o n i n g o f the v e r t i c e s of G such that x and y are i n the same c e l l i f and o n l y i f x ~ y. Hence the automorphism p a r t i t i o n i n g of G gives p r e c i s e l y the o r b i t s of D e f i n i t i o n 1..23 a f i x e d - p o i n t of a graph G i s a v e r t e x f i x e d by a l l the automorphisms of G. D e f i n i t i o n 1.24 A graph i s c a l l e d an i d e n t i t y . g r a p h i f no two d i s t i n c t v e r t i c e s x and y are s i m i l a r . D e f i n i t i o n 1.25 A graph i s point—symmetric (or t r a n s i t i v e on the v e r t i c e s ) i f every two v e r t i c e s x and y are s i m i l a r . Thus f o r a point-symmetric graph G the automorphism p a r t i t i o n i n g i s V (G) . S i m i l a r l y we say t h a t a graph G i s iiie=§y.|imetric (or transitiye_pn ;.the ;-e ;dges)' i f . f o r every 10 p a i r of edges p and g, t h e r e e x i s t s at l e a s t one automorphism o f G mapping the endpoints of p t o the endpoints of g., fhegrem_1.U I f u, v are two s i m i l a r v e r t i c e s of a graph G, then G - u S G - v. We w i l l now c o n s i d e r the f o l l o w i n g o p e r a t i o n s on graphs and groups (see [16, p. 21 and p,163])t L e t G, and G 2 be graphs with d i s j o i n t vertex s e t s V, and Va and edge s e t s E, and E 2 , r e s p e c t i v e l y . The union G = G, 0 G 2 has vertex s e t 7 = V, U 7 2 and edge s e t E = E, 0 E 2., t The j o i n G, • G 2 c o n s i s t s o f G, U G 2 and a l l edges j o i n i n g 7, and 7 2. For any connected graph G, we w r i t e nG f o r the graph with n components each isomorphic with G. The product G, x G 2 has v e r t e x set 7 = 7, x V 2 . The edge s e t E of G, x G 2 i s d e f i n e d as f o l l o w s : Consider any two v e r t i c e s u = (u, , u 2) and v = (v, , v 2) i n 7 = 7, x V 2 . Then u and v are adjacent i n G, x G z whenever [ U i - v i and u 2 a d j v z 3 o r f Q a = v 2 a n < * u, a d j v, }. , Let H be a permutation group o f degree d a c t i n g on the set X = (x, , x 2 , x^}, and l e t K be another permutation group of degree e a c t i n g on the s e t Y - {y, , yz i . r y e l . The sum H + K i s a permutation 11 group which a c t s on the d i s j o i n t union X U Y and whose elements are a l l the ordered p a i r s of permutations vi i n H and p i n K, w r i t t e n * + ^ . Any element z of X 0 Y i s permuted by oi • f according to the r u l e : C oi z, z € x (<* * B) ( T ) = < ' V- pz, z « Y. The c a r t e s i a n product H x K of H and K i s a permutation group which a c t s on the s e t X x Y and whose permutations are a l l the ordered p a i r s , w r i t t e n o( x ^  , of permutations o( i n H and ^ i n K. The element (x, y) of X x Y i s permuted by oi x & as f o l l o w s : x p) <x, y) = {4x, |Sy). The wreath product Hf" K 1 of H around K a l s o a c t s on the set X x Y. For each « H and any seguence t f\ » •••» y^ .) •'°f permutations i n K, there i s a unique permutation i n H[K] w r i t t e n (e<; p,,. |32, ..., yS^ ) such t h a t f o r ( x t , y. ) i n X x Y: (4; p,, p2, . . . » f A ) (x L , y^) = (olxif |S- y^) .. The f o l l o w i n g are r e s u l t s concerning the r e l a t i o n s h i p between o p e r a t i o n s on graphs and o p e r a t i o n s on t h e i r automorphism groups. Theorem 1.5 [ 1 8 ] I f G, , G 2, ...» G w are p a i r w i s e non—isomorphic, connected graphs and n G = T ffli,Gk, then k=1 * 12 r<G> = i s w [F (G K > i . k=1 k C o r o l l a r y , 1 , 1 [16, p.166 3 no, + G 2 ) = r < G , ) • r ( G 2 > i f and o n l y i f no component of G , i s isomorphic with a component of G 2 . Theorem_1J!.6 ([ 32 3; f 1 6 , p. 166 3) r<G, x G 2 ) = n s , ) x r<c2) i f and only i f G , and G 4 are r e l a t i v e l y prime (see [16, p. 1663 or [323 f o r a d e f i n i t i o n of prime graphs). 1.3 M o t i v a t i o n From Theorem 1.1, we see th a t the c o n s t r u c t i o n of the automorphism group o f a graph G i s e q u i v a l e n t to f i n d i n g a l l permutation matrices t h a t commute with & ( G ) . The s o l u t i o n to t h i s problem o b v i o u s l y depends on the s t r u c t u r e of A (G ) . The minimal and c h a r a c t e r i s t i c polynomials of A ' (G) r e f l e c t , t o some exten t , p r o p e r t i e s of A ( G ) . Hence we expect t o o b t a i n some p r o p e r t i e s o f the automorphism group of a graph by s t u d y i n g the p r o p e r t i e s of i t s minimal and c h a r a c t e r i s t i c polynomials. The problem of determining the automorphism group of a graph i s c l o s e l y r e l a t e d to the graph isomorphism problem. In f a c t , i t i s known t h a t the automorphism 13 p a r t i t i o n i n g problem i s a l g o r i t h m i c a l l y e g u i v a l e n t t o the graph isomorphism problem. That means, g i v e n an a l g o r i t h m t h a t can s o l v e the automorphism p a r t i t i o n i n g problem, we can use i t to s o l v e the graph isomorphism problem and v i c e v e r s a . Hore d e t a i l e d treatment o f t h i s c o n n e c t i o n w i l l be cons i d e r e d i n S e c t i o n 4.3. A p p l i c a t i o n s can be found i n r e t r i e v i n g i n f o r m a t i o n which i s s t o r e d g r a p h i c a l l y . Chemical compounds, f o r example, can be rep r e s e n t e d by graphs corresponding to t h e i r s t r u c t u r a l formulas, and we may d e s i r e t o i d e n t i f y a l l the chemical compounds t h a t have a given r a d i c a l or s u b s t r u c t u r e . T h i s problem i n v o l v e s f i n d i n g subgraphs of the graphs r e p r e s e n t i n g the chemical compounds which are isomorphic to a given graph. Sussenguthf39] d e s c r i b e s an a l g o r i t h m f o r matching chemical s t r u c t u r e s . The a l g o r i t h m uses v a r i o u s p r o p e r t i e s of the v e r t i c e s o f the two graphs t o p a r t i t i o n the vertex s e t s . In chemical s t r u c t u r e s , these p r o p e r t i e s i n c l u d e atom and bond types. A c t u a l l y these p r o p e r t i e s can be represented by means of l a b e l s on v e r t i c e s and weights on edges. Sussenguth*s a l g o r i t h m can a l s o be used to check whether a chemical compound co n t a i n s a c e r t a i n s u b s t r u c t u r e . He note t h a t the general problem of i d e n t i f y i n g i somorphic graphs i s c o n s i d e r a b l y more d i f f i c u l t than matching chemical s t r u c t u r e s . 1•^ Stateaent of _Problems The f o l l o w i n g two problems w i l l be s t u d i e d : (i) c h a r a c t e r i z a t i o n o f t h e automorphism group of a graph from p r o p e r t i e s of i t s adjacency matrix, ( i i ) c o n s t r u c t i o n of the automorphism groups of graphs whose adjacency matrices share some common p r o p e r t i e s . We s h a l l concern o u r s e l v e s mainly with f i n i t e simple graphs (as d e f i n e d i n S e c t i o n 1 . 1 ) . Various extensions w i l l a l s o be c o n s i d e r e d i n Chapter IV. L i t e r a t u r e m Review In t h i s s e c t i o n , we are going t o review b r i e f l y r e s u l t s t h a t are r e l a t e d t o the problems mentioned i n S e c t i o n 1.4. The problem : of the e x i s t e n c e of graphs with a given group was posed by Kttnigf21 ]. I n 1938 F r u c h t [ 1 1 ] proved t h a t f o r any f i n i t e group H t h e r e e x i s t i n f i n i t e l y many graphs with automorphism groups a b s t r a c t l y isomorphic to H. Later the same authorf10 1 extended t h i s r e s u l t t o connected r e g u l a r graphs of degree three. Then i n 1957, S a b i d u s s i f 3 3 ] g e n e r a l i z e d t h i s r e s u l t to graphs with c e r t a i n given p r o p e r t i e s . The f o l l o w i n g i s the main r e s u l t of S a b i d u s s i * s g e n e r a l i z a t i o n . 15 Theorem, 1. 7 Given a f i n i t e group H o f order > 1 and an i n t e g e r j , 1 < j < 4, th e r e e x i s t i n f i n i t e l y many non—homeomorphic connected f i x e d - p o i n t - f r e e graphs G such t h a t ( i ) the automorphism group of G i s isomorphic to H, and {ii} G has property P; , where the p r o p e r t i e s P- ( j = 1, 2, 3, 4) are as f o l l o w s : •T-J»e-- conneet'iV'±'ty-'0'f-G"-is'--k-,- *her«'--k--i»-an---"i»teger > 1. P 2 : The chromatic number o f G i s k, where k i s an i n t e g e r > 2. P 3: G i s r e g u l a r of degree k, where k i s an i n t e g e r > 3. : G i s spanned by a graph I homeomorphic to a given connected graph Y. The other problem i s to c o n s t r u c t the automorphism groups of c e r t a i n p a r t i c u l a r c l a s s e s of graphs. U s u a l l y the c o n s t r u c t i o n of the automorphism groups depends on the knowledge of the s t r u c t u r e of graphs i n t h a t c l a s s . Frucht, Graver and Watkins [12] c o n s i d e r e d the problem o f c h a r a c t e r i z i n g the automorphism groups o f the g e n e r a l i z e d Petersen graphs which are d e f i n e d as f o l l o w s : For i n t e g e r s n and k with 2 < 2k < n, the g e n e r a l i z e d Petersen graph G(n, k) has been de f i n e d t o have v e r t e x - s e t V(G(n, k)) = {u 0, a,, ..., u„_, , v., v, , ..,, v„_, J and edge set E(G(n, k)) c o n s i s t i n g of a l l edges o f the 16 form ( u L , u t + 1 ) , ( u t , v t ) , (v t , v i + | t ) , where i i s an i n t e g e r and a l l s u b s c r i p t s are t o be read modulo n. However c l a s s e s o f graphs with common a l g e b r a i c p r o p e r t i e s can a l s o be c o n s i d e r e d . Rowshowitz[24] d e s c r i b e s an a l g o r i t h m f o r the c o n s t r u c t i o n of the automorphism groups of graphs with non—derogatory adjacency matrices ( i . e . those with i d e n t i c a l minimal and c h a r a c t e r i s t i c p o l y n o m i a l s ) . I f G i s a graph of t h i s type with n v e r t i c e s then Mowshowitz*s a l g o r i t h m w i l l c o n s t r u c t t h e automorphism group T(G) i n at most 2 s t e p s * . The d i f f i c u l t y i n c o n s t r u c t i n g the automorphism group of a graph i n c r e a s e s r a p i d l y as the number of v e r t i c e s gets l a r g e r . Hence i t w i l l be d e s i r a b l e i f we can decompose the graph i n t o s m a l l e r component graphs and c o n s t r u c t the automorphism group of the graph from those of the component graphs, Harary and Palmer f 1 8 ] s t u d i e d the automorphism groups of product graphs i n r e l a t i o n t o the automorphism groups of the component graphs. Another approach i n c h a r a c t e r i z i n g the automorphism group of a graph i s to f i n d i t s automorphism p a r t i t i o n i n g . * [ p ] denotes as usual the g r e a t e s t i n t e g e r < p. 17 Weichseir40] considered a p a r t i t i o n P of the vertices of the graph G which i s related to i t s automorphism group. The p a r t i t i o n P i s c a l l e d a star p a r t i t i o n of G and i s defined as follows: £®flaiti2S_dt26 P i s a - s t a r - p a r t i t i o n • of G i f i t s a t i s f i e s the following: (i) I f A fe- P, then a l l elements of A are of the same degree. ( i i ) Let a « A € P and b fe B fe P with a adjacent to b. Then for each a* e A there i s b» fe B such that a* i s adjacent to b*. The following theorem i s given in [40]: Theorem, 1. 8 Let G be a graph whose only star p a r t i t i o n i s the t r i v i a l , p a r t i t i o n ( i ^ e . /the p a r t i t i o n whose elements are singleton sets). Then G i s an i d e n t i t y graph.. An algorithm ?forr finding a s t a r p a r t i t i o n i s also described i n £40]. It i s worthwhile to note that the automorphism p a r t i t i o n of a graph G i s a star p a r t i t i o n of G and the algorithm produces only the coarsest of a l l star p a r t i t i o n s . Also the algorithm does not y i e l d anything for a regular graph since in t h i s case the set of a l l vertices of the graph forms the coarsest star p a r t i t i o n . ,• 18 The route t h a t we are going t o take i s v i a the c h a r a c t e r i s t i c polynomial and minimal polynomial of the adjacency matrix o f the graph. The eig e n v a l u e s o f a graph are the r o o t s of the c h a r a c t e r i s t i c polynomial and the t o t a l i t y o f a l l e i g e n v a l u e s i s c a l l e d the spectrum of the graph. A l i s t of the eig e n v a l u e s and c h a r a c t e r i s t i c p o l y n o m i a l s o f connected graphs with not more than s i x v e r t i c e s i s g i v e n i n T a b l e s I and I I of the Appendix. The f o l l o w i n g theorems are r e s u l t s concerning the r e l a t i o n s between the eigenvalues of a graph and i t s automorphism group. fhgoggj^l^f f 3 6 ] I f the automorphism group of a connected graph G i s t r a n s i t i v e on the edges, then there i s but one p o s i t i v e simple eigenvalue of G and i t i s the l a r g e s t e i g e n v a l u e . I f G i s b i p a r t i t e then r(G) and -r(G) are the only two non-zero simple e i g e n v a l u e s of G. Theorem 1 ..10 [ 27 ] Let G be a graph of order n with adjacency matrix A = A (G) , and automorphism group P= Tt6) {regarded as a group of permutation m a t r i c e s ) . I f A has n d i s t i n c t e i g e n v a l u e s , then every P i n V has order two (which, of course, i m p l i e s t h a t T i s A b e l i a n ) . The f o l l o w i n g theorem i s an extension o f the previous 19 one. Theorem 1.1.1 f 3] Let G be a f i n i t e graph with n v e r t i c e s ( d i r e c t e d or u n d i r e c t e d , with or without l o o p s ) , A = A (G) be i t s adjacency matrix, and P<G) be i t s automorphism group. I f the e i g e n v a l u e s o f A ( i n the complex number f i e l d ) are d i s t i n c t , then T ( G ) i s A b e l i a n . I t i s w e l l known that the c h a r a c t e r i s t i c polynomial of a graph does not c h a r a c t e r i z e a graph completely. Graphs with the same c h a r a c t e r i s t i c polynomial are c a l l e d c o s p e c t r a l graphs. Some examples of c o s p e c t r a l graphs and digraphs are given by Harary, King, Mowshowitz and Read i n [17]. A l s o i t can be e a s i l y seen from the f o l l o w i n g example t h a t c o s p e c t r a l graphs do not n e c e s s a r i l y have isomorphic automorphism groups., 20 F i g u r e 1.1; ft P a i r o f _ C o s p e c t r a l Graphs HG,) = D 4 r<Gz) S s 4 c h a r a c t e r i s t i c polynomial o f G, = c h a r a c t e r i s t i c p o l y nomial o f Gz = X s - 4X3 = X3 (X - 2) (X 2) From the previous example we see t h a t u s i n g o n l y i n f o r m a t i o n from the c h a r a c t e r i s t i c polynomial of a graph does not enable us to determine the automorphism group. In the f o l l o w i n g chapters we a r e going to study how the p r o p e r t i e s of the minimal polynomial and c h a r a c t e r i s t i c polynomial of a graph r e f l e c t those of the automorphism group. 21 IT. MINIMAL POLYNOMIAL OF THE ADJACENCY MATRIX In t h i s c h a p t e r , we w i l l study the r e l a t i o n s h i p between the automorphism group and the minimal polynomial of a graph. We w i l l use f ( G ; x) and p(G; x) t o denote the c h a r a c t e r i s t i c polynomial and minimal polynomial of a graph G i n the indeterminate x. When the dependence on the indeterminate i s c l e a r from the context, we w i l l employ the u s u a l n o t a t i o n f(G) and p(G). The f o l l o w i n g theorem g i v e s a c h a r a c t e r i z a t i o n of the minimal polynomial o f any graph.. Theorea_2a.1 The minimal polynomial of any graph G i s a product of d i s t i n c t i r r e d u c i b l e polynomials over the i n t e g e r s , i . e . the m u l t i p l i c i t y o f any f a c t o r i n the e x p r e s s i o n f o r the minimal polynomial i s one. Proof Let A be the adjacency matrix of G. Since A i s symmetric the minimal polynomial o f A c o n s i s t s of d i s t i n c t i r r e d u c i b l e f a c t o r s over the r e a l number f i e l d . Hence i t i s a l s o a product o f d i s t i n c t i r r e d u c i b l e f a c t o r s over the i n t e g e r s . From the above theorem we see t h a t the minimal polynomial of a graph can be determined by the c h a r a c t e r i s t i c p o l y n o m i a l . For, i f we have computed the 22 c h a r a c t e r i s t i c p o l y nomial o f a graph and decomposed i t i n t o i r r e d u c i b l e f a c t o r s then the minimal polynomial i s simply the product of the d i s t i n c t i r r e d u c i b l e f a c t o r s . Hence c o s p e c t r a l graphs a l s o have t h e same minimal polynomial. The f o l l o w i n g theorem by Mowshowitz £24] g i v e s a s u f f i c i e n t c o n d i t i o n f o r a graph t o be an i d e n t i t y graph. Theorem_2jL2 I f the c h a r a c t e r i s t i c polynomial of a graph i s i r r e d u c i b l e over the i n t e g e r s , then the automorphism group of the graph i s t r i v i a l . In the next s e c t i o n , we s h a l l study graphs t h a t have i r r e d u c i b l e minimal polynomials. 2.] I p r e d u c i b l e _ M i n i m a l _ P o l y n o m i a l The adjacency matrix o f a graph c o n s i s t s of 0, 1 e n t r i e s and hence i s a non-negative matrix. Thus r e s u l t s on non-negative matrices can be a p p l i e d t o adjacency matrices of graphs. The f o l l o w i n g are concepts and r e s u l t s i n the theory of non^negative matrices that are r e l e v a n t i n t h i s s e c t i o n . 23 !^f^£ill£&£i2*Jr; ( c f . [81) ,-, An n x n matrix A (n > 2) i s s a i d t o be i r r e d u c i b l e i f no permutation matrix P e x i s t s such t h a t A(1 A ( 2 PAP-* = 0 A 2 2 J where A„ , A 2 2 are square m a t r i c e s . ; 2h®2£§S_2±.3 (Frobenius—Perron theorem [8]) Let A be an i r r e d u c i b l e non—negative matrix. Then A has a c h a r a c t e r i s t i c r o o t r > 0 such that (i) there i s a s s o c i a t e d to r a p o s i t i v e e i g e n v e c t o r x„; ( i i ) i f ©<. i s any c h a r a c t e r i s t i c r o o t o f A, JeC| < r ; f l i i ) r i n c r e a s e s when any element o f A i n c r e a s e s ; (iv) r i s a simple r o o t . Let p be the minimal polynomial o f a graph and assume p i s i r r e d u c i b l e of degree m. I f f i s the c h a r a c t e r i s t i c polynomial and has degree n, then mjn and f = p> where k = n/m. Theorem_2 iii I f G i s a graph with f and p d e s c r i b e d above as i t s c h a r a c t e r i s t i c and minimal p o l y n o m i a l s r e s p e c t i v e l y , then G i s the union of k c o s p e c t r a l connected i d e n t i t y graphs with c h a r a c t e r i s t i c and minimal polynomials = p. 24 Proof (By Frobenius-Perron Theorem) I f G i s connected, then the adjacency matrix A i s o b v i o u s l y i r r e d u c i b l e . T h e r e f o r e the maximal c h a r a c t e r i s t i c r o o t r of f i s simple; but every c h a r a c t e r i s t i c r o o t o f f i s of m u l t i p l i c i t y k. Hence G i s connected only i f k = 1. Let G, be a component of G. Then s i n c e f<G,)|f, we have f(G,) = p h f o r some h such t h a t 1 < h < k. Since G, i s connected, the maximal c h a r a c t e r i s t i c r o o t r, of f(G,) i s simple, so h = 1. T h e r e f o r e every component of G has c h a r a c t e r i s t i c polynomial p, which i m p l i e s t h a t the components of G are c o s p e c t r a l . By Theorem 2.2, i f p i s i r r e d u c i b l e the components are i d e n t i t y graphs. Since f i s the product c f the c h a r a c t e r i s t i c polynomials of the components, the number of components i s k. Before we study the automorphism groups of graphs with i r r e d u c i b l e minimal p o l y n o m i a l s , we s h a l l f i r s t prove the f o l l o w i n g simple lemma. Lemma,, 2.1 I f G, i s an i d e n t i t y graph and Gz i s isomorphic to G,, there i s o n l y one isomorphism from G, to G*. Proof Let <r, , <rz be two d i s t i n c t isomorphisms from G, t o 25 G 2 » 0~, # *2 i m p l i e s <rfl<r, # e where e i s the i d e n t i t y permutation. Take any (u, v) 6 V (G,) x V(G,) where V ( G , ) t V(G 2) denote the vert e x s e t s of G, and G 2 r e s p e c t i v e l y . L et E(G,), E{G a) denote the edge s e t s o f G, and G a r e s p e c t i v e l y . Then (u, v) € E(G,J--,-:!££ (<J7«, o^y) e E(Ga) i f f (ffi-i<r; u, erf* <r, v) t E (G, ) . So ff2_,cr, i s an automorphism of G, and <r-^cr, * e c o n t r a d i c t s the f a c t t h a t G, i s an i d e n t i t y graph. The lemma then f o l l o w s . Co r o l l a r y . _ 2 I J [ I f G, , G 2 , ..., G k are isomorphic i d e n t i t y graphs, then f{G) = S k, the symmetric group on k elements and tHG) 1 = k! where G = G, 0 G 2 0 ... U G k. Theorem 2...5 Let the minimal polynomial p of a graph G be i r r e d u c i b l e , and f = p k be the c h a r a c t e r i s t i c p o l y nomial of the graph 26 where k i s a p o s i t i v e i n t e g e r . Then* i=1 i ana IPCG) | = k, !k 2! ... k y! , f o r some k, , k 2 , k r such t h a t k = k | ^ k 2 •**..-, •+ k y • Proof By Theorem 2.4, G c o n t a i n s k components. Now l e t us c o l l e c t the k components i n t o groups of mutually isomorphic graphs and l e t us assume t h a t t h e r e are r such groups with k,, k 2, k r connected graphs i n each group. Consider the s e t of automorphisms t h a t f i x a l l v e r t i c e s except those of graphs i n the i - t h group. T h i s s e t i s isomorphic to S k . Therefore i r<G) = S. + S. + ... + S. and ir<G) i = k, !k 2! ... k K1 with k, +• k x • ... + kY- k. He note t h a t Theore 2.5 assumes t h a t there e x i s t a t l e a s t r c o s p e c t r a l connected i d e n t i t y graphs. When a l l the * See f 1 6 , p.1631 or S e c t i o n 1.2 f o r d e f i n i t i o n s of o p e r a t i o n s on permutation groups. 2 7 c o m p o n e n t s a r e i s o m o r p h i c , we h a v e r e q u a l t o 1. The f o l l o w i n g t h e o r e m s a r e p r o v e d i n [ 2 5 ] and [ 2 2 ] , Theorem 2,_6 [ 2 5 ] G i v e n any p o s i t i v e i n t e g e r k, t h e r e e x i s t s an i n t e g e r n s u c h t h a t t h e r e a r e a t l e a s t k n o n - i s o m o r p h i c c o n n e c t e d r e g u l a r g r a p h s w i t h n v e r t i c e s a l l h a v i n g t h e same c h a r a c t e r i s t i c p o l y n o m i a l . T h e o r e m _ 2 I 7 [ 2 2 ] F o r any p o s i t i v e i n t e g e r k t h e r e a r e k c o s p e c t r a l g r a p h s w i t h g i v e n a u t o m o r p h i s m g r o u p . Thus we a r e l e d t o c o n j e c t u r e t h a t t h e r e e x i s t n o n — i s o m o r p h i c , c o s p e c t r a l , c o n n e c t e d i d e n t i t y g r a p h s whose common c h a r a c t e r i s t i c p o l y n o m i a l i s i r r e d u c i b l e . 2 . 2 R e d u c i b l e , H i n i m a l P o l y n o m i a l S i n c e t h e d i a g o n a l e n t r i e s o f t h e a d j a c e n c y m a t r i x o f a g r a p h a r e a l w a y s e q u a l t o z e r o , we s e e i m m e d i a t e l y t h a t i f t h e m i n i m a l p o l y n o m i a l o f a g r a p h i s l i n e a r t h e n i t must be t h e raonic p o l y n o m i a l x and t h i s i s t r u e i f and o n l y i f t h e g r a p h i s a v o i d g r a p h . N e x t we c o n s i d e r t h e c a s e when t h e m i n i m a l p o l y n o m i a l i s q u a d r a t i c . 28 Thgorem_2.8 Let p = x 2 • ax + b be the minimal polynomial of a graph G with n v e r t i c e s . Then b < 0 and G c o n s i s t s of n/(1 - b) c o p i e s of complete graphs of order 1 - b and p = (x + 1) (x + b) . , Proof I f A i s the adjacency matrix of G, we have p = xz • ax + b and A 2 * a A + b i = 0. Let B = [ b ^ ] = A*; then (i) hiL = degree of vertex i , <ii) b t: = number of v e r t i c e s adjacent t o both i and j 0" Ci * j) • Since B = -aA - b i and a-^ = 0, <i) i m p l i e s G i s r e g u l a r of degree -b and so b < 0. Let E(G) be the edge set of G. , I f ( i , j) 4 E(G), i # j , then the number of v e r t i c e s adjacent t o both i and j equals 0; and i f ( i , j) e E{G), then the number of v e r t i c e s adjacent to both i and j equals -a. Now take any two v e r t i c e s i and j ( i # j) such that <i, j) 4 E(G). Let S;, = (k| ( i , k) € E(G)}, S-^ = {kf ( j , k) € E <G)} . C l e a r l y Si A S^ = <p. Take any two v e r t i c e s k, 1 e S t. .  (k, 1) 4 E ( G ) i m p l i e s that the number of v e r t i c e s adjacent t o both k and 1 i s 0, but i i s a d j a c e n t t o both k 29 and 1, so we must have (1c, 1) fe E(G) . T h e r e f o r e every p a i r of v e r t i c e s i n S t i s adjacent. A l s o every vertex i n i s adjacent to i ; hence S t U {i} i s a complete graph. Since the number of v e r t i c e s adjacent t o both k and 1 i s -a, the order of S^ 0 fi} i s -a + 2. S i m i l a r l y f o r S^ 0* {j}. So G c o n s i s t s o f n/(2 - a) c o p i e s of complete graphs of order 2 - a; but G i s r e g u l a r o f degree -b, so -b = -a *• 1. Therefore G c o n s i s t s of n/(1 - b) c o p i e s of complete graphs of order 1 - b. Now -b = -a + 1, so t h a t a = b + 1. Therefore p = x 2 + ax • b = x 2 * (b + 1)x • b = (x * 1) (x + b ) . C o r o l l a r 2 _ 2 ^ 2 I f p = (x + 1) (x + b) i s the minimal polynomial of a graph G with n v e r t i c e s , then* res) = s w rs,_ b i 1-b and | T(G) ! = (n/(1 - b ) ) ! ( ( 1 - b ) ! ) V ( i - b ) . * See [16, p. 164] or Section 1.2 f o r a d e f i n i t i o n of the wreath product A[B] of A around B. 30 Now l e t us c o n s i d e r some o p e r a t i o n s on graphs (as d e f i n e d i n S e c t i o n 1.2) and t h e i r e f f e c t s on the c h a r a c t e r i s t i c polynomials of the component graphs. D e f i n i t i o n , 2. 2 A graph G i s s a i d t o be i n t e g r a l (or, e g u i v a l e n t l y , to have i n t e g r a l spectrum) i f a l l the e i g e n v a l u e s of G are i n t e g e r s . I t f o l l o w s from D e f i n i t i o n 2.2 that the minimal and c h a r a c t e r i s t i c polynomials of an i n t e g r a l graph c o n s i s t only of l i n e a r f a c t o r s . The f o l l o w i n g theorem on complements of r e g u l a r graphs i s due to Sachs [ 3 4 1. Theorem 2._9 Let G be a r e g u l a r graph of degree r and with n v e r t i c e s , then f ( G ; x) = (-1)" f ( G . _ x . 1 ) # C o r o l l a r y . _ 2 i 3 j- i g ] I f a r e g u l a r graph G i s i n t e g r a l then so i s G. The f o l l o w i n g r e s u l t s are proved i n [353 and [ 1 9 ] , 31 Theorem_2i.10 [ 3 5 ] Let f ( G ; x) = 7T ( x - XL) and f{H; x) = TT(x - yUj) be the c h a r a c t e r i s t i c polynomials of two graphs G and H. Then* f ( G x H; x) = TTTTCx - *i f ( G A H; x) = TT]T(x - Xifo) f < G * H; x) = T T T T ( x - Kfo - Ai . C o r o l l a r y 2.4 [19] I f G , and G 2 are i n t e g r a l , then so are G , x G 2 , G, A G z and G, * G 2 . Theorem_2 i1J [ 3 5 ] I f G, and Gz are r e g u l a r graphs o f degrees r ( and r 2 and with n, and n 2 v e r t i c e s r e s p e c t i v e l y , then f <G, ) f (G 2) f(G, + G 2; x) = (x* - (r, + rz)x + r, r A - n, n 2) , x y x _ y . Cor o l 1 a r 2 _ 2^ .5 [ 1 9 ] The j o i n G, • G 2 of two r e g u l a r graphs i s i n t e g r a l i f and o n l y i f both G, and G 4 are i n t e g r a l and (r, - r 2 ) 2 + 4n, n 2 i s a p e r f e c t sguare. * See [35 ] and [16] f o r d e f i n i t i o n s of the o p e r a t i o n s on graphs guoted i n t h i s theorem. 32 Next, we are going to c o n s i d e r f a m i l i e s of graphs with l i n e a r f a c t o r s i n t h e i r minimal polynomials. ( 1) Complete^graphs and void_graphs Let n be > 2. Then f <K„; x) = (x - n + 1) (x + 1 p ~ l , so t h a t P(Ky,; x) = (x * 1) (x - n + 1) . The complement K w of K M i s the v o i d graph on n v e r t i c e s . fiKy,; x) = x" and p {K„; x) = x. The r e f o r e a l l f a c t o r s o f the minimal polynomials of K„ and K„ are l i n e a r f o r n = 2, 3, .... A l s o we know that only void graphs can have l i n e a r minimal polynomials, and connected graphs with g u a d r a t i c minimal polynomials are complete. , Since = and [-(*„) = , we have r<KJ = TtKv,) •= S*, and I R K J I = ITCK,,) I = n!. ( i i ) Complete b i p a r t i t e gra£hs Let K W ) 1 denote the complete b i p a r t i t e graph (see f 1 6 , p. 17]) on V, and V 2 where | V, j = m, |V Z| = n. Schwenk[35] has shown that fCK^^ ; x) = (x 2 - mnjx™*"- 2 which i m p l i e s pCK^ ^ ; x) = x (x 2 - mn) f o r m • n > 2. Theref o r e K „ B i s i n t e g r a l i f and only i f mn i s a 33 p e r f e c t square. Also i f m - n, K m ^ and K W j W > are both i n t e g r a l . f(K«,, w; X ) = ( X - B + 1 ) 2 ( X + 1 ) Z " - 2 , and f o r m > 1 P<K„ # W 1; x) = (x - • • 1) (x + 1) . Since „ = K M + K w, the above r e s u l t s are a c t u a l l y p a r t i c u l a r cases of C o r o l l a r y 2.5. I f m # n, then by C o r o l l a r y 1.1, r ( K M > w ) = T ( K J • R K « ) = S„ + S,.. Therefore i T f K ^ , ) I = n!n!.. I f m = n, = 2K m i m p l i e s r ( K m < w ) = S J S J . Hence r ( K m > w J = n^, w) = S 2 [ S W ] and- IRK*,, J I = f r ( K w . « ) l = 2(m ! )2. When m = 1, n > 2, the r e s u l t i n g graphs are c a l l e d claws (or s t a r s ) . The s t a r K, i s i n t e g r a l i f and only i f n i s a p e r f e c t square, i n which case we have P(K 1 („ ; x) = x(x* - n) , r(K l > w) = s„, ana i r(K l ( Y,) \ = n!. ( i i i ) Cubes Let Q w denote the n—dimensional cube. Then 34 n terms I t has been proved i n [ 3 5 ] that f (Q„; x) = T T <x - n + 2i) and i=0 n P(Q n: x) = T T (x - n + 2i) . i=0 Thus Q„ i s i n t e g r a l f o r a l l n. Since Q w i s r e g u l a r o f degree n f o r a l l n we a l s o have that Q M i s i n t e g r a l f o r a l l n. By Theorem 2.9, we have x - z n * y, + , " <"> f <Q«! x> = , + „ + , TTl-x - 1 - n • 2i) = (x - 2 * n • 1) T T (x + 1 • n - 2i) i=1 For n = 1, p (Q, ; x) = x; n = 2, p(Q 2; x) •= (x - 1) (x + 1) , and n > 2, P(C> . x) = (x - 2 + n • 1) T T (x + 1 + n - 2 i ) . i=1 The f o l l o w i n g theorem has been proved by Palraer[29] ( f o r a d e f i n i t i o n of the e x p o n e n t i a t i o n group, see [16, p. 177]). Theorem 2.12 I f G i s connected and prime <with r e s p e c t t o the product d e f i n e d i n Sect i o n 1.2), then 35 nc*) = tr ie) r. Coro!lary__2. 6 HQ*) = T ( Q J = f S a 1 ana | H Q J I = I T(Q J I = n!2 w. Proof T h i s f o l l o w s immediately from the f a c t t h a t K 2 i s prime and It B 1 AI = | AJ • fBJ* where d i s the s i z e o f the s e t on which the permutation group A a c t s . When n = 2, Q 2 = K 2 X K2 = C 4. The r e f o r e 2 i\) f <c4; x) = TT (x - 2 + 2i) i=0 = x*(x - 2) (x + 2) , and p ( C + ; x) = x(x - 2) (x + 2) . S 2 A l s o T( C4) = T{C4) = [ S z ] = D 4, t h e d i h e d r a l group on f o u r elements, and hence |RC 4) I = ir<C 4) I = 8. (iv) T r e g s o f diameter 3 I f T i s a t r e e with diameter 3, i t i s easy to see t h a t T's cent e r i s a p a i r of adjacent v e r t i c e s . Moreover, T i s completely c h a r a c t e r i z e d by t h e degrees of the two 36 c e n t e r v e r t i c e s . The f o l l o w i n g theorem concerning 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 an a r b i t r a r y t r e e i s proved by Mowshowitzf 25]. Theorem_ 2 ..13 Let T be a t r e e of order n, then f o r 0 < k < n, the k-th c o e f f i c i e n t a f e of n LO, otherwise, where h r(T) = number of c o l l e c t i o n s of r nonadjacent edges i n T. I f T i s a t r e e o f diameter 3, and m, n are the degrees of the c e n t e r v e r t i c e s then f (T; x) = x m + v ,-*(x» - (m + n - 1)x* + {m - 1) (n - 1}). Proof h, (T) = number o f edges i n T = m + n - 1 . Obviously, h 2 (T) = (m - 1) (n - 1) and h r(T) = 0 f o r a l l r > 3. Therefore f (T) i=0 i s given by (-1) Vh r<T), i f k = 2r f o r some r > 1; 37 f ( T ; x) = x w+» - (m + n - 1) x^ 1*"- 2 * (m - 1) (n - 1 ) x * + " - » - x W + r , _ 4 t X 4 _ (rn + n - 1 ) x 2 * (m - 1) (n - 1 } ) . F i g u r e 2. 1 : \A i,Trge i - iof_Diaffleter 3 £orollarj_2 A8 I f T i s a t r e e o f diameter 3, and m, n are the degrees of the center v e r t i c e s , then T i s i n t e g r a l i f and only i f the f o l l o w i n g a re s a t i s f i e d : (i) <m + n - I ) 2 - H{m - 1) (n - 1) = k 2 f o r some i n t e g e r k, and ( i i ) i f <i) ho l d s f o r some i n t e g e r k then ((m + n - 1) • k)/2 and ((m + n - 1) - k)/2 are p e r f e c t sguares. Proof Obvious from the c h a r a c t e r i s t i c polynomial of T. In p a r t i c u l a r , i f m = n we have the f o l l o w i n g theorem. 38 Theorem 2.14 I f T i s a t r e e of diameter 3, and the degrees of the ce n t e r v e r t i c e s are both equal t o m, then T i s i n t e g r a l i f and only i f m = pz • p * 1 f o r some p o s i t i v e i n t e g e r p. Proof I f m = n = p 2 • p • 1 f o r some p o s i t i v e i n t e g e r p, then (m • n - 1 ) 2 - 4{m - 1) (n - 1) = (2pz + 2p • 1} z - 4 (pz + p) z = 4p* + 4pz + 1 + 8p3 * 4pz 4- 4p - 4p» - 8p3 - 4p 2 s 4pz • 4p + 1 = (2p + I ) 2 . Let k = 2p • 1. Then <{m + n - 1) + k)/2 = (2p 2 2p + 1 + 2p + 1)/2 = (2pz * 4p + 2)/2 = pz + 2p + 1 = (p • 1)z, and (<m + n - 1) - k) /2 = (2pz • 2p #• 1 - 2p - 1)/2 = pz, which i m p l i e s T i s i n t e g r a l . Now suppose T i s i n t e g r a l . Then (m + n - 1 ) 2 - 4 (m - 1) <n - 1) = (2m - 1)z - 4 (m - 1) z must be a p e r f e c t square. Now (2m - 1) z - 4 (m - 1) 2 = 4mz - 4m * 1 - 4m2 + 8m - 4 = 4m - 3. I f 4m - 3 = kz f o r some p o s i t i v e i n t e g e r k, then ((m + n - 1) k)/2 and {(m • n - 1) - k)/2 must be p e r f e c t sguares., 39 Let tin + n - 1) + Je)/2 = <{2m - 1) + k)/2 = q 2 <(m • n - 1) - k)/2 = ((2m - 1) - k)/2 = p 2 f o r some p o s i t i v e i n t e g e r s p and q. Obviously we have g > P. Then p 2 • q 2 = 2m - 1, and p 2 q 2 = ((2m - 1 ) 2 - 4m + 3)/4 = (4m2 - 4m + 1 - 4m • 3) /4 = (4m 2 - 8m + 4)/4 = m2 - 2m • 1 = (m - 1) 2 , T h e r e f o r e m - 1 = pg and p 2 + q 2 = 2(pq • 1) - 1 = 2pq * 1, which i m p l i e s (p - g)2 = 1, so t h a t q = p + 1. Hence m = pq + 1 = p (p + 1) «• 1 = p 2 + p • 1. I n t e g r a l t r e e s of diameter 3 having unegual degrees f o r the cente r v e r t i c e s are more d i f f i c u l t t o f i n d . A l i s t o f a l l i n t e g r a l t r e e s of order < 500 i s g i v e n i n Table I I I of the Appendix. From t h i s we see that the s m a l l e s t i n t e g r a l t r e e of diameter 3 with unequal degrees f o r the c e n t e r v e r t i c e s i s one with m = 51 and n = 99. The automorphism group of a t r e e with diameter 3 can be determined q u i t e e a s i l y . I f T i s a tre e o f diameter 3 havinq c e n t e r v e r t i c e s o f deqrees m and n r e s p e c t i v e l y , then pro = sm_, + s „_ , , I T"{T) ! = (m - 1) ! (n - 1) ! f o r m * n; no and n?) S S 2 [ S M . J 1 r ( T ) J = 2<(m - 1 ) ! ) 2 , f o r m = n. (v) S u b d i v i s i o n graphs of s t a r s Kly, Let G M denote the s u b d i v i s i o n graph of K, F i g u r e 2.2: S u b d i v i s i o n Graph o f K, 4 We are going t o use the f o l l o w i n g theorem by Schwenk[35] to compute f{G„; x ) . Theorem 2.15 Let v be a vertex of a graph G and l e t C(v) be the c o l l e c t i o n of c y c l e s c o n t a i n g v. Then f{G) •= xf (G - V) - 2 f (G - V -u ad j v - 2 Z Z6C {V) f ( G - V(Z)) where V(2) i s the set of v e r t i c e s c o n t a i n e d i n Z. 41 C o r o l l a r j _ 2 j L 9 f(G„; x) = x ( x 2 - n - 1) (x - 1 ) " - i ( x • 1)" Proof Let v be the vertex o f degree n i n G-„. Then G», - v c o n s i s t s of n c o p i e s of K a. Therefore f (G„ - v; x) •= (x - 1 ) " (x + 1 ) w . . For any u adjacent t o v, G„ ~ u - v c o n s i s t s of an i s o l a t e d v e r t e x and n - 1 copies of K a. . Hence f (G„ - v - u; x) = x (x - 1)*1 -» <x + 1 p . Since t h e r e are n v e r t i c e s adjacent t o v, Z ftG,, - v - u; x) = nx(x - 1>*>-»(x • I ) " - 1 . u a dj v Since G„ i s a t r e e , C{v) = <f>. So we have f(G„; x) = x(x - 1)" (x + 1 ) w - nx(x - 1)"-»(x + 1)* ~ l = x (x - 1)" - i (x • 1)* - i ((x - 1) (x + 1) - n) = x{x - I)*--*<x + 1)"-l(xz - n - 1). Thus G^ i s i n t e g r a l i f and only i f n + 1 i s a p e r f e c t square, i . e . when n = p 2 - 1 f o r some p o s i t i v e i n t e g e r p. I t i s obvious t h a t r<G„) = S„ and i r(G„) I = n!. O b v i o u s l y , t h e r e are other i n t e g r a l graphs which do not f a l l i n t o any of the above mentioned f a m i l i e s . Seme of them are composite graphs of i n t e g r a l graphs such as the one shown i n F i g u r e 2. 3. 42 K, + 3Ka f (K, + 3K 2; x) = (x - 1) 2{x + 1 )3 (x + 2) (x - 3) Some other i n t e g r a l graphs which have not yet been c l a s s i f i e d are shown i n F i g u r e 2.4 (see a l s o [ 1 9 ] ) . (i) ( i i ) < o f ( C 6 ; x) = (x - 1) 2{x + 1 ) 2 ( x - 2) (x * 2) f (G; x) = x (x + 1) (x - 1 ) 2 (x + 2) 2 ( x - 3) Fi g u r e 2.4: ,..,Tvo_Hore_Intggral_graphs We note t h a t C 6 = TT{3, 2, 1), the symmetric block design with parameters v = 3, k = 2 and A = 1. Obviously many graphs t h a t have both l i n e a r and n o n - l i n e a r f a c t o r s can be found i n f a m i l i e s o f graphs de s c r i b e d i n ( i i ) , (iv) and (v) above. Next we are going t o s t a t e a theorem by Schwenkr35] and use i t t o compute the c h a r a c t e r i s t i c polynomials of a f a m i l y of graphs. Theorem 2.16 l e t uv denote a l i n e of G j o i n i n g the v e r t i c e s u and v and l e t C(uv) be the s e t of a l l c y c l e s c o n t a i n i n g t h i s l i n e . The c h a r a c t e r i s t i c polynomial of G s a t i s f i e s f(G) = f (G - uv) - f{G - u - v) - 2 2 f (G - V(Z) ) Z«C{uv) where V (Z) i s the set of v e r t i c e s c o n t a i n e d i n Z. We s h a l l use t h i s theorem t o compute the c h a r a c t e r i s t i c p o l y nomial of K„ - uv where uv i s the l i n e i n K M (n > 3) j o i n i n g any two v e r t i c e s u and v. By Theorem 2. 16, we have f (Ry\ - uv) = f + f (K* - u - v) + 2 Z f l K * - V(Z)) Z*C (uv) = (x - n + 1) (x + 1)"-* + (x - n + 3) {* • 1)11 ~ 3 + 2 £ f (K„ - V(Z)). Z6C (UV) Let Z be a c y c l e of le n g t h k + 2 c o n t a i n i n g uv. Then ffK„ -7(Z)) = <x - n • k • 3) (x + 1 ) * - K - 3 . Obviously t h e r e are t,_2.Pk such c y c l e s ; t h e r e f o r e f (K,, - uv) = (x - n + 1 ) (x * 1 ) " - * + (x - n + 3) (x + n-2 + 2 I k« <"-*) <x - n • k + 3) (x + 1 ) " - k ~ 3 . *= 1 Using i n d u c t i o n we can show t h a t t h i s e x p r e s s i o n i s e q u i v a l e n t to x (x • 1 ) * - 3 ( x 2 - (n - 3) x - 2 (n - 2) ). So we have f (K M - uv) = x(x • 1)"-3{x* - (n - 3) x - 2<n - 2)) . 45 I I I . ADJACENCY MATRIX AND AUTOMORPHISM GROUP Two main t o p i c s w i l l be s t u d i e d i n t h i s chapter. F i r s t we w i l l look a t graph p r o p e r t i e s t h a t correspond to s p e c t r a l p r o p e r t i e s o f the adjacency matrix. Then the r e l a t i o n s h i p between the c h a r a c t e r i s t i c polynomial o f the adjacency matrix and t h e automorphism group w i l l be examined. 3.1 Spect rum_of _a_Grap_h As d e f i n e d i n Se c t i o n 1.5, the spectrum of a graph i s the set of a l l eigenvalues (with r e p e t i t i o n s ) of the adjacency matrix; the index of a graph G, denoted by r , i s the l a r g e s t v a l u e i n i t s spectrum. I f G i s connected, then by the Frobenius—Perron theorem, r i s a simple root of the c h a r a c t e r i s t i c polynomial o f A. In t h i s s e c t i o n , we w i l l c o n s i d e r graph p r o p e r t i e s t h a t can be c h a r a c t e r i z e d by the p r o p e r t i e s o f i t s spectrum. The f o l l o w i n g theorem i s a simple r e s u l t f o r graphs with s m a l l index. Theorem 3.1 I f r < 2, then every component of G i s a t r e e . Proof I f G, i s a component o f G which i s not a t r e e then G, c o n t a i n s a c y c l e , say v, , v 2 , ...» v p , v( . Let b be the ei g e n v e c t o r f o r A(G,) corresponding to 46 r, , the index of G,, such that b, , b 2 , . . . , b f are the e n t r i e s i n b corresponding t o v, , v 2 , ..., v p , r e s p e c t i v e l y . By the Frobenius-Perron Theorem, a l l e n t r i e s of Jb are p o s i t i v e , and s i n c e ( i ) v, i s adjacent to v t , v p , ( i i ) Vp i s adjacent t o v, , v p_, , and ( i i i ) f o r i = 2, 3, ... , p - 1, Vi i s adjacent to v t_, , v i + ) , we have r, b, > b t + bp r, bp > b, • b p _, and r, bj, > b t _ , • b £ + l f o r i = 2, 3, p - 1. Hence p p r , i b i > 2 j b, i=1 i=1 which i m p l i e s r, > 2; but r, < r i m p l i e s r > 2. So f o r r < 2 every component of G must be a t r e e , Smithf36] proved a stronger r e s u l t as s t a t e d i n the f o l l o w i n g theorem. The index of a graph i s < 2 i f and only i f each component of G i s a proper subgraph of one of the graphs i n Figure 3.1. 47 (a) (b) (c) (3) (e) (f) Fiqqrg m3 A1?,^Graplis_ j g 4 t f e-l5i§3? , 2 The f o l l o w i n g theorem i s qiven i n [ 5 ] , Theorem 3.3 Let r be the index of a f i n i t e , connected graph G with n v e r t i c e s , and l e t g m i i > , q and q m a - x t r e s p e c t i v e l y , be the minimum, averaqe, and maximum degree of the v e r t i c e s . Then the f o l l o w i n g i n e q u a l i t i e s hold; (i) g*,ih < q < r < q m „ , ( i i ) 2cos T . <r < n - 1. We w i l l now present some other i n e q u a l i t i e s on the 48 index of a graph and c h a r a c t e r i s t i c those graphs which a t t a i n e q u a l i t i e s . Theorem 3.4 I f k i s the maximum degree* o f a connected graph G, then r« > k > r. Proof J From Theorem 3. 3, we have k > r . Now l e t A(G) be the adjacency matrix of G with vertex s e t {v, , v 2 , . .,, v„} i n which v, i s of degree k. A l s o l e t {a, bzt b 3 , ..., b„)* be the e i g e n v e c t o r o f A(G) a s s o c i a t e d with r . Then r a = Z b c UK where K = [ i \ v c i s adjacent t o v, }. Therefore |K| = k. Now f o r each i t K, rb; = a + Z b; where K-t = {jj v- i s adjacent to v L , j # 1}. Hence r i b ' = Z a + Z Z b;. i*K i€K i«K KL By the Frobenius-Perron Theorem, a > 0 and b ; > 0 f o r * The maximum degree o f a graph G w i l l a l s o be denoted by k i n C o r o l l a r i e s 3.1 and 3.2. us ]^ — 2 j 3 ^  « * • r n* Therefore r 2 a > ka and r 2 > k. C o r o l l a r 2 _ 3 i J G i s a connected graph with r 2 = k i f and o n l y i f G i s a claw*. Proof I f G i s a claw with n v e r t i c e s , then k = n - 1 and f ( G ; x) = x h - 2 ( x 2 - n + 1). T h i s i m p l i e s r = «/n - 1, and thus r 2 = k. Now assume t h a t r 2 •= k. Then we have r 2 a = ka + £ £ b; , which i m p l i e s i€K jeK L 2 Z b L = 0. From t h i s i t f o l l o w s t h a t i f K• * </> ifcK jfeKL *• bj_ = 0 f o r a l l j 6 KL , i t K. Since G i s connected b^ > 0 f o r a l l j = 2 , 3, n, so t h a t K-L = <f> f o r a l l i * K, and v L i s adjacent o n l y to v, f o r a l l i K. Therefore the induced subgraph with v e r t e x s e t {v, 3 0 {vL | i * K] i s a claw. * See p.33 f o r the d e f i n i t i o n of a claw. 50 Now deg v, = k , deg v^ = 1, f o r a l l i £ K i m p l i e s t h a t no other vertex i n G i s connected to any of the v e r t i c e s i n {v, } U [v^ j i t K} ; but t h i s c o n t r a d i c t s the f a c t t h a t G i s connected. Hence V(G) = {v, } U f v c | i e K} , and G i s a claw. Corollar2_3i.2 G i s a connected graph with r = k i f and only i f G i s r e g u l a r of degree r. Proof I f G i s r e g u l a r of degree r, then o b v i o u s l y k = r. Now assume r = k , d^ = degree o f vert e x V j _ with d, = k , and k i s the adjacency matrix of G with vertex s e t {v, , v 2 , v M}. Also l e t (b i $ b 4 , • • • be an e i g e n v e c t o r a s s o c i a t e d with r . Then we have M b , , b 2 , . • • » b h)» = r(b, , b a , ...» b,,)' i . e . a,, b, + a l 2 b 2 + . • • + a.» b,, = rb, a 2 l b, • • a 2 2 b a • . . . *• a 2 v , b « r b 4 • a«, b, K + . . . + a„„b„ rb„. Rewriting we have 51 (a,, - r)b, + a i a b 2 + .... + a l h b B = 0 a a, b, • ( a 2 l - r ) b 4 * ... * a 2 ) ) b h = 0 a*, b i • a H 1 bt + ... + (a„„ - r) b„ = 0. C l e a r l y , n n (( £ a v, ) - r ) b , • {{ I aKX) - r ) b 4 • ... i=1 i=1 n M ( I a i h ) - r i b , = 0. i=1 T h i s i m p l i e s (k - r)b, + ( d 2 - r ) b 2 • ... (d* - r)b„ = 0. Now r = k i m p l i e s r > d^ f o r a l l i = 1, 2, ...,n. Since bL > 0 f o r a l l i = 1, 2, ..., n, d; = r f o r a l l i = 1, 2, n. In Theorem 3.3, we know that the index r of a connected graph G s a t i s f i e s the f o l l o w i n g i n e g u a l i t y : 2cos ^-TT ^ r < n - 1. By Theorem 3.1, the lower bound can be r a i s e d t o 2 i f G i s not a t r e e . Hence, f o r any connected graph which i s not a t r e e we have 2 < r < n - 1. Obviously f o r any graph w i t h n v e r t i c e s , the maximum p o s s i b l e degree i s n - 1 . So i f r = n - 1, then by 52 C o r o l l a r y 3.2, G i s r e g u l a r of degree i . e . G = K„. Now f o r any graph G which i s not the complete graph, G must be a subgraph of K„ - uv f o r some uv such that uv 4 E (G) . By the Probenius-Perron Theorem, we know t h a t the index of G i s l e s s than or equal t o the index of K h - uv, which i s equal to (n - 3 • Vfn - 3 ) 2 • 8 (n - 2)} /2 (see S e c t i o n 2.2). So we have the f o l l o w i n g i n e q u a l i t y f o r the index r of a graph G which i s not the complete qraph: r < (n - 3 + V(n - 3 ) 2 + 8 (n - 2) }/2. The spectrum of a qraph c o n t a i n s the index and hence should provide more i n f o r m a t i o n on the s t r u c t u r e o f the graph. The f o l l o w i n g theorem, as s t a t e d i n f 7 1, i n d i c a t e s how a r e g u l a r graph can be recognized by i t s spectrum. Thgorem_3,5 Let { X, = r , XZ T * 3 , A,,} be the spectrum of a graph G, where r denotes t h e index of G. Then G i s r e g u l a r i f and only i f n 1 =1 More r e s u l t s on the c h a r a c t e r i z a t i o n of a graph by means of i t s spectrum can be found i n [ 5 ] , [7"I and f ^ 1 ] » The f o r e g o i n g r e s u l t s on c h a r a c t e r i z a t i o n of a graph 53 by means o f i t s spectrum o b v i o u s l y depend on the computation of the c h a r a c t e r i s t i c r o o t s of the graph. U s u a l l y some knowledge of the s t r u c t u r e of a graph w i l l h elp i n computing i t s c h a r a c t e r i s t i c p o l y n o m i a l , and thus i t s spectrum. In [5], the symmetrical p r o p e r t i e s of a graph have been used t o s i m p l i f y the c a l c u l a t i o n o f the c h a r a c t e r i s t i c polynomial, 8e w i l l show one method i n which t h i s can be done. Let G be a graph with v e r t e x s e t fu , , u 2 , u p ; v,, v 2 , •>., v M ; v m + , , v > n + 2 , ,»,, v l m} such t h a t the s e t s 7, = fv, , vz , ...» v^ ,} and V 2 = ( V v „ + I , v w + 2 , v 2 w } are symmetrical about U = (u, , u 4 , Up}. That i s t o say, f o r i» j = 1» 2, m, (vt , vp € E(G) i f f ( v w + i, V w ) 4.) 6 E(G), <^ , + e E(G) i f f i v ^ , v^ ) c E(G), and f o r any vertex u € U, ( v L , u) € E(G) i f f (v^ + l , u) € E(G). Hence we can p a r t i t i o n the adjacency matrix A(G) as f o l l o w s : " c R R " A = R» P Q . R« Q P. C = 3 P = 1 Q = 3 54 E = and C; 9 i i •{ 1 i f u L i s adjacent to U: , 0 otherwise, i , j = 1, 2, ..., p; 1 i f v t i s adjacent to v^ , 0 otherwise, i , j = 1, 2,..,, in; 1 i f vi i s adjacent to v m + . , 0 otherwise, i , j = 1, 2, ..., m; 1 i f u t i s adjacent to , 0 otherwise, i - 1, 2, p, j = 1, 2, «.,, m, Let I be the i d e n t i t y matrix of order 2m • p. Then d e t ( x l - A) = det xlp - C -R» -R xi*, - P -Q -R -Q x l m " P. = det x l p - C -2R -R -R» x l m - P - Q -Q -R* XI*, - P - Q X l m - P = det xlp - C -2R -R -H» XIm - P - Q -Q 0 0 x l w - P • Q = det (xl„ - P + Q)det fxlp - C -2R -R« X l m - P - Q Hence the c a l c u l a t i o n of the c h a r a c t e r i s t i c polynomial of A i s reduced to c a l c u l a t i n g the 55 c h a r a c t e r i s t i c polynomials of two (three i f E = 0) s m a l l e r matrices. The f o l l o w i n g example w i l l i l l u s t r a t e t h i s method more c l e a r l y . Example 3.1 Consider the graph G shown i n Figure 3.2. 1 2 4 3 Figure.3.2: ,A ,Graph_with_Symmgtry Here U = {5} , V = { 1 , 4}, V = {2, 3); so C = [ 0 ] , 0 1 P = .1 0 0 1 .1 1 Q = d e t ( x l 2 - P + Q) = det det x 0 0 x + 1 = X ( X • 1) , -2R fx I, - C -E' x l 2 - P - Qj 56 = det x -2 -2 -1 x -2 1-1 -2 x - 1 = x3 - x z - 8x + 2. Therefore f (G; x) = x(x + 1) ( x 3 - x 2 - 8x + 6) = x(x + 1 ) 2 ( x 2 - 2x - 6). 3.2 C h a r a c t e r i s t i c _ P o l y n o m i a l and , Automorphism Group of a Graph In t h i s s e c t i o n the r e l a t i o n s h i p between the c h a r a c t e r i s t i c p o l y nomial and the automorphism group of a graph w i l l be s t u d i e d i n d e t a i l . The f o l l o w i n g theorem i s proved by Howshowitzf 24 }. Theorem 3.6 Let D be a digraph with adjacency matrix A, automorphism group T, and c h a r a c t e r i s t i c p olynomial f of degree n; and l e t k be the number of o r b i t s of T . Then there e x i s t s a polynomial of degree k d i v i d i n g f . For s i m p l i c i t y sake, we w i l l r e s t r i c t o u r s e l v e s to u n d i r e c t e d graphs; the g e n e r a l i z a t i o n to digraphs w i l l be di s c u s s e d i n the next chapter. Before we prove the next theorem we w i l l need some lemmas. 57 Lemma_3.1 I f H i s a group o f automorphisms of a graph G, and i f B, S (R may be equal to S) are any two o r b i t s o f H, then f o r v-t , v^ 6 B, the number o f v e r t i c e s i n S adjacent to v-- the number of v e r t i c e s i n S adjacent to v•. Proof I f V;, , v- e R, then t h e r e e x i s t s <r e H such t h a t Take any w e S such t h a t (v^ , w) € E (G) , Then (V L, w) 6 E CG) i f f (Vj , <r{w)) € E(G), and s i n c e <r(w) e S, we have number of v e r t i c e s i n S adjacent to V;_ = number o f v e r t i c e s i n S adjacent t o v j . * Now l e t H be a group of automorphisms of a graph G. We d e f i n e the o r b i t - m a t r i x and o r b i t - d i g r a p h as f o l l o w s : Dsf inition_3.i_1. Let P, , P 2, ... , P k be the o r b i t s of H. For each P-t take v- e P; t o be i t s r e p r e s e n t a t i v e . The matrix «{H) = C 3, with mv = number of v e r t i c e s i n P- adjacent t o v^, i , j = 1, 2, . k, i s c a l l e d the o r b i t - m a t r i x of H (with 58 r e s p e c t to G)*. The weighted digraph with ver t e x s e t {v, , v 2 , ...» v k) and a r c weights (v L , v) = m.. , i s c a l l e d the o r b i t - d i g r a p h o f H. Obviously the o r b i t - m a t r i x and o r b i t - d i g r a p h of any group of automorphisms of a graph are independent o f the c h o i c e of r e p r e s e n t a t i v e s . We w i l l make t h i s d e f i n i t i o n c l e a r by the f o l l o w i n g example. Examp.le_3._2 Let G = , the claw on f i v e v e r t i c e s with c e n t r e {1}, and H = <(25), (31) >. Obviously H i s a group of automorphisms of G. The o r b i t s o f H are {1}, {2, 5} and f3, 4} . L e t 1, 2 and 3 be the r e p r e s e n t a t i v e s . Then '0 2 2 M(H) = 1 0 0 .1 0 OJ and the c o r r e s p o n d i n g o r b i t - d i g r a p h i s shown i n F i g u r e 3.3. * The phrase i n parentheses w i l l be omitted whenever the terra i s c l e a r from the context. 59 F i g u r e , 3. 3 K t 4 and A s s o c i a t e d O r b i t - d i g r a p h o f < (25) , (34) > Now i f H, i s a g r o u p o f a u t o m o r p h i s m s o f a g r a p h G, H 2 a s u b g r o u p o f H, , and B, , B z , ..., B k a r e t h e o r b i t s o f H, w i t h s i z e s b, , b a , ... r b k» r e s p e c t i v e l y , t h e n H z h a s o r b i t s A u , A , . . . , A ; w i t h s i z e s a u , a, 2 , a , p ; a a i ' a l 2 , a 2 p j a k i ' a k 2 * a k p r e s p e c t i v e l y . Ic The A ^ and a t ^ s a t i s f y t h e r e l a t i o n s 60 P • P • 1 x ' x U f t i L = &i and I a i L = b t i = 1, 2, . . . , k . Let T = I ^ i j . 1 be the k x k matrix d e f i n e d by t j : = number o f v e r t i c e s i n B: adjacent to a vertex i n B^, C l e a r l y T = M(H,), the o r b i t - m a t r i x of H,. , Let S be the matrix p a r t i t i o n e d i n t o k 2 submatrices, where the i j — t h subraatrix and s<^i-> -= number of v e r t i c e s i n A^, adjacent to a vertex i n &u » 1 = 1, 2, ...» p L ; m = 1 , 2 , . . . , p- . S = H(H Z) i s the o r b i t — m a t r i x o f H 2. Now we have the f o l l o w i n g lemma., Lemma 3.2 The c h a r a c t e r i s t i c polynomial of T d i v i d e s t h a t of S, i . e . d e t ( x l - T) J d e t ( x l - S). Proof P1 Since A L. C B; and \J A- = B; m=1 «" * i , j = 1, 2, k , and the A^ m's are mutually d i s j o i n t , we have PD .. J s<^> = t L : i , j = 1, 2, ... , k . m= 1 Now l e t (z, , z z , z^) ' be an e i g e n v e c t o r of T 61 corresponding to the eigenvalue A. Then we have k HtiLzl = f o r a 1 1 1 = 1 * 2, k. j=1 *" * Consider the e x p r e s s i o n p terms p terms p. terms i - 1 The ( p- + l ) - t h term, where 1 < 1 < p. , i s j=1 * k p j k Z ( 2 s« i<h')z L = _T t-- Z : = Xz. . -j=1 m=1 ' 1=1 * " Hence X i s a l s o an eigenvalue of S, from which i t f o l l o w s that det ( x i - T) |det<xl - S) . The next theorem f o l l o w s r e a d i l y from Lessa 3.2. Theorem 3.7 Let H,, H z, H| be groups o f automorphisms of a graph G with H, = fe) , H^  = T(G) and H^  a subgroup o f H i + 1 f o r a l l i = 1, 2, ... , q - 1 . I f T t = M(H L), the o r b i t — m a t r i x o f H-tf then we have f (Tj) If <Tj_,), f <Tj_ , ) |f (T|_ t) f f (T 2) If (T,) = f (G). CorpJ.lary._3_3 I f H i s a group of automorphisms of a graph G and i f H has k o r b i t s , then there e x i s t s a polynomial of degree k t h a t d i v i d e s f (G) . 62 The converse of C o r o l l a r y 3.3 i s , however, not t r u e as shown by the f o l l o w i n g example. Example^^S Consider the path on f i v e v e r t i c e s as shown i n Figure 3,4. The c h a r a c t e r i s t i c polynomial i s x (x - 1) (x + 1) ( x 2 - 3) and the only n o n t r i v i a l subgroup of the automorphism group i s H = {e, (15)(24)}, the automorphism group i t s e l f . 1 2 3 4 5 • • • • • F i g u r e 3.4: The.,,, path .on .Fiye V e r t i c e s H has t h r e e o r b i t s {1, 5}, {2, 4} and {3}. The o r b i t - m a t r i x o f H with r e p r e s e n t a t i v e s 1, 2 and 3 i s '0 1 0* 1 0 1 . ,0 2 0. The c h a r a c t e r i s t i c polynomial of t h i s matrix i s x ( x z - 3) . Hence by Lemma 3.2 or Theorem 3.7 t h e r e does not e x i s t a group of automorphisms which has x, x - 1, x + 1, x 2 - 3, x(x - 1), x(x • 1), (x - 1) ( x 2 - 3), (x - 1) (x + 1} or (x • 1) ( x 2 - 3) as the c h a r a c t e r i s t i c polynomial of i t s o r b i t — m a t r i x . The f o l l o w i n g theorem i s given by Yap i n [ 4 2 ] . 63 Theorem.3.8 The c h a r a c t e r i s t i c polynomial o f the adjacency matrix A of a weighted digraph D with n v e r t i c e s whose automorphism group T i s n o n - t r i v i a l i s the product o f the c h a r a c t e r i s t i c polynomials o f the f o l l o w i n g two matrices. B = [b-^ ], C = f C i j . ] d e f i n e d by: C ) b V i = _£ a.. i , j = 1, 2 , k, * v t«P c v L i s the r e p r e s e n t a t i v e o f the i - t h o r b i t , PL , k = number of o r b i t s o f T. <2) c-t- = a k + L ^ . - a k + . r i f v f c +. e P r x ^  3 1| 2| • • • y n *• R • Yap c a l l e d the two f a c t o r s the c h a r a c t e r i s t i c ESlY p6li§l-:2l -1r} 1?,. S Y nW?' tltlg-B a rfe ,of,. ft and the g h a r a c t g r i s t i c _ _ o l y n o _ i a ^ _ p f the_cpmfilgmentarY_gart pf„A, r e s p e c t i v e l y . . I t happens t h a t the c h a r a c t e r i s t i c polynomial of t h e symmetric part o f A eguals the c h a r a c t e r i s t i c polynomial of the o r b i t — m a t r i x of • We w i l l now d e f i n e a matrix C(H) which i s analogus to the complementary part of A. Let G be a graph and H a n o n t r i v i a l subgroup of the automorphism group of G; a l s o l e t P, , P 2, ...» P k be the o r b i t s of H, and v t | , vzi , v k ( the r e p r e s e n t a t i v e s used i n computing H (H). 64 Let P, = K , , v, v } 1 r2 ' k where p L = JP^J. Let B = {i | p L > 1} and |B| = b. low we assume ( r e l a b e l i n g i n d i c e s i f necessary) t h a t p c > 1 f o r 1 < i < b and p. = 1 f o r b < i < k. Also l e t 3(u, v) be the adjacency f u n c t i o n of G. Then the orbit-complement-matrix and orbit—complement—digraph o f H with res p e c t t o G w i l l be d e f i n e d as f o l l o w s . D e f i n i t i o n _ 3 . 2 Let C(H) be the p a r t i t i o n e d matrix with b 2 submatrices such t h a t the i j - t h submatrix where c<^> = 5 ( v i / £ + 1 , v. Y n + ( ) - ^(v., , V j , w + 1 ) 1 — 1, 21 • • •, p -t ~ 1; m = 1, 2, ... r p- - 1; and i , j t B. Then C(H) i s c a l l e d the orbit—complement-matrix of H, and the weighted digraph with vertex s e t 65 b i=1 and weights given by C(H) i s c a l l e d the orbit-cpmplement-digraph of H. Then we have the f o l l o w i n g theorem (c f . ,[42]). lll§o£em_3_i_9 Let H be a n o n — t r i v i a l subgroup of the automorphism group of a graph G with n v e r t i c e s and D, , D 2 the o r b i t - d i g r a p h and orbit—complement-digraph of H r e s p e c t i v e l y . Then f (G) = f (D, ) f (D 2) . Proof The proof i s e s s e n t i a l l y the same as the proof of Theorem 2 i n [ 42]. Le t P, , P 2, ... , P k be the o r b i t s of H and v, t v z , v k t h e i r r e p r e s e n t a t i v e s . Then i f a i s the adjacency matrix of G with vertex s e t {v, , v z , v k ; v k + | , v k + i , v„] , we have 66 f(G) = x - a. - a 2 l -a -a -a. -a x - a -a, -a -a i k -a I, K + I 11 * -a -a i , k + i kz ... x - a f c k k + ( " a k - M , i • • • - a k - n < t x " ak+.,M., -a. -a ~ a *>, lc+t -a, -a i n -a k w • » • ™ cL k+l, r< . x - a. where a ^ = i j - t h element of A, i , j = 1, 2, ..., n. I f we add to column j , j < k, a l l columns 1 > k * 1, such that fe , then we can w r i t e f (G) as f o l l o w s : f(G) = P Q R S where P = ... —b i k -b, x - b a i -b »k -b ki - b K 1 ... x - bfc|t b^• ^E. a^p i# j — 1/ 2/ •. . # k. 67 Q = -a , k+i ~ a»,k+ 2 -a . -a i n k,fc+i ~ a k , K + z -a fcn H = f r L ] where r ^ i s the i - t h row of B and r • = (0, 0, ... r 0, x, 0, 0, ...» 0) f t - t h p o s i t i o n - (b t | , b t t b t k ) i f v ^ e P t. (Note t h a t the e n t r i e s i n r-t are the same as those of the t - t h row i n P because k+ 3 - 1# 2, . » • , k , whenever v., . e P...) ~ ak+2,k+i and S = -a k+v, k+z x ~ ak+*,k<-2 -a n, k+2 ... . ™ a • • -a k+2,w x - a, Now f o r the i - t h row i n [B SJ, i f ^  c o n t a i n s the in d e t e r m i n a t e x i n the t - t h p o s i t i o n , then s u b t r a c t from i t the t - t h row of [P Q ]. Then 68 f (G) with T = xl„. P Q 0 T u - W where W - [w^ ] !1 ™" I f 2^ • * • y n "~* K • . Obviously Set P = f ( D ( ) and det W = f ( D z ) and f(G) = (det P) x (det W) , which i m p l i e s f (G) = f ( D , ) f ( D 2 ) . T h e r e f o r e , i f we know a n o n t r i v i a l subgroup of the automorphism group of a graph then the computation of i t s c h a r a c t e r i s t i c polynomial w i l l be reduced t o computing the c h a r a c t e r i s t i c polynomials o f two s m a l l e r weighted digraphs. We w i l l i l l u s t r a t e t h i s by the f o l l o w i n g example. Example 3.4 Consider the graph G shown i n Pigure 3.2. Obviously {e, (12) (34)} i s a group of automorphisms and the corresponding o r b i t - m a t r i x and orbit-complement—matrix with 1,3 and 5 as the r e p r e s e n t a t i v e s of the o r b i t s are given by: '0 2 1* 2 1 1 .2 2 0, and 69 0 0 .0 -1 J* The c h a r a c t e r i s t i c polynomials are x 3 - x 2 - 8x - 6 and x(x +1} r e s p e c t i v e l y . Hence f (G) = x<x + 1) ( x 3 - x* - 8x - 6) = x(x • 1) 2<x 2 - 2x - 6) . Note that the method used i n Secti o n 3.1 i s a s p e c i a l case of Theorem 3.9. 3.3 G r _ _ _ _ _ _ i t h _ _ a _ e l s We w i l l now study graphs whose v e r t i c e s have l a b e l s attached t o them. The f o l l o w i n g i s a p r e c i s e d e f i n i t i o n of graphs with l a b e l s . D e f i n i t i o n 3.3 A graph with, l a b e l s i s an ordered t r i p l e G = (V{G) , E(G) , 1 6) where V(G),- E(G) are the u s u a l vertex s e t and edge s e t r e s p e c t i v e l y , and 1^ i s the l a b e l i n g f u n c t i o n d e f i n e d on V{G) t o a set of l a b e l s , say (1, 2, p} where p > 2 i s the number of d i s t i n c t l a b e l s . I f 1Q(U) # I Q C V ) f o r every p a i r o f d i s t i n c t v e r t i c e s u, v $ 7(G) , then we c a l l G a l a b e l e d graph. The n o t i o n o f automorphisms of graphs can be extended 70 to graphs with l a b e l s as f o l l o w s . Def i n i t i o n _ . 3 . 4 IF i s an automorphism of G = (V (G) , E (G) , 1^) i f f o r a l l u, v fe V(G)t (u, v) fe E(G) i f f (<7-{u) , <T{v)) 6 E(G) ana l Q { u ) = 1<. (<r(u)) . Obviously the automorphisms of G a l s o form a group. The u s u a l c h a r a c t e r i s t i c polynomial of a graph G i s d e f i n e d as aet<xl - A (G)). i n order to take i n t o account the l a b e l s of the v e r t i c e s , we w i l l a l s o l a b e l the corresponding i n d e t e r m i n a t e s . D e f i n i t i o n 3. 5 Le t G = (V(G), EJG), i & ) with l a b e l s e t £1, 2, ..», p} and vertex s e t V{G) = f v , , v 2 , v ^ ; v ^ + | , v ^ + z , T v v - + V i + | ' 7 k i + y - + v i 4 2 ' Vy,} such that l ^ ( v , ) = 1 Q ( V 2 ) = . . . = 1 ^ ( v^ ) = 1, 1 71 T n e c h a r a c t e r i s t i c polynomial of G, denoted by f ( G ) , i s the determinant of We note t h a t the c h a r a c t e r i s t i c polynomial of a graph with l a b e l s i s a polynomial i n p in d e t e r m i n a t e s where p i s the number of d i s t i n c t l a b e l s . Theorem 3.9 can o b v i o u s l y be extended t o graphs with l a b e l s as f o l l o w s : Theorem 3.10 Let H be a n o n — t r i v i a l group of automorphisms of G = (V (G) , E (G) * . 1Q) and D, , Dz the o r b i t - d i g r a p h and orbit—complement-digraph of H r e s p e c t i v e l y . , A l s o l e t v, , v_, , . . . , v„ be t h e v e r t i c e s of G such t h a t v, f vz, ...» v k are the r e p r e s e n t a t i v e s of the o r b i t s P, , P a, ...» P k o f H with 72 <vL ) = l t i = 1, 2, . ... , n. Then f <G) = f (D,) f ( D J , where f(D,) = the determinant of x. 0 - M (H) and f { D i ) = the determinant of *k+1 0 x, -a k + 2 n - C{H) Now we have the f o l l o w i n g r e s u l t which i s analogus to C o r o l l a r y 3.3. C o r o l l a r y 3.4 I f H i s a group of automorphisms of a graph G = (V(G) , E(G), 1^) with p types of l a b e l s , and i f H has k^ o r b i t s whose elements have l a b e l i , then t h e r e e x i s t s a polynomial of degree k t i n xj. ( f o r a l l i = 1, 2, . •., p) t h a t d i v i d e s f (G) . A l i s t of graphs with two types of l a b e l s and a t most f o u r v e r t i c e s i s given i n Table IV of the Appendix. 73 IV. EXTENSIONS AND APPLICATIONS Various e x t e n s i o n s and a p p l i c a t i o n s w i l l be c o n s i d e r e d i n t h i s chapter. In p a r t i c u l a r , we w i l l extend the concepts of adjacency m a t r i c e s and automorphisms to digraphs and non—simple graphs. 4.1 Digraphs As d e f i n e d i n S e c t i o n 1,1, a digraph of order n i s an ordered p a i r D = (V (D), E(D)) c o n s i s t i n g of a nonempty s e t of v e r t i c e s V(D) with | V (D) | = n and a s e t of l i n e s E (D) such t h a t each e.e E(D) i s i d e n t i f i e d with an ordered p a i r (u,v) of d i s t i n c t v e r t i c e s u, v € V(D) . C e r t a i n important concepts of a digraph w i l l be given i n the f o l l o w i n g d e f i n i t i o n s . ; L e t D be a digraph with v e r t e x s e t V (D) = {v,, v t , v h } . The matrix MD> = [ a . L 1 i s c a l l e d the adjacency matrix o f G. The c h a r a c t e r i s t i c polynomial f ( D ) , and the minimal polynomial p(D) of D are given by f(A(D>) and p(A<D)), where 1 i f there i s a l i n e i n E<D) from v t to V; 0 otherwise. r e s p e c t i v e l y . D e f i n i t i o n 4 , _ 2 f i s an automorphism of a digraph D i f y i s a permutation on the vertex set V(D) such t h a t The main d i f f e r e n c e between the adjacency matrix of a digraph and t h a t o f a graph i s the f a c t t h a t the l a t t e r i s symmetric. I f , i n a digraph D, (u, v) i E(D) i f f (v, u) € E{D), then h (D) w i l l be i d e n t i c a l t o k (G) where G i s the graph having the same vertex s e t and <u, v) € E(G) i f f (u, v) « E(D) . So we can regard graphs simply as symmetrical digraphs. Now, s i n c e the adjacency matrix o f a digraph i s nonnegative, a l l the f o r e g o i n g r e s u l t s on adjacency matrices of graphs hold e q u a l l y well f o r digraphs i f the assumption t h a t the adjacency matrix i s symmetric i s not r e q u i r e d . We w i l l now e x p l i c i t l y s t a t e some of the r e s u l t s as extended t o digraphs. i m p l i e s 75 Th§oreni_4 Let H,, H 2 , v.., be groups of automorphisms of a digraph D with H, = fe} , = f{D) and a subgroup of H t + 1 f o r a l l i = 1, 2, g - 1. I f T L = tt(EJ then f l ? % ) | f (Tj_,) , f (T^_.) |-f ( T ^ _ 2 ) , f ( T 4 ) | f ( T ( ) = f<D). C o r o l l a r y 4.1 I f f (D) i s i r r e d u c i b l e over the i n t e g e r s , then T ( n ) i s t r i v i a l . By v i r t u e of C o r o l l a r y 4.1 we expect to have a r e s u l t analogous to Theorem 2.4. We w i l l need the f o l l o w i n g concepts f o r a digraph. D e f i n i t i o n ^ U ^ ( c f . {16, p. 198]) A path of length p from u t o w i n a digraph D i s a sequence of d i s t i n c t v e r t i c e s v 0 = u, v, , v 2 , v p_, , v p = w such t h a t <v.k_( , v L ) fe E(D) f o r a l l i = 1, 2, p. A vertex v i s s a i d t o be r e a c h a b l e from u i f there i s a path from u to v. A digraph i s s a i d t o be s t r o n g l y .connected i f every two v e r t i c e s are mutually reachable. A stro n g l y , connected component of D i s a maximal s t r o n g l y connected subdigraph of D. We have the f o l l o w i n g analogue of Theorem 2.4. 76 Theorem 4,2 I f D i s a digraph with an i r r e d u c i b l e minimal polynomial, and c h a r a c t e r i s t i c polynomial f = p , then D has k s t r o n g l y connected components which are c o s p e c t r a l i d e n t i t y digraphs with c h a r a c t e r i s t i c and minimal polynomials p. The f o l l o w i n g i s an example of a digraph which i l l u s t r a t e s C o r o l l a r y 4.1 and Theorem 4.2. ___________ The digraph D shown i n Fig u r e 4.1 i s the union of two digraphs which are converses of one another, i . e . one can be obtained from the oth e r by r e v e r s i n g the d i r e c t i o n s of a l l the l i n e s . Obviously digraphs t h a t are converse to each other have the same c h a r a c t e r i s t i c polynomial because t h e i r adjacency matrices are transposes of one another. F i g u r e 4_1 ___________________ _ i i k _ l E _ _ d _ c j ^ l e _ C ] ^ r a c t _ r i _ t i _ _ _ o l _ n _ _ i a l and i t s C o n v e r s e 77 Now f(D) = (x* - 2x2 - x - 1)2 and p (D) = x* - 2x2 - x - 1. The two s t r o n g l y connected components of D are i d e n t i t y digraphs because both of them have p(D) as the c h a r a c t e r i s t i c p o l y n o m i a l , and t h i s polynomial i s i r r e d u c i b l e . As i n t r o d u c e d i n S e c t i o n 3.2, a weighted digraph i s simply a digraph with weights attached t o i t s l i n e s . The adjacency matrix A (D) of a weighted digraph D with vertex s e t fv, , v z , v„3 i s given by A(D) = f a - ^ 1 where /-the weight on the l i n e from v-^  t o v- i f a-t^ = < t h e r e i s a l i n e from v L to v^, ^0 i f t h e r e i s no l i n e from v L t o v^ . The edge set of a weighted digraph w i l l be the set of l i n e s which have nonzero weights. 4.2 Non-simple.Graphs I f we allow l o o p s and m u l t i p l e edges i n the edge s e t of a graph, then t h e graph w i l l be a non-simple graph as d e f i n e d i n S e c t i o n 1. 1. D e f i n i t i o r ^ i ^ a The adjacency f u n c t i o n of a non-simple graph G = (V (G) , E (G) , fa ) i s d e f i n e d as f o l l o w s : 78 f o r u, v e V{G) ^ ( u , v) = number o f edges i n E(G) j o i n i n g u and v. Then the adjacency matrix of a non-simple graph w i l l be d e f i n e d as i n D e f i n i t i o n 1.6 with the above adjacency f u n c t i o n . Note that the adjacency matrix of a non—simple graph i s a l s o nonnegative and symmetric; hence most of the r e s u l t s i n Chapter I I and Chapter I I I apply t o non-simple graphs as w e l l . Also we note t h a t a non—simple graph can be viewed as a symmetric weighted digraph i n which the weight on the l i n e from u to v i s ^ { u , v ) . 4. 3 The Graph. Isomorphism Problem The r e l a t i o n s h i p between the automorphism p a r t i t i o n i n g problem and graph isomorphism problem w i l l be d i s c u s s e d i n t h i s s e c t i o n . F i r s t , we assume t h a t we have an al g o r i t h m t o f i n d the automorphism p a r t i t i o n i n g of a graph; then we w i l l show how to use the a l g o r i t h m t o s o l v e graph isomorphism problems. Le t G, and G 2 be two a r b i t r a r i l y chosen graphs. Since components of G, must correspond to components of G 2 whenever G, and G 2 are isomorphic, i t s u f f i c e s to c o n s i d e r the case when G, and G 2 are both connected. Let G, U G 2 = G. Then G, = G 2 i f and o n l y i f each o r b i t of T(G} c o n t a i n s elements of V(G,) and V ( G 2 ) . Now assume t h a t we have an a l g o r i t h m t o s o l v e the 79 graph isomorphism problem. For any two v e r t i c e s x, y of a graph G, form the graph G x with two types of l a b e l s by a s s i g n i n g x l a b e l 1 and the other v e r t i c e s of G l a b e l 2. G^ i s formed s i m i l a r l y . Then x ~ y i f f G x = G^. The o r b i t c o n t a i n i n g x w i l l be the s e t of a l l v e r t i c e s s i m i l a r to x. The other o r b i t s w i l l be c o n s t r u c t e d s i m i l a r l y . Hence we can o b t a i n the automorphism p a r t i t i o n i n g of a graph by means of an al g o r i t h m f o r t e s t i n g whether two graphs are isomorphic. A l s o note t h a t when two graphs are isomorphic then t h e i r o r b i t - d i g r a p h s , d e f i n e d i n S e c t i o n 3.2, w i l l a l s o be isomorphic. Hence comparing the o r b i t - d i g r a p h s w i l l act as a f i l t e r t o screen out non-isomorphic graphs when t e s t i n g whether two given graphs are isomorphic. 4 • 4 A l g o r i t h m i c C o n s i d e r a t i o n s He w i l l now d e s c r i b e an al g o r i t h m f o r c o n s t r u c t i n g the automorphism p a r t i t i o n i n g of a graph. The f o l l o w i n g i s an o u t l i n e o f the a l g o r i t h m . We w i l l assume t h a t the graph G being c o n s i d e r e d i s a f i n i t e simple graph. Extensions t o d e a l with other graphs can be done by s l i g h t m o d i f i c a t i o n s . Step 1: F i n d the c h a r a c t e r i s t i c polynomial f (G) i n f a c t o r i s e d form. Step__2: L e t f(G) have k-t f a c t o r s of degree i . Note t h a t ! I 80 n, where n i s the order of G. i F i n d the s e t MP = {I i * * L : Si are i n t e g e r s , 0 < SL < k t } \ { 0 f n ) . i i . e . the s e t o f the degrees of a l l p o s s i b l e n o n t r i v i a l f a c t o r i z a t i o n s of f (G) . Le t P be the t r i v i a l p a r t i t i o n i n g , H = {e}. Step 3: L e t p be the maximum value i n HP. Merge c e l l s i n P so as to make the number of c e l l s equal t o p. C a l l t h e new p a r t i t i o n i n g P». Step <f: Check the f o l l o w i n g c o n d i t i o n : {*) For every p a i r of d i s t i n c t v e r t i c e s u, v i n the same c e l l C,, the number of v e r t i c e s i n a c e l l C 2 t h a t are adjacent t o u - the number o f v e r t i c e s i n C 2 adjacent to v. Here we may have C 2 = C, . I f (*) holds, go to Step 6. Ste__5: I f a l l p a r t i t i o n i n g s with p c e l l s obtained from P by merging c e l l s have been checked, go t o Step 7. I f not, r e p l a c e P f by another p a r t i t i o n i n g with p c e l l s o b t ained from P by merging c e l l s . Go to Step 4. Ste2_6: Search f o r an automorphism f of G such t h a t <H, <r> w i l l have P» as the set of o r b i t s . I f t h e r e e x i s t s such a <r, set H to <H, <r>, s e t NP to NP\(p}, set 81 P to P», and go to Step 3. I f not, go to Step 5. Step 7: If p = minimum value i n NP, stop with P the automorphism p a r t i t i o n i n g of G. I f not, set NP to NP\fp) , and go to Step 3. , We w i l l i l l u s t r a t e the algorithm by the following example. Example ft.2 Consider the graph G as shown i n Figure 3.2. The algorithm, when applied to G, w i l l run as follows: Step_1: f (G) = x(x • 1 ) 2 { x 2 - 2x - 6). Step_2:k, = 3, k z = 1, NP = (1, 2, 3, 4), P = H ) , {2}, {3}, f4}, {5}; H = fe} . Step 3: p = 4, P' = {1, 2), {3}, f4} i s a pa r t i t i o n i n g obtained from P by merging c e l l s and the number of c e l l s i n P» i s 4. Step .4: 1 and 2 are adjacent to 3, 4 and 5; 1 and 2 are not adjacent, hence the condition (*) i s s a t i s f i e d . Step..6: The only possible candidate i s (12) and t h i s i s 82 indeed an automorphism; hence H = <{12) >, NF = {1, 2, 3}, P = [1, 2}, {3}, {4}, [5). Ste__3: p = 3, P' = (1, 2, 3}, {4}, {5} i s a p a r t i t i o n i n g with t h r e e c e l l s obtained from P by merging c e l l s . _ te__4: In {1, 2, 3}, 3 i s adjacent to 1 and 2 but 2 i s adjacent t o 3 only; hence (*) i s v i o l a t e d . Step 5: V1 - {1, 2, 4}, [3}, {5} i s another p a r t i t i o n i n g with t h r e e c e l l s o b t ained from P by merging c e l l s . Step 4; In p , 2, 4}, 4 i s adjacent to 1 and 2 but 2 i s adjacent t o 4 only, hence (*) i s v i o l a t e d . Step, 5; P f = {1, 2, 5}, {3}, {4} i s another c a n d i d a t e p a r t i t i o n i n g . Step 4: {*) i s v i o l a t e d when comparing v e r t i c e s 2 and 5 i n the c e l l {1, 2, 5} . SteE_5: P' = (1, 2}, (3, 4}, (5} i s another candidate p a r t i t i o n i n g . ______: 1 and 2 are both adjacent to 3, 4 and 5. 3 and 4 are both adjacent to 1, 2 and 5. Hence (*) i s s a t i s f i e d . Ste__6: (34) i s an automorphism t h a t s a t i s f i e s the requirements; he^ce H = <(12) , (34)>, NP = {1, 2}, 83 P = (1, 2} , {3, 4} , {5}. Step 3: p = 2, P' = {1, 2, 3, 4}, {5} i s a candidate p a r t i t i o n i n g . Step 4: (*) i s v i o l a t e d when comparing v e r t i c e s 2 and 4 i n c e l l {1, 2, 3, 4}. Step_5: P» = (1, 2, 5}, {3, 4} i s another candidate p a r t i t i o n i n g . Step_4: (*) i s v i o l a t e d when comparing v e r t i c e s 2 and 5 i n c e l l (1, 2,5}. Step_5: P' = (1, 2}, {3, 4, 5} i s another candidate p a r t i t i o n i n g . Step_4: 1 and 2 are both adjacent to 3, 4 and 5. 3, 4 and 5 are a l l adjacent to 1 and 2. Hence (*) i s s a t i s f i e d . Step 6: (354) i s an automorphism t h a t s a t i s f i e s the requirements; hence H = <{12) , (34) , (354) >, NP = {1}, P = (1, 2} , {3, 4, 5}. Step 3: p = 1, P' = (1, 2, 3, 4, 5} i s the only candidate p a r t i t i o n i n g . Step_4; (*) i s v i o l a t e d when comparing 2 and 5 i n c e l l {1, 2, 3, 4, 5}. Step_5: The only p a r t i t i o n i n g with one c e l l obtained from merging c e l l s i n P has been checked. 84 Ste__7: p = 1 = minimum value in HP, hence P = {1, 2), [3, 4, 5} i s the automorphism p a r t i t i o n i n g of G. We w i l l now consider the number of operations required for the algorithm. As noted i n [20, p.56 0], the c h a r a c t e r i s t i c polynomial of a matrix can be found i n 0 ( n 3 - 3 1 ) operations. The f a c t o r i z a t i o n of the c h a r a c t e r i s t i c polynomial presents some problems. However, we note that the f a c t o r i z a t i o n of a polynomial over GF(p), where p i s a prime, can be done in 0(n 3(log p) 2 • n 2 (log p) 3 ) operations. These fa c t o r i z a t i o n s w i l l then give some idea of the possible fa c t o r i z a t i o n of the polynomial over the integers. This process does not y i e l d a polynomial bounded algorithm for complete f a c t o r i z a t i o n of a polynomial over the integers. However, since we are only interested i n the degrees of possible f a c t o r i z a t i o n s , we may stop t h i s process when the number of primes considered i s too large. The most time consuming operations are Step 4 and Step 6. The number of partitionings that have to be considered i n Step 4 depends on the f a c t o r i z a t i o n s of the c h a r a c t e r i s t i c polynomial and the structure of the automorphism group. The worst case occurs when the automorphism group of a graph G does not contain any n o n t r i v i a l subgroups and the c h a r a c t e r i s t i c polynomial of G i s completely reducible into l i n e a r factors. In t h i s 85 case we may have to check over a l l p a r t i t i o n i n g s t h at r e f i n e the automorphism p a r t i t i o n i n g and then search f o r a generator of the automorphism group. The search f o r an automorphism i n Step 6 can be done by f i r s t making an assignment which i s i m p o s s i b l e i n the pr e v i o u s a d m i s s i b l e p a r t i t i o n i n g . T h i s w i l l reduce t h e number of o p e r a t i o n s r e q u i r e d t o f i n d an automorphism. A l i s t of the automorphism p a r t i t i o n i n g s of simple connected graphs with not more than s i x v e r t i c e s i s given i n Table V of the Appendix. 4.5 C o n c l u s i o n He have e s t a b l i s h e d some connections between the automorphism group of a graph and i t s c h a r a c t e r i s t i c polynomial. We have seen how the r e d u c i b i l i t y of the minimal polynomial of a graph r e f l e c t s the p r o p e r t i e s of the graph and i t s automorphism group. We have a l s o s t u d i e d t h e r e l a t i o n s h i p between the number of o r b i t s of a subgroup of t h e automorphism group of a graph and the f a c t o r i z a t i o n of i t s c h a r a c t e r i s t i c polynomial. Although the r e s u l t s have been proved f o r simple graphs, e x t e n s i o n s t o other graphs are immediate. He have a l s o c o n s i d e r e d an algorithm to c o n s t r u c t the automorphism p a r t i t i o n i n g o f a graph by making use of the c h a r a c t e r i s t i c polynomial. The a l g o r i t h m r e g u i r e s the computation o f the c h a r a c t e r i s t i c polynomial and i t s 86 f a c t o r i z a t i o n ; hence the e f f i c i e n c y of the algorithm w i l l also depend on these computations. Also since the f a c t o r i z a t i o n of the c h a r a c t e r i s t i c polynomial i s related to the orbits of the subgroups of the automorphism group, we would expect r e s u l t s on the automorphism group of a graph to a s s i s t i n the exploration of the properties of the c h a r a c t e r i s t i c polynomial, and vice versa. 87 BIBLIOGRAPHY 1. N. Biggs, A l g e b r a i c G r a p h Theory. Cambridge T r a c t s i n Mathematics 67, Cambridge U n i v e r s i t y P r e s s , London, 1974. 2. J . A. Bondy and U. S. R. Murty, Graph_Theory with A p p l i c a t i o n s , Macmillan P r e s s , London and Basingstoke, 1976. 3. C. Y. Chao, A note on the eigenvalues of a graph, J.. Com b i n a t o r i a l Theory Ser. B 10 (1971) . 301 - 302. 4. C. Y. Chao, On groups and graphs, Trans. Amer. Math. Soc^. V18(1965) , 488 - 497. 5. L. C o l l a t z and U.,Sinogowitz, Spektren e n d l i c h e r Graphen, Abh. Math. Sem. Univ. Hamburg 21(1957), 63 - 77. 6. G. C r i s c u o l o , C M . Kwok, A. Mowshowitz and R. T o ^ t o r a , Some Connections between the Minimal Polynomial and the Automorphism Group of a Graph, T e c h n i c a l Report 77-18, Department of Computer S c i e n c e , U n i v e r s i t y of B r i t i s h Columbia, Vancouver, 1977. 7. D. M. C v e t k o v i c , Graphs and t h e i r s p e c t r a , Univ.,TBeograd Publ. E l e k t r o t e h n . Fak. Ser. Mat. F i z . 354_-_356 (1971), 1 - 5 0 . 8. G. Debreu and I. N. H e r s t e i n , Nonnegative sguare m a t r i c e s , Iconometrica 21(1953), 597 - 607. 9. N. Deo, Graph Theory witij^ABBlisatloPs.to^Ejtgln^erigg.ana-Computer_Science, P r e n t i c e - H a l l , Engiewood C l i f f s , N. J . , 1974. 88 10. R. Frucht, Graphs of degree three with a g i v e n a b s t r a c t group, Canad______ath_ 1(1949), 365 - 378. 11. R. Frucht, Herstelung von Graphen n i t vorgegebener a b s t r a k t e r Gruppe, C^)_p_.sito_Math_ 6 (1938) , 239 - 250. 12. R. Frucht, J . E. Grayer and M. E. Watkins, The groups of the g e n e r a l i z e d Petersen graphs, Proc. Cambridge P h i l p s . Soc_ 70(1971), 211 - 218. 13. F. R. Gantmacher, The Theory o f . M a t r i c e s , Vol. 1 and 2, C h e l s e a , New York, 1959. 14. F. Harary, The determinant of the adjacency matrix of a graph, SIA___ev_ 4(1962), 202 - 210., 15. F. Harary, Four d i f f i c u l t unsolved problems i n graph t h e o r y , i n : Recent Advances i n Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, 249 - 256. 16. F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969. 17. F. Harary, C. King, A. Mowshowitz and R. C. ,Read, C o s p e c t r a l graphs and d i g r a p h s . B u l l . London Math._ Soc^ 3(1971), 321 - 328. 18. F. Harary and E. M. Palmer, On the automorphism group of a composite graph, S t u d i a S c i . Math. Hungar. 3(1968), 439 -441. 19. F. Harary and A. J . Schwenk, Which graphs have i n t e g r a l s p e c t r a ? , i n : L e c t u r e ,,,No t es in_M at he ma t i c s 4 06l S£a_bs_and Combinatorics, 45 - 51. 20. D. E. Knuth, The A r t of C: p m pu t e„ _ P r pgr a m m i n_, V o l . 2, 89 Addison-Wesley, Reading, Massachusetts, 1969. 21. D. KSnig, Theorie,.der_endliche_n_und_un , Akademie V e r l a g , L e i p z i g , 1936 and C h e l s e a , New York, 1950. 22. 7. Krishnaraoorthy and K. R. Parthasarathy, C o s p e c t r a l graphs and digraphs with given automorphism group, J.. C o m b i n a t o r i a l T h e o r y Ser. B .19(1975), 204 - 213. 23. H. Marcus and H. Mine, A S u r v e y o f Matrix^Theory and Matrix I neguaj.it i e s , A l l y n and Bacon, Boston, 1964. 24. A. Mowshowitz, The adjacency matrix and the group of a graph, i n : New D i r e c t i o n s i n the Theory of Graphs (ed. F. Harary), Academic P r e s s , New York, 1973. 25. A. Mowshowitz, The c h a r a c t e r i s t i c polynomial o f a graph, J.. C o m b i n a t o r i a l Theory Ser. B VI (1 972) , 177 - 193. 26. A. Mowshowitz, Graphs, groups and ma t r i c e s , i n : Proceedings of the Canadian Mathematical Congress (June 1971) , 509 -522. 27. A. Mowshowitz, The group of a graph whose adjacency matrix has a l l d i s t i n c t e i g e n v a l u e s , i n : P r o o f _ T e c h n i g u e s _ i n Graph Theory (ed. Harary), Academic Press, New York, 1969, 109 - 110. 28. 0. Ore, Theory pf.Graphs, Amer. Math. Soc. C o l l o g . Publ. 38, Providence, 1962. 29. E. M. Palmer, The e x p o n e n t i a t i o n group as the automorphism group of a graph. Proof Technigues j n Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, 1969, 125 - 131. 90 30. G. C. E. Prins, On the Automorphism Group of a Tree, Ph. D. Thesis, University of Michigan, 1957. 31. J. Riordan, An Introduction _p_Cpmbinatprial Analysis, John Riley 5 Sons, 1958. 32. G. Sabidussi, Graph m u l t i p l i c a t i o n , Ma_k____ 72(1960), 446 -457. 33. G. Sabidussi, Graphs with given group and given graph t h e o r e t i c a l properties, Can.ady_J, Math. 9(1957), 515 -525. 34. H. Sachs, Dber selbstkomplementare Graphen, Ptibl,. Math. Debreccen 9(1962) , 270 - 288. 35. A. J. Schwenk, Computing the ch a r a c t e r i s t i c polynomial of a graph, i n : Lecture Notes i n Mathematics 406_ Graphs_and Combinatorics, 153-172. 36. J. H. Smith, Some properties of the spectrum of a graph, i n : Combinatorial Structures and their_Applications (R. K. Guy, et. a l . , eds.) , Gordon and Breach, New York, 1970, 403 - 406. 37. L. Sp i a l t e r , The atom connectivity matrix and i t s ch a r a c t e r i s t i c polynomial, J__Chem__np^umej_t 4(1964), 261 - 274; J__A_er__C_____Spc_ 85(1963), 2012 - 2013. 38. D. A. Suprunenko and R. I. Tyshkevich, Commutatiye Matrices, Academic Press, New York, 1968. 39. E. H. Sussenguth, A graph theoretic algorithm f o r matching chemical structures, J. Chem. Documentation 5(1965), 36 -43. 40. P. M. Weichsel, A note on asymmetric graphs, Israel_J_> Mlhi. 10 (1971) , 234 - 243. 91 41, P. J . Hilson, On the adjacency matrix of a graph, i n : Combinatorics (Proc. of the Conference on Combinatorial Hath,, held at the Hath..Institute, Oxford, 1972, edited by D. J. A. Welsh and D. H. Woodall), Inst. Math. Appl., Southend-on-Sea, 1972, 295 - 321. 42. H. P. Yap, The c h a r a c t e r i s t i c polynomial of the adjacency matrix of a multi-digraph, Ianta_Matlu 8(1975), 41 - 46. APPENDIX Ta b l e _ I Spectra of Simple Connected Graphs up__to n_=_6_Vgrtices !--+-Graph T T 1 Index J Other values of the spectrum J 1 -1 | +-T " I A 1. 4142* 0 A -1 1.6180 1.7321 0.6180 -1.4142 -1 -0.6180 -1.6180 -1.7321 2. 1701 0.3111 -1 -2 -1.4812 2.5616 -1 -1.5616 -1 -1 -1 15 I L 1.7321 -1 -1.7321 * N o n — i n t e g r a l values are rounded to 4 decimal p l a c e s . i — r -Graph J Index | Other values of the spectrum j — T 1 T r T ^ -A-1. 84 78 0.7654 0 -0.7654 -1.8478 -2 ^7 2. 1358 2. 21 43 2. 30 28 2. 3429 0.6180 0.6622 0.6180 -1.6180 -0.6622 -0.5392 0.6180 0. 4707 -1 -1.3028 -1 -1.6180 -2.1358 -1.6751 -1.6180 -1.8136 2.44 95 2.4812 2.5616 2.6412 2.6855 0.6889 0.7237 0. 3349 -1 -0.5892 -1.1701 -1 -1 -1.2713 -2.4495 -2 -1.5616 -1.7757 -1.7491 i x . I — T T 1~ n | Graph | Index 1 Other values o f the spectrum I 2 • 8558 2. 9354 3.0861 0.3216 0.6180 0.4280 -0.4626 -1 -1 -1.4728 -1 -1 -2.1774 -1.6180 -2 -1.5141 3.2361 3.3234 0.3579 -1 -1.2361 -1 -2 -1.6813 + 3. 6458 -1 -1 -1.6458 -1 -1 -1 -1 c J A \ 1.8019 1.9021 1.9319 1.2470 1.1756 0.4450 -0.4450 -1.2470 •1. 1756 0.5176 -0.5176 -1 -1 I L -1.8019 -1.9021 -1.9319 -2 95 S I T 1 1 |n| Graph | Index \ Other values of the spectrum \ T T r r T 1 + 2.07 43 2.2361 0.8350 0 4--0.8350 -2.0743 -2.2361 o <_> ci -1 -1 2. 1149 2. 1753 2.2283 2.2361 2.2470 2.2784 2.2882 2.3342 2. 3799 0.6180 -0.2541 1.1260 1. 3604 -1.6180 -1.1260 0.1859 -1 -1 -1 0.8019 1.3174 0.8740 1. 0996 0.5550 -0.5550 -0.7046 0. 274 2 0.2914 -0.5945 -0.7510 -0.8019 -1 -0.8740 -1.3738 -1 -2 -1.8608 -2.1753 -1.7746 -2.2361 -2.2470 -1.8912 -2.2882 -1.7397 -1.9202 96 I — T 1 "1 n| Graph | Index | Other values of the spectrum H T T 1 1 1 1 A < 2.4142 2.4458 2.5141 2.3914 2. 4142 2. 4142 2.4383 2.5035 2. 5243 2.5.3 95 2.5576 2. 5616 0.6180 0.7968 0.5720 0.7729 1.7321 1.1386 1.2644 0.7923 1.0825 0.6772 0.6180 0.6180 0.4142 -0.4142 0.6180 0.2611 -0.4142 -0.4142 -1 •0.8202 -0.5767 -0.5406 -1.6180 -1.3703 -1 -1.6180 -1 -1 -1.6180 -1 -0.7923 -1.2061 -0.6772 -1.5616 -1.6180! -1.87231 -2.0861 i x . -2.16421 -2.4142i -1.7321 -1.75661 -2.1911 -2.5243! -2.1364! -2.5576! -2 j 97 I T"" In T T J Graph | Index | Other values of the spectrum J -I T : r , r 1 X < 3 i 4 Y A 2.5991 2. 62 87 2.6554 2.7056 2.7093 2.7093 2.7321 2.7537 2.7913 2.8136 2.73 21 2.7321 0.7661 1.2297 1.2108 1.0561 0.7727 0.6180 0.5293 0. 7321 1. 4142 0.4669 0.1397 0.1939 0.1939 0 0.3064 -0.3848 -1 -1 -0.5600 -1 -1 -0.7321 -0.6093 -0.7321 -1, 3053 -1.3198 -1 -1.3504 -1 -1 -1 -1.3293 -1.6180 -1.34 29 -0.7321 -1.4142 -2.1420 -1.6783 -1.8662 -1.8513 -1.9032 -1.9032 -2 -1.8942 -1.7913 -2 — I -2.7321 -2 98 ) rt f Graph 1 T 1 Index | Other values of the spectrum \ ' T 1 1 "I 1 + 4S> 2.7411 2.79 13 2.7964 2.8136 2 . 8 2 8 4 2.84 22 2.8529 2.8951 2.9032 2. 9327 2. 9439 2.9474 I 0.71031 0.6180) -0.2314 -1.6180 -2.22001 1 1 I 0.61801 -1 -1.6180 -1.7913} | 0.8532j 0 I 0 1-1. 1955 -2.4541J I 1 I 0.52931 -1 -1.3429 -2 | I 0 | 0 j 0 0 -2.8284J | 1. 5069| -0.5069 -1 -1 -1.8422J 1 1. 0554| 0. 1830| -0.6611 -1.2718 -2.1584} 1 1 I 0 1 -0.6027 f -1 -2.2924} | 0. 8061| 0 1 0 -1.7093 -2 | I 0.72721 0. 3088| -0.6 570 -1 -2.31171 J 0.6648| 0 ! 0 -1.3684 -2.24031 | 1.15931 0 ! -1 -1.2859 -1.8208J 99 I — T T T * § xi | Graph | Index | Other values of the spectrum I J L , , —1 "J 1 1-2.9809 3 . 0 1 1 3 3.04 37 3.0478 3.0965 3. 1020 3. 1642 3, 1774 3.0868 3.0922 1. 0420 0.8481 0.6 180 0.8214 1.1169 0.3443 0.6180 0.6784 1. 1558 0.7020 0 0. 1967 0.3285 -0.5089 0.2271 0.1096 -0.7062 -0.7248 -0.5482 -0.7562 -1 -1 -1 -1 -1.5371 -1.4780 -1.6180 -1 -1 -1.3228 -1.3914 -1 -2 -1.1736 -1.2855 -1.7796 -1.8563 -1.8241 -2.1129 -1.7045 -2.1235 -1.6180 -1.8558 -3 -2 -2.1787 •2.5086 100 i — r 1 •» 1 n| Graph | Index | Other values of the spectrum \ — H 1 1 1 1 1 1 f -13.1149 | 0.7459] 0.61801 -0.8608 -1.61801 -2 1 |3.1413 | 0.4849! o i 0 -1 I - 2 . 6262! | 3. 16 92 I 0.7282I 0.2798! -0.4663 -1.50581 - 2 . 2052J | 3.1819 | 1.24701 -0.4450 -0.5936 -1.58 84] - 1 . 80191 | 3.18 88 J 0.83471 0 \ -0.6272 -1 ! - 2 . 3962| I 3.2227 1 1 I 0.1124' -1 -1.5266! - 1 . 80851 ! 3.2 361 | 0.6180] 0.6180! -1.2361 -1 .6180! - 1 . 6180J | 3.2361 1 1 I 0 -1 -1.23 61 2 1 I 3.2618 I 1.3399| -1 -1 -1 - 1 . 6017J | 3. 2814 | 0.77191 0 -0.5125 -1.5408 2 1 I 3.2948 J 0.73471 0 -0.5975 -1.2927 - 2 . 1392) | 3.3234 10.3579 ] 0 0 -1.6813 2 1 1 L -101 T 1 » n| Graph | Index f Other v a l u e s of the spectrum J _H| 1 1 r —r 1 1 J-3. 3 539 3.3723 3.38 39 3.4037 3. 3723 3. 3885 3.39 23 3.4495 3.4609 3.4679 3.4979 3.5141 1 0.7424 0.4 897 0.8019 0.3254 0.6180 0.3493 0.9128 0.7299 0.6694 -0.4765 0.2512 0.1873 0.6180 0.1505 -1 -1 -1 -1 -0.5550 -1.4495 -0.7989 -1 -0.5284 -1 -1 -1.3279 -1.2827 -1 -1.5758 -1 -1.6180 -1.3387 -1.5818 -1.1876 -1.4782 -1.8774 -2.3723 -1.7985 -1.8619 -2.3723 -2.2470 -2.7177 -1.6180 -2.4715 -2 -2.1907 -2.1769 102 1 — T 1 T 1 ri 1 Graph 1 Index | Other values of the spectrum — + 1 T » J T 1 13.53 44 j 1. 0827| -0.40711 -1 1-1. 5111| 13.5616 | 1 | -0.5616J -1 1 -1 I | 3. 5926 \ 0.6180! 0.1589| -1 |-1.61801 I3.6262 | 0.51511 0 1 -1 1 -1 I | 3. 69 03 j 0.75341 -0.5784! -1 I -1 I 13.7105 | 0.44081 0 | -1 1-1.3842! | ^ 13.7136 | 0.61801 0 ! -0.4 829 J-1.61801 13.7321 I 0.4142' 0.2679! -1 J -1 | 13.7664 J 0 ! 0 1 0 1-1.2828! 13.7785 | 0.7108! 0 I -1 1-1.98931 13.8201 | 0.4594 0 1 -1 1 -1 I I3.8284 | 1 -1 i -1 I -1 I - 1 . 6 9 9 0 -2 -1.7515 -2.1413 -1.8653 -1.7670 -2.230 7 -2.4142 -2.4836 -2 -2.2795 -1.8284 i ± 103 , — 1 1  Graph | Index j Other va l u e s of the spectrum — + 3. 8590 3.8951 4.0514 0.7792 0.3973 0. 4 827 -0.3791 -1 -1 -1 -1.4758 -1.2924 -1 -1.7832 -2 -1.5341 4.0678 4.1190 4. 1623 4.2015 0. 3616 0. 6180 -0.4316 0. 5451 -1 -1 -1 -1 -1 -2 -1.2446 -1.6180 -1 -1 -2 -2.18481 -1.68741 -2.16231 -1.74661 4.3723 4.4279 0.3757 -1 -1 -1 -1.3723 -1 -2 -1.8035! 4.7016 -1 -1 -1 -1.70161 -1 -1 -1 -1 -1 I L. 104 T a b l e _ l l C h a r a c t e r i s t i c ^ P o l y n o m i a l s of -Simple,••Connected Graphs up to n = 6 _ V e r t i c e s I — T " |n h Graph | C h a r a c t e r i s t i c Polynomial 1 X 2 - 1 = ( X - 1) ( X • 1) A x3 - 2x = x ( x 2 - 2) A x3 - 3x - 2 = {x - 2) ( X + 1) 2 x* - 3x2 + 1 ( X 2 - x - 1) ( X 2 • x x* - 3 x 2 x 2 ( x 2 - 3) - 1) X 4 - 4 X 2 = x 2 (x - 2) <x + 2) x* - 4x 2 - 2x + 1 = (x • 1) <x3 - x 2 - 3x + 1) x* - 5x 2 - 4x = x{x + 1) ( x 2 - x - 4) x* - 6x 2 - 8x - 3 = (x - 3) (x + 1) 3 X 5 - U X 3 + 3x = x(x - 1) ( X + 1) ( X 2 X S - U X 3 • 2x = x{x* - 4x2 + 2) 3) 105 I — T ~ In| Graph 1 C h a r a c t e r i s t i c Polynomial X s - I X 3 = x 3 ( x - 2) {x • 2) xs - 5x3 + 5x - 2 = (x - 2) ( X * + x - 1) 2 x s - 5x3 + 2x = x(x* - 5x2 + 2) X * - 5x 3 - 2x2 + 4x + 2 = (x - 1) (x + 1) (x3 - 4x - 2) xs - 5x3 - 2x2 + 3x = X { X 2 - X - 3) (X2 • X - 1) x« - 5x3 - 2x2 + 2x = X ( X • 1) ( X 3 - x 2 - 4x + 2) xs - 6x 3 = X 3 ( X 2 - 6) X s - 6x 3 - 2x2 • u x = x{x + 2) <x3 - 2x 2 - 2x + 2) x s - 6 X 3 - 4X2 • 5x + 4 = ( X - 1) ( X • 1) 2 ( X 2 - x - 4) x s - 6x3 - 4X2 • 3x • 2 = ( X + 1) (x* - x 3 - 5x2 • x + 2) X s - 6x 3 - 4x 2 + 2x = x(x* - 6x z - 4x • 2) x s - 7 X 3 - n X 2 + 2x = x (x + 1) (x3 - x 2 - 6x + 2) 106 Graph | C h a r a c t e r i s t i c Polynomial x s - 7 X 3 - e x 2 + 3 x + 2 = ( x 2 •• x - 1) ( x 3 - x 2 - 5 x - 2 ) x s - 7 X 3 - 6 x 2 = x 2 (x - 3) (x + 1) {x + 2) x s - 7 X 3 - 8 x 2 + 2 = (x + 1 ) 2 { x 3 - 2 x 2 - 4 x + 2 ) \ -+ X s - 8 x 3 - 8 x 2 = X 2 ( X * 2) ( x 2 - 2 x - 4 ) xs - 8 x 3 - 1 0 x 2 - x + 2 = (x • 1 ) 2 { x 3 - 2 x 2 - 5x + 2) X * - 9x 3 - 14x2 - 6x = X ( X + 1) 2 ( X 2 - 2x - 6) x s - 1 0 X 3 - 20x2 - 15x - 4 = {x - 4 ) (x + 1} • A~\ A K x* - 5 x * • 6x2 _ 1 ( x 3 - x2 - 2x • 1) ( x 3 + x 2 - 2x x* - 5 x * * 5x2 x 2 (x* - 5x2 + 5) x* - 5x* + 5x2 - -j (x - 1) <x + 1) (x* - 4x2 + 1) x 6 - 5x* + 4 x 2 x2 (x - 1) (x + 1) <x - 2) (x + 2) x* - 5 x * + 3x2 x2 <x* - 5x2 + 3) - 1) L _ l _ 1 0 7 I — T " |n| Graph | r H T C h a r a c t e r i s t i c Polynomial I -+ •5^  x * - 5 x * = x * ( x 2 - 5) o < i x * - 6 x * *• 9x2 - 4 = (x - 1 )2 *x «- 1 ) 2 < x - 2) {x + 2} x * - 6 x * + 8x2 - 2x - 1 = (x - 1} ( x 2 + x - 1) <x3 - 4 x - 1) x * - 6 x * * 6 x 2 = x 2 ( x « - 6 x 2 • 6) x * - 6 x * - 2 x 3 • 8 x 2 + 4 x - 1 = (x + 1 ) 2 ( x * - 2 x 3 - 3 X a + 6x - 1) x 6 - 6 x * • 5 x 2 = x 2 (x - 1) (x • 1) ( x 2 - 5} x 6 - 6 x * • 5x2 - 1 = (X3 - 2x2 - x + 1) ( x3 * 2 x 2 - x - 1) X 6 - 6x* - 2 x 3 + 7 X 2 + u x = x ( x • 1) ( x * - x 3 - 5 x 2 + 3 x • 4) x « - 6 x * * 4 x 2 = x 2 ( x * - 6 x 2 4- 4) x * - 6 x * - 2 x 3 • 7 X 2 + 2x - 1 x * - 6 x * - 2 x 3 • g X 2 + 2 x - 1 = ( x - 1) {x • 1) ( x « - 5 x 2 - 2x + 1) x * - 6 x » - 2 x 3 + 6 x 2 - 1 = ( x 2 - 2x - 1) < x 2 • x - 1 ) 2 108 In| Graph \—\ — C h a r a c t e r i s t i c Polynomial I -+ x* - 6x* - 2x3 + 5 X 2 = x 2 <x« - 6x 2 - 2x •• 5) x* - 6x* - 2x3 + 3 x a = x 2 ( x + 1) <x3 - x z - 5x + 3) x 6 - 7x* + 9 x 2 - 4x = x{x 2 * x - 1) (x3 - x 2 - 5x + 4) x* - 7x* + 7x 2 - 1 = (x - 1) (x + 1) ( x 2 - 2x - 1) ( x 2 + 2x - 1) x s - 7 X 4 - 4 X 3 * 1 1 X 2 + -|2x + 3 - (x • 1 ) 2 ( x 2 - 3) ( x 2 - 2x - 1) x* - 7x» - 2x3 + i r X 2 + 2x - 4 = <x2 • x - 1) {x* - x3 - 5x 2 2x • 4) x* - 7x* - 2x3 + 8x 2 • 4x = x(x * 1) <x* - x3 - 6x 2 • 4x + 4) x 6 - 7x* + 4x 2 = x 2 (x* - 7 x 2 • 4) x s _ 7 X* _ 2x3 + 8x 2 + 2x - 1 x* - 7x* + 3x 2 = x 2 (x* - 7 x 2 + 3) x* - 7x* - 2x3 + 8x 2 = x 2 (x - 1) (x + 2) ( x 2 - x - 4) X 6 - 7 X 4 - 2x3 * 7 X 2 - 1 109 I T" |nj Graph V—I C h a r a c t e r i s t i c Polynomial i d 4S> A Y x* - 7x* - 4x3 + 9x2 + 6x - 1 |= (x + 1) (xs - x* - 6x3 • 2x 2 + 7x - 1) x* - 7x* - 4x3 + 8x2 + 6x = x(x • 1 ) 2 ( x 3 - 2x 2 - 4x • 6) x* - 7x* - 4x3 + 7x2 • 4x i = x ( x s - 7x 3 - 4x 2 + 7x + 4) x* - 7x* - 4x3 • 7x2 + 4x - 1 = ( X - 1) ( X + 1 )2(x 3 - X 2 - 5X + 1) x* - 7x* - 4x3 + 7x2 + 4x - 1 | = ( X - 1) <X + 1 ) 2 ( X 3 - X 2 - 5 X + 1) x* - 7x* - 4x3 + 6x2 + nx |= x{x - 1) (x + 1) (x + 2) <x2 - 2x - 2) x* - 7x* - 4x3 * 6x2 * 2x - 1 X 6 - 7x* - 4x3 + 5x2 X 2 ( X 2 + X - 1) <X2 - X - 5) X 6 _ 7 X 4 - 4x3 + I x 2 x2 {x + 2) ( x 3 - 2x2 - 3X + 2) x 6 - 8x* +4x2 | = X 2 ( X 2 - 2x - 2) (x2 2x - 2) x* - 8x* - 4x 3 • 12x2 • 8x = x(x • 2) (x2 - 2) (x2 - 2x - 2) x* - 8x* - 2x 3 + 10x2 - 2x - 1 |= ( x 2 • x - 1) (x* - x 3 - 6x 2 + 3x + 1) i L-110 Graph •T~ I C h a r a c t e r i s t i c Polynomial 43 X 6 _ 8x* - 4x3 + 12x2 + 4x - 5 (x - 1) (x + 1) <x2 • x - 1) ( x 2 - x - 5) x« - 8x* - 2x3 + 7 X 2 x 2 (x* - 8 x 2 - 2x + 7) x* - 8x* - 4x3 • 11 X 2 + 4x - 4 (x - 1} {x • 1) (x + 2) ( x 3 - 2x2 - 3x + 2) x« - 8x* X * ( X 2 - 8) X * - 8 X * - 6X3 + 11x2 *. 14 X • 4 ( X • 1)2 (x* - 2x3 - 5 X 2 + 6x + 4) x 6 - 8 x * - 4x3 • 9x2 • 4x - 1 x« - 8 x * - 4 x 3 • 7x2 + 4x x(x - 1) (x • 1) ( x 3 - 7x - 4) x* - 8 x * - 4x3 • 8 x 2 x2 (x * 2) ( x 3 - 2x2 - 4x + 4) x* - 8 x * - 4x3 • 6x2 + 2x - 1 (x • 1) (xs - x* - 7x3 + 3x2 + 3x - 1) x* - 8 x * - 4x3 + 6 x 2 x2 (x* - 8x2 - 4x + 6) x* - 8 x * - 6 x 3 + 9 X 2 + 8x X ( X * 1) ( X * - x 3 - 7x2 + X + 8) x« - 8 x * - 6 x 3 + 8 x 2 + 6x x(x« - 8x3 - 6x2 + 8x + 6) f I L -111 I T |n| Graph | H T-C h a r a c t e r i s t i c Polynomial i I 4 ^ X 6 - 8 x * - 6 x 3 + 7 X 2 • 4 x - 1 x* - 8 x * - 6 x 3 + 6 x 2 + 2x - 1 = ( X 2 + X - 1) ( X » - X3 - 6 x 2 - X • 1) x* - 8x* - 6 x 3 + 5 x 2 + 4 x = X ( X * 1) f X * - X 3 - 7X2 + X • 4 ) x* - 8 x * - 8x3 + 6 X 2 + - J O X • 3 = (X * 1 ) 2 ( x * - 2x3 - 5 X 2 • 4 X + 3 ) x 6 - 8x* - 6 x 3 + 3 x 2 = x 2 (x* - 8 x 2 - 6 x + 3 ) x* - 8 x * - 8 x 3 + 4 x 2 + 4 x - 1 = (X + 1) ( x 2 + x - 1) ( X3 - 2 x 2 _ 4 X + 1) x* - 8 x * - 8 x 3 + 3 x 2 + 4 x = X<X • 1 ) 2 { X 3 - 2X2 - 5 x + 4) x* - 9 x * x* <x - 3) (x • 3 ) x* - 9 x « - 4 x 3 +- 1 2 x 2 x 2 (x - 1) (x - 3 ) <X • 2 ) 2 X * - 9 X 4 - 6 x 3 • 1 1 x 2 + 8 x - 1 (x + 1) (x« - x* - 8 x 3 + 2 x 2 * 9 x - 1) X 6 - 9 X * - q X 3 *• 7 X 2 x 2 ( x * - 9 x 2 - 4 x + 7 ) x* - 9 x * - 6 x 3 + 1 1 x 2 • 4 x - 4 (x • 2) <x* • x - 1) Cx 3 - 3 x 2 - x • 2) I n! Graph C h a r a c t e r i s t i c Polynomial x* - 9x* - 4x 3 • 4x 2 x 2 (x + 1) ( x 3 - x 2 - 8x + 4) x* - 9x* - 6x 3 • 8x 2 + 2x - 1 x 6 - 9x* - 8x 3 • 10x 2 + 12x • 3 ( x 3 - x 2 - 6x - 3) ( x 3 • x 2 - 2x - 1) x* - 9x* - 6x 3 + 6 x 2 + 4x x (x + 1) (x* - x 3 - 8x 2 2x * 4) x 6 - 9x* - 8x 3 *• 9x 2 + 8x - 1 (x - 1) (x * 1) (x* - 8x 2 - 8x • 1) x* - 9x* - 8x 3 + 9x 2 • 6x - 4 ( x 2 - 2x - 4 ) ( x 2 • x - 1 ) 2 x 6 - 9x* - 8x 3 * 8x 2 * 8x x(x - 1) (x • 1) (x • .2) ( x 2 - 2x - 4) X 6 - 9 X* - 1 0 X 3 * 9x 2 + 18x • 7 (x + 1 ) 3 ( x 3 - 3x 2 - 3x + 7) x e _ g x * _ 8x 3 * 6x 2 + 4x x{x + 2) (x* - 2x 3 - 5x 2 + 2x + 2) x 6 - 9x* - 8x 3 • 5x 2 + 4x x{x* - 9x 3 - 8x 2 + 5x + 4) x e - g x * _ Qx 3 + 4x 2 x 2{x + 2) ( x 3 - 2x 2 - 5x • 2} x 6 - 9x* - 10x 3 + 5 x 2 + 10x «• 3 (x - 1) (x + 1 ) 2 { x 3 - x 2 - 7x - 3) i a_ 113 I T " | B | Graph f~+- — C h a r a c t e r i s t i c P o l y n o a i a l * — + X 6 _ g x * ._ g X 3 X3 (X + 1) ( x 2 - x - 8) x 6 - 9 x * - 10x 3 + 4 x 2 • 6x x{x + 1) (x* - x3 - 8 x 2 — 2x • 6) x 6 - 9 x * - 10x 3 • 3 x 2 • 4x - 1 {x + 1) (xs - x* - 8x3 - 2 x 2 5x - 1) x 6 - 10x* - 8 x 3 + 9 x z • 8x x(x - 1) (x + 1) 2 {x 2 - x - 8) x* - 10x* - 8x3 + 9 x 2 + 4x - 1 ( x 3 - 2x2 - 5x + 1)(X3 + 2x2 - x - 1) x* - 10x* - 6x3 • 3 X 2 X2 (X + 1) <X3 - X 2 - 9X + 3) x* - 10x* - 10x3 + 10x2 + 8x - 5 {x 2 - 2x - 5) ( x 2 + x - 1 ) 2 x 6 - 10x* - 8 x 3 + 4 x 2 x 2 (x* - 10x 2 - 8x + U) x e - - J O X * - 10x3 + 8 x 2 + 8x x(x + 2) (x* - 2x3 - 6x 2 + 2x + H) x« - 10x» - 10x3 • 6x2 + 6x - 1 {x * 1) ( x s - x * - g X 3 - X 2 + 7 X - 1) x 6 - 10x* - 10x 3 + 5x2 * 4x X(X5 - 10X3 - 10X2 + 5X + U) X 6 - i o x * - 12x3 • 7 X 2 + l a x + U {x • 1) (xs - x* - 9 x 3 - 3 x 2 • 10X + 4) 114 Graph C h a r a c t e r i s t i c Polynomial x* - 10x* - 12x3 • 5 X 2 + 12X + 4 (x - 1) (x + 2) (x • 1) 2(x2 - 3x - 2) x« - 10x* - 12x3 + 4x2 + 6x - 1 (X • 1) ( x 2 + x - 1) ( X 3 - 2x2 - g x + 1 } x 6 - 10x* - 1 2 x 3 - x2 • 4x x ( x + 1 ) 2 ( x 3 - 2x2 - 7 X + n) x* - 10x* - 14x3 + 8x • 3 (X • 1 )2(x* - 2x3 - 7 X 2 • 2x + 3) x* - 10x* - 1 4 x 3 - x 2 + 4x x ( x + 1) <x* - x3 - 9 x 2 - 5x + 4) t x 6 - 11x* - 1 2 x 3 + 5 x 2 + 4x = x ( x 2 • x - 1) ( x 3 - x 2 - 9x - 4) X 6 - 1 1 x 4 - 12x3 • 3x2 + 4x - 1 = (x • 1 ) 2 . x 2 • 2x - 1 ) ( x 2 - 4x • 1) x* - 11x* - 12x3 = X 3 ( X 3 - 1 1 X - 12) x 6 - 11x* - 14x3 • 4 x 2 * 8x = x ( x + 1) {x * 2) (x3 - 3 x 2 - 4x • 4) x 6 - 11x* - 14x3 + a.x = X ( X + 1 ) 2 ( X 3 - 2x2 - 8x • 4) X 6 - 1 1 X 4 - 1 6 X 3 • 3 X 2 • I 6 x * 7 = (x - 1) (X • 1)3{x2 - 2x - 7) x» - 11x* - 16x3 • X2 *- 10x *• 3 = (x + 1) ( X S - x * - 10x3 - 6x2 • 7 x • 3) I A -r — T - Graph T " C h a r a c t e r i s t i c Polynomial X 6 _ ii x» - 16x3 - 2x2 + nx - x(x + 1) (x + 2) ( x 3 - 3x 2 - 4x + 2) x 6 - 11x* - 20x3 _ g X 2 * 4x • 3 = (x + 1 ) 3 < X 3 - 3x« - 5x + 3) x* - 12x* - 16x3 = X 3 (X - 4) (X + 2) 2 X 6 - 12 X* - 18x3 - 3x2 + a x = X{X • 1} (X* - X3 - 11x2 - 7x + U) x* - 12x* - 20x 3 - a x 2 • 8x + 3 = (X • 1) <X2 + x - 1) (X3 - 2x2 - 8x x* - 12x* - 20x 3 - 9 X 2 = X 2 (X + 1)2 ( x 2 - 2x - 9) x* - 12x* - 22x3 - 9x2 «• 6x + 4 = (x + 1 ) 3 ( X 3 - 3 x 2 - 6x • 4) - 3) x 6 - 13x* - 24x3 _ i 2 x 2 = x 2<x + 1) (x + 2) ( x 2 - 3x - 6) x* - 13x* - 26x3 - 15x 2 • 2x + 3 = (x + 1) 3(x3 - 3x2 - 7x * 3 ) x* - 14x* - 32x3 - 27x2 = x(x + 1)3( X2 - 3x - 8) - 8x x« - 15x* - 40x3 - 45x 2 = (x - 5) (x + 1) s - 24x - 5 116 Table I I I : I n t e g r a l Trees of Diameter 3 and Order < 50 0 « I Order 1 — T~ | ffl | — T — n | C h a r a c t e r i s t i c Polynomial I 1 ! 6 1 3 | 3 | x * { x - 1) (x * 1) (x - 2) (x • 2) — J J I 1* 1 7 | 7 | X 1 0 ( X - 2) <x • 2 ) (x - 3 ) (x + 3) | 26 1 13 | 13 I X 2 2 ( X - 3} (x + 3 ) <x - 4} (x • 4) | 42 | 21 | 21 ! X 3 8 ( X " 4) (x * 4 ) (x - 5 ) (x • 5) I 62 I 31 | 31 | X s * ( x - 5} <x • 5) ( x - 6 ) (x + 6) | 86 I **3 | 4 3 | X82 (X - 6) (x + 6 ) ( x - 7 ) (x • 7 ) | 114 I 5 7 | 5 7 | x * i o ( X - 7 ) (x • 7 ) (x - 8 ) (x • 8) J 146 I 7 3 | 7 3 f X* * 2 (X - 8) (x + 8) tx - 9 ) ( x • 9) \ 150 | 51 | 9 9 j X * * 6 (X - 7) {x • 7) (x - 10) (x + 10) I 182 I 91 I 91 | X 1 7 B (x - 9) {x + 9) (x - 10) (x • 10) ! 2 2 2 | 111 | 111 | X 2 * 8 (X - 10) (x + 10) (x - 11 ) (X + 11 ) I 2 6 6 ! 1 3 3 J 1 3 3 | X 2 ^ 2 ( X - 11) {x + 11) <x - 12) (x • 12) I 3 1 4 | 1 5 7 | 157 J ° (X - 12) (x * 12) (x - 1 3 ) ( x • 13 ) | 341 I 148 | 1 9 3 | X 3 3 7 ( X - 12) {x + 12) (x - 1 4 ) ( x + 14) | 366 | 1 8 3 | 1 8 3 | X 3 * 2 (X - 13) (x «• 13) (x - 1 4 ) ( x + 14) | 4 2 2 I 211 | 211 | X * * 8 < X - 14) (x + 14) (x - 1 5 ) ( x • 15) I 4 8 2 | 241 | . j i . 241 | X * 7 * {X - 15) (x • 15) (x - 1 6 ) ( x + 16 ) J 117 I a b l e _ I _ Connected Graphs* with 2 types o f _ L a b e l s and t h e i r c h a r a c t e r i s t i c Polynomials j f o r I — T ~ n| Graph L_4_ C h a r a c t e r i s t i c Polynomial I -+ x* »y xy - 1 +— x z y - y - x x{xy - 2) A , (x • 1) (xy - y - 2) x* y< x< X ' x •-y -x 3 y - 2xy - x 2 • 1 x 3 y - xy - 2x 2 + 1 x 2 y 2 ~ Y 2 - xy - x 2 • 1 x 2 y 2 - 3xy • 1 * Graphs t h a t can be o b t a i n e d by i n t e r c h a n g i n g x and y are omitted. 1— T " |n | Graph \ C h a r a c t e r i s t i c Polynomial x< (xy - x - 1) <xy * x - 1) I X y y X * -•x • X -*x • X • X x ( x 2 y - 2y - x) x 2 (xy - 3) y ( X 2 y _ y - 2x) xt fx *x X x ( x 2 y - 2x - 2y) (xy + x + y) (xy - x - y) y y *x X xy(xy - H) x Y tx (x • 1) ( x 2 y - xy - 2y - x • 1) x3y - 2xy - 2x 2 - 2x + 1 (x • 1) ( x 2 y - xy - 3x + 1) x 2 y 2 - v2 - 3xy - 2xy + 1 (y + 1) ( x 2 y - y - x 2 - 2x + 1) 11 In i Graph \ C h a r a c t e r i s t i c Polynomial — + (x • 1) (x*y - xy - 2y - 2x) x(x*y - 2y - 3x - 4) X 2 y 2 - y2 - X y - y - X 5 y{x • 1) {xy - y - 4) (x + 1 )2(xy - 2y - 3) (x + 1) (y + 1) (xy - y - x - 3) 120 Table_V ftutomgrghism_Par^itioTtings_of Simple Connected Graphs Si?..tg.,n ,~ 6.. Vert i c e s f T G • i — • 1 automorphism 1 P a r t i t i o n i n g _ T _ — — 1 1 C h a r a c t e r i s t i c \ | Polynomial of 1 1 O r b i t - d i g r a p h f o r F(G) | i I 2 | 1« *2 \ ( 1 , 2} » I I x -1 | i 3 i A 3 * \ 2 I P I » ( 2 , 3} l x 2 - 2 | i r ,A- I {1, 2, 3} I x - 2 ) J J 1* • 4 « • 2 • 3 I {1, 4} , [ 2 , 3} f x z - x - 1 1 j J Hi fx >2 »3 l {1} , 12, 3 , 4} 1 x * - 3 1 14 I 1-4« 4< 1 1 1 1 2 •3 2 | ( 1 , 2, 3 , 4} I 0 ) , (2 , 3}, [4} 1 x - 2 1 1 X3-X2~3X+1 | 1 1 1< N >2 '3 I P , 3} , [ 2 , 4} i 1 X 2 - X - 4 1 I I 1< | J 4* X 2 I 1 {1, 2 , 3 , 4} 1 x - 3 | ! 5 | L X. 5?A^ 2 | [ 1 , 2), 13, 5 } , {4} -1 _ 1 X 3 - 3 X 1 ! = x ( x 2 - 3 ) | X _ _ _ - J 121 » — T " Automorphism P a r t i t i o n i n g C h a r a c t e r i s t i c Polynomial of O r b i t - d i g r a p h f o r f(G) {1, 5}, {2}, {3}, m {1},{2, 3, 4, 5} x*~ 4x 2 + 2 x 2-4 = (x-2) (x+2) {1, 2, 3, 4, 5} {1} , {2/ 43, {33 , {5} {1} ,{2} ,{3, 4} ,(5} {1, 2}, (3, 5}, {4} ( 1 , 2} , (3, 4}, {5} x-2 x*-5x 2*2 x*-x 3-4x 2 + 2x+2 = (x- 1) (x 3-4x-2) x 3 - x 2 _ 3 X =x (x 2-x-3) x 3-x 2-4x«-2 (1, 3, 4}, {2, 5} f1}, {2, 5}, {3, 4} {1, 5}, {2}, {3, 4} (13, (2, 4}, (3J , (5} x 2-6 x 3-2x 2-2x+2 x 3~2x 2-3x+4 = <x-1) (x 2-x-4) x*-x 3-5x 2+x+2 122 Automorphism P a r t i t i o n i n g 1} , {2} , {3, 5} , [4} C h a r a c t e r i s t i c Polynomial of O r b i t - d i g r a p h f o r f(G> x*-6x z-4x+2 — + J J & 3 : 1, 2}, {3, 5}, {4} 1/ 3}, {2}, {4, 5} 1; 3, 4}, (2, 5} 1},{2, 3, 4} ,{5} x3-x«-6x+2 x 3 - x 2 - 5 x - 2 x z- x-6 = {x+2) (x-3) x3-2x z-4x*2 1}, (2, 3, 4, 5} 1], 12, 5), {3, 4} x z-2x-4 X 3-2x z-5x+2 V 3, 4}, {2, 5} x z-2x-6 1, 2, 3, 4, 5} x-4 1, 4}, {2, 3}, {5, 6} 1} , {2, 3}, {4} , {5}, {6} X 3 - X 2 - 2 X + 1 xs- 5x3+ 5x =x (x*-5x z+5) «—i_ 123 n Automorphism P a r t i t i o n i n g C h a r a c t e r i s t i c Polynomial of O r b i t - d i g r a p h f o r T(G) 6/ *3 5* 1« 1}, {2, 5}, {3, 4}, {6} 1, 2}, (3, 4, 5, 6} 1}, (2, 3, 4}, {5} , {6} 1, 3, 4, 5, 6}, {2} x*-4x 2 + 1 x 2-x-2 = <x+1) (x-2) x*-5x 2 + 3 x 2-5 'U. 5* 1ft 1 f 2, 3, 4, 5, 6} 1, 4}, {2}, (3} ,{5, 6} 1, 5} r {2}, {3} , {4} , (6} 1, 6}, {2},{3},{U},{5} 1, 4}, {2, 5} , [3, 6} 1, 43, (2, 3}, {5, 6} 13 , 12) , (3, 4} ,{5, 6} x-2 x*-x 3-4x 2+3x+1 = (x-1) (x 3-4x-1) X s - 6 x 3 + 6 x =x <x*-6x2+6) x s-x*-5x 3+3x 2+5x-1 = {x+1) (x*-2x 3-3x 2+6x-1) x 3- 5x =x(x 2-5) x 3-2x 2-x+1 x*-x 3-5x 2*3x*4 I — T ~ n Automorphism P a r t i t i o n i n g Cha r ac te r i s t i c Polynomial o f O r b i t - d i g r a p h f o r P(G) 5 ^ - ^ X 4 5s* «4 •A 5 1 }» (2, 3 } , { 4 , 6 } , {5} } , (2), {3} , {4} , {5} , {6} }, {2}, { 3 } , { 4 } , f5, 6} , 2, 5}, {3, 4, 6} }, {2, 3}, { 4 } , { 5 } , {6} }, {2, 3 , 4 } , { 5 , 6} x * - 6 x 2 + 4 x * - 6 x * - 2 x 3 + 7 x 2 + 2x-1 x 5 - x * - 5 x 3 * 3 x 2 * 3 x - 1 = (x-1) i x * - 5 x 2 - 2 x + 1) x 2-2x-1 x s - 6 x 3 - 2 x 2 + 5 x = x <x*-6x 2-2x+5) X 3 - X 2 - 5 x 4 - 3 si Jra 5 ^ \ £1 , 2}, {3, 6 ) , ( 4 , 5} , 3 , 4 , 6} , {2, 5} , 2, 3 , 6 } , ( 4 , 5} , 5} , [2, 4 ) , { 3 } , [ 6 ] , 5}, (2, 3 } , { 4 } , {6} x 3 - x 2 - 5 x * 4 x 2-2x-1 x 2~2x-1 x*-x 3-5x 2+2x>4 x * - x 3 - 6 x 2 + 4 x + 4 125 1—T~ 1 1 C h a r a c t e r i s t i c Polynomial of O r b i t - d i g r a p h f o r T{G) Automorphism P a r t i t i o n i n g 5M H ' \2 in H , <»3, {2, 3}, {5}, {6} f l ) , {2} , {3}, W, {53, {63 {13, {2, 3, 5} f {4}, {6} { I t ^3. C2}, {33 ,{5, 63 {13, {23, {33, {43, {53, {63 {1r 63 , (23, {33,{4|, {53 {1, 53, {23 , (33 , {4}, {6} [13, {2} , {33, {4, 6}, {5} {1, 3, 4, 6}, {2}, {5} {1, 43, {2, 53, {3, 63 {1, 5 3 , {2}, {3, 4 3 , {6} x * - 7 x 2 + 4 x* - 7 x*-2x 3 + 8 x*+2x -1 x*-7x2 + 3 x * - 2 x 3 - 3 x 2 + 4 x -x (x-1) ( x 2 - x - 4 ) x* - 7 x*-2x3 + 7 x 2 -1 x s - x * - 6 x 3 + 2 x 2 + 7 x - 1 x s ~ x * - 6 x 3 + 2 x 2 + 6 x =x (x + 1) (x 3-2x2 - 4 x + 6 ) x s - 7 x 3 - 4 x 2 + 7 x + 4 x 3-x 2 - 5 x + 1 x 3-x 2 - 5 x + 1 x+-x 3 - 6 x 2+2x+ 4 = {x-1) (x*2) (x2-2x-2) In ^ , — | Characteristic Polynomial of Orbit-digraph for f(G) automorphism P a r t i t i o n i n g 1}, m, {3}, m, {5}, {6} 1# [2, 5 } , {3, 6} 1, 5 } , {2, 3}, f4},[6} x * - 7 x * - 4 x 3 * 6 x 2 + 2 x-1 x 3 - x 2 - 5 x =x{x2-x-5) x * - 7 x 2 - 4 x + 4 = (x+2) ( x 3 - 2 x 2 - 3 x + 2) m i s •£3 1, 2, 4, 5 } , {3, 6} 1, 2, 4, 5 ) , (3, 6} 1. 3}, {2}, {4, 6}, {5} 1, 2), [3, 6}, {4, 5} 1, 2], {3}, {4}, {5}, {6} 1}, {2, 6}, {3, 5 ) , {4} 1, 2, 3, 5 } , {4, 6} 1, 5), {2, 3}, {4}, {6} x 2-2x-2 x 2-2x-2 x*-x3-6x 2+3x+1 X 3-2 X 2-4x+ 5 = (x-1) ( x 2-x - 5 ) xs-8x3-2x2+7x =x tx*-8x2-2x+7) X4-7 X 2-4x+4 = <x*2) (x3-2x2-3x + 2) x2-8 x*-2x3-5x2 + 6x + 4 I f ; 1 1 C h a r a c t e r i s t i c Polynomial of Or b i t - d i g r a p h f o r fCG) ass V\—T2 m automorphism P a r t i t i o n i n g cn, m. (33, m, {5}, {6} , 5}, {2}, [3} , {4, 6} , 2} , (3, 6} , {4, 5} } , ( 2 } , {3} , {4 } , r 5 , 6} , 5} , [2} , [3} , (4} , [6} , 5}, (2, 3}, {4}, (6} } . {2} , {3} , [4} , [5} , (6} 1 , C2} , [3} , [4} , f5) , [6} , 61, (2, 5}, {3}, {4} , 5 ) , {2, 6}, {3}, {4} },{2},{3},f4, 5, 6} x6-8x*-4x 3+9x 2+4x-1 x*-x 3-7x 2+3x+4 = {x-1) <x3-7x-4) x 3-2x 2-4x+4 xs-x*-7x 3+3x 2*3x-1 X s - 8x 3 - 4x 2 +6x -x (x4-8x 2 -4x+6) x*-x 3 -7x 2 *x+8 x*-8x*-6x 3+8x 2+6x =x(xs-8x 3-6x 2+8x+6) x * -8x* -6x 3 «-7x 2 + 4x-1 x*-x 3 -6x 2 -x+1 x*-x 3-7x 2+x+4 x*-2x 3-5x 2+4x+3 t X -128 automorphism P a r t i t i o n i n g C h a r a c t e r i s t i c Polynomial of Orbit-aigraph f o r f<G) 5 ^ 4 {1. 2, 5), {3}, [H), {6} f l , 2}, {3, 6}, [4, 5} {1, 5, 6}, {2, 3} , {4} x*-8x 2-6x+3 x3-2x z-4x+1 X 3 - 2x 2-5x + 4 s i *4 [1. 2, 3, 4, 5, 6} {1. 2, 3, 4, 5, 6} C U 6}, {2}, {3},f4},(5} (1} , (2} , {3} , {4, 6}, {5} PI , [2, 4}, {3} , ( 5 , 6} P , 2}, {3, 6} , [4, 5} {1} , f2) , {3} , {4} , (5) , {6} {1, 4} , [2, 5}, {3, 6} x-3 x-3 x s-x*- 8x 3 «-2x2+9x-1 x«-9x 3-4x 2+7x = x (x*-9x 2-4x+7) x*-x 3-7x 2 + 4 = (x+2) (x 3-3x 2-x+2) x 3-x 2-8x+4 x 6-9x*-6x 3+8x 2*2x-1 x 3-x 2-6x-3 L L-129 Automorphism P a r t i t i o n i n g Cha rac t e r i s t i c Polynomial of O r b i t - a i g r a p h f o r f(G) S3 1. 5} f {2, 4}, {3}, {6} 1}, {2, 6}, {3, 5}, {4} 1, 3, 5}, {2, 4/6} 1, 6}, [2, 5}, (3, 4} 1, 5, 6}, {2, 3} , {4} 1, 2}, {3}, {4} , {5}, {6} 1}r {2, 6}, (3), {4}, {5} 1, 2, 5, 6} , {3} , {4} 1, 6}, {2, 5}, {3}, {4} 1, 2, 4, 5}, {3, 6} 1, 5}, {2}, {3}, {4}, {6} x*-x 3-8x 2 + 2x + 4 x*- 8x 2-8x + 1 x 2-2x-4 x 3-3x 2-2x+4 = (x-1) (x 2-2x-4) x 3-3x 2-3x + 7 x s-9x 3-8x 2+6x+4 = (x+2) <x*-2x 3-5x 2+2x+2) x5-9x 3-8x 2+5x + 4 x 3-2x 2-5x+2 x*-2x 3-6x 2+4x+3 = (x-1) (x 3-x 2-7x-3) x 2-x-8 xs-x*-8x3-2x 2*6x =x (x*-x 3-8x 2-2x+6) 130 I —T EE 1 5 V Automorphism P a r t i t i o n i n g {1} , {2} , [3} , {4}, {5, 6} {1, 2, 4, 5} , [3, 6} (1. 6}, [2, 5}, {3, 4} {1, 3, 5}, {2, 4), {6} {1, 2, 3, 5 f 6), (4} (1/ 3}, {2}, {4, 6}, {5} { V 3}, {2}, {4, 6 ] , {5} {13 , {2}, {3} , {4, 6}, {5} {1, 5}, f2}, {3}, {4}, [6} C l 3 r {2}, {3}, {4}, (5, 6} {1, 2, 4 r 5 3 , {3, 6} C h a r a c t e r i s t i c P olynomial of O r b i t - d i g r a p h f o r T(G) xs-x*-8x3-2x2*5x-1 x 2-x-8 x 3-2x 2-5x + 1 x 3-x 2-9x+3 x 2- 2x-5 x*-10x 2-8x+4 x*-2x 3-6x 2+2x*4 x s - x » - 9 x 3 - x 2 + 7x-1 xs-10x 3~10x 2+5x+4 xs-x*-9x 3-3x 2+10x+4 x 2-3x-2 i x. automorphism P a r t i t i o n i n g C h a r a c t e r i s t i c Polynomial of O r b i t - a i g r a p h f o r H G ) H 3 , { 2 , 6 3 , {3, 5} ,{4} {1, 2}, {3, 6}, (4, 5} f1}, {2, 5, 6}, {3}, {4} [1, 5], [2, 6 } , C 3 } , { 4 } x*-x3-8x2-5x+1 = (x+ 1) (x3-2x 2-6x+1) X3-2x2-7x+4 x*-2x3-7x2+2x+3 x*-x 3-9x 2-5x*4 [1, 4} , [2, 5), {3, 6} {1, 2, 4, 5} ,{3, 6} [1, 3, 5} ,12, 4} , [6} (1, 2), {3}, [4} , {5, 6} [1, 4, 5}, (2), [3, 6} {1, 2, 4, 5} ,-{3, 6} (1, 5}, {23, {3}, {4}, {6} x3-x 2-9x-4 x 2-4x* 1 X 3 - 1 1 X - 1 2 x*-2x3-7x2+4 = (x+1) (x 3-3x 2-4x+4) x3-2x2-8x+4 x 2-2x-7 xs-x*-10x3-6x2+7x*3 i— i— , , , C h a r a c t e r i s t i c Polynomial of O r b i t - d i g r a p h f o r f( G> Automorphism P a r t i t i o n i n g H , 5}, {2}, {3, 6}, {4} {1, 2, 5, 6}, {3}, (4} x*-x 3-10x 2-6x+4 = {x+2) <x 3-3x 2-4x+2) x 3-3x 2-5x + 3 f1, 2, 3, 4, 5, 6} f1}» {2, 6}, {3, 5} ,{4} {1. C2, 5} , {3, 6} {1, 3, 5} , [2, 4, 6} [1, 3}, (2) , [4, 5, 6} x-4 x*-x 3-11x 2-7x+4 x 3-2x 2-8x-3 x 2-2x-9 x 3-3x 2-6x+4 P r 2, 4, 5}, (3, 6} {1}, {2, 4, 6}, {3, 5} x 2-3x-6 x 3-3x 2-7x+3 6^  p , 5}, 12, 3, 4, 6} x 2-3x-8 {1, 2, 3, 4, 5, 6} x-5 I L 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0094269/manifest

Comment

Related Items