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  in THE FACULTY  OF GRADUATE  STUDIES  (Department o f M a t h e m a t i c s and Institute  of Applied  We a c c e p t  Mathematics and S t a t i s t i c s )  t h i s t h e s i s as conforming  to the reguired  standard  THE UNIVERSITY OF BRITISH COLUMBIA April,  ©  1978  Fat-Kwong L o u i s  Ng, 1978  In p r e s e n t i n g t h i s  thesis  an advanced degree at the L i b r a r y s h a l l  in p a r t i a l  make i t  freely available  for  I agree  reference and  f o r e x t e n s i v e copying o f  this  that  study. thesis  s c h o l a r l y purposes may be granted by the Head of my Department or  by h i s of  the requirements f o r  the U n i v e r s i t y of B r i t i s h Columbia,  I f u r t h e r agree t h a t p e r m i s s i o n for  fulfilment of  this  representatives. thesis  It  is understood that  f o r f i n a n c i a l gain s h a l l  w r i t ten pe rm i ss ion .  Department of  Mathematics  The U n i v e r s i t y o f B r i t i s h  2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5  Date  A  P r i l 28, 1978.  Columbia  copying or p u b l i c a t i o n  not be allowed without my  i i A B S T J ACT This  thesis  polynomial graph  and  discusses  the  minimal polynomial  reducibility  how  this  of  reflects  automorphism  properties  T h e n we  number o f o r b i t s  of  graph  factorization  and  Finally  we  the  present  partitioning  to  of  a  of the r e s u l t s  graphs with  study  a subgroup  an  the  can  the  to  graph  the relationship  a l s o be  determine  the  i t scharacteristic  loops...  a  consider see  and  i t s  between  the  group  of  a  polynomial. automorphism polynomial.  extended t o d i r e c t e d graphs  and  of  o f a graph and  of i t scharacteristic  using  p a r a l l e l edges  of  first  o f t h e automorphism  algorithm graph  characteristic  g r o u p . We  the minimal polynomial the  group.  of  of the adjacency matrix  t o c h a r a c t e r i z e i t s automorphism  the  Most  use  and  iii TABLE OF CONTESTS  I.  INTRODUCTION  1  1.1 B a s i c D e f i n i t i o n s 1.2 B a s i c P r o p e r t i e s 1 • 3 Mo  and N o t a t i o n s o f t h e Automorphism  1.5 L i t e r a t u r e MINIMAL  Group  .........  14  POLYNOMIAL  OF THE ADJACENCY  Minimal Polynomial  MATRIX  ........... 21  .....................  2.2 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  3.1 Spectrum  o f a Graph  3.2 C h a r a c t e r i s t i c  45  .  45  P o l y n o m i a l and  Automorphism  Group  o f a Graph  ... 56  3.3 G r a p h s w i t h L a b e l s I V . EXTENSIONS 4. 1 D i g r a p h s  AND  . . . . . . . . . . . . . . . . ........ ..... ..... . 69  APPLICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . .  ....77  4.3 T h e G r a p h I s o m o r p h i s m P r o b l e m 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 C o n e l u s i on •  Appendix  73  . . . . . . . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ,73  4.2 N o n - s i m p l e G r a p h s  Bibliography  22 27  ADJACENCY MATRIX AND AUTOMORPHISM GROUP  m5  8  ..............................14  Review  2.1 I r r e d u c i b l e  III.  1  Vet tx on •••••*••• • • • » • • • * * • • • • • • • • • • • * • • • • • « • « • • • ; ' 12  1.4 S t a t e m e n t o f P r o b l e m s  II.  ...  •  *  •  •  •  •  •  •  •  • «  •  *  *  ......................  78  . . . . . . . . . . . . . . . . . . . . . . . . . 79 •  •  •  *  t  •••• •••** ••••« • •  * 85 . 87  ................ . 92  iv L I S T OF  FIGOSES  FIGURE 1.1:  PAGE  A Pair  of Cospectral  Graphs  20  2 . 1 : A T r e e o f D i a m e t e r 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 of K,  2.2: S u b d i v i s i o n  Graph  2 . 3 : An I n t e g r a l  Composite Graph  2 . 4 : Two  More I n t e g r a l  3.1: G r a p h s  with  3.2: A Graph 3 . 3 : K,  4  Graphs  on F i v e  4.1:  An I d e n t i t y Polynomial  42  ................................ 55  Orbit—digraph  Vertices  Digraph  42  47  Symmetry  and A s s o c i a t e d  The P a t h  ..........................  Index 2  with  3.4:  40  4  o f <(25) , (34) > .... 59  ............................  With  and I t sC o n v e r s e  Irreducible  62  Characteristic 76  ACKNOWLEDGMENT I this  would  topic  I  t o t h a n k Dr. Abbe Pfowshowitz f o r s u g g e s t i n g  and f o r h i s c a r e f u l  would  throughout  like  also  like  editing  o f the t h e s i s .  t o t h a n k Dr. R. A. R e s t r e p o f o r h i s  the preparation o f the t h e s i s .  help  1 I.  INTRODUCTION  In  this  thesis  we  will  between t h e a u t o m o r p h i s m  group  m i n i m a l and c h a r a c t e r i s t i c In that  are related  this of  Chapter  thesis.  using  examine of  a  the relationship graph  I we w i l l  present d e f i n i t i o n s  t o t h e problems  the  I n C h a p t e r I I , we w i l l c o n s i d e r  t h e problem  the minimal  polynomial of the adjacency matrix to  automorphism  group  the structure  group.  of a  i n terms o f v a r i o u s  Chapter  graph  and  properties of  a d j a c e n c y m a t r i x . C h a p t e r IV d e a l s w i t h e x t e n s i o n s and obtained i n the previous chapters.  Algorithmic considerations  Basic,,, D e f i n i t i o n s  will  this  section.  whose  f  G  E (G))  elements  of  is  order  consisting are  E (G) , whose e l e m e n t s e € E(G)  throughout  be g i v e n  i n the d e f i n i t i o n s  this  in will  thesis.  1.1  ft grajah (V (G)  concepts w i l l  Notation introduced  be u s e d c o n s i s t e n t l y  Definition  a l s o be i n c l u d e d .  and N o t a t i o n s  Some b a s i c g r a p h t h e o r e t i c  G =  and r e s u l t s throughout  applications of results  1.1  the  t o be s t u d i e d  i s devoted t o examining  its  and  p o l y n o m i a l s o f G.  c h a r a c t e r i z e t h e g r a p h and i t s automorphism III  G  n  identified  an  ordered  o f a nonempty f i n i t e  called are  is  vertices  called  (points),  edjges,  such  w i t h an u n o r d e r e d p a i r  pair  s e t V(G), and a s e t that  each  ( u , v) o f  2 distinct e•=  vertices  ( u , v)  the  In the  and  E (G)  |V(G)J i n V(G) general,  n vertices  we w i l l  say  that  v. V{G)  edge-; s e t ,  be  d e n o t e d by  u s e v, , v , a  the  edge  will  be  called  The  number o f  n.  . ,. , v  to  OT  represent  i n V ( G ) ; sometimes o n l y t h e s u b s c r i p t s  an o r d e r e d p a i r  e e E(G) , t h e n {or  the  will  be u s e d when no c o n f u s i o n If  fe  j o i n s t h e v e r t i c e s u and  vertex set  elements  u , v t V (G) .  will  arise.  ( u , v)  G i s called  will  i s used  to i d e n t i f y  a di<JE§B!j and  e =  an  edge  ( u , v) a  line  a r c ) f r o m 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  s e n s e , i . e . " l o o p s " and precisely  a g e n e r a l graph  where V{G) from  is  a  nonempty  incidence.function unordered  edges  pair edge  e, )  =  parallel  e  ^Q(  e 2  )'  1.1  = e  set  that associates  of v e r t i c e s  and  Definition  is a triple  a r e a l l o w e d . More  G =  (V (G) , E ( G ) ,  i s a nonempty s e t o f v e r t i c e s ,  V(G))  An  " p a r a l l e l edges"  edggs,  He  said a  will  "simple" to d i s t i n g u i s h  I 5 i s an  a loop i f u =  to  graph  be in  i s a g e n e r a l graph with  edges.  and  w i t h e a c h edge o f G  ( u , v) i s c a l l e d  Thus  (disjoint  an  o f G.  are  z  of  E (G)  Y^)  sometimes  v.  parallel the  no use  graphs from g e n e r a l  sense  loops the  and  Two i f of no  adjective  graphs.  3 •Def i n i t i g n Two  vertices  denoted vertex  1 . .3  by  u, v € V(G)  u a d j v,  v, d e n o t e d adjacent  to  It-regular  (or r e g u l a r  the  Definition For  that  The  i s d e f i n e d as  the  of_degree  a  graph  k)  i f  adjacent, degree  is  of a  number  of  said  be  to  every  vertex  has  can  define  the  i f u adj  *-0  otherwise.  u, w  u, Vp  ft p a t h f r o m  Definition A  Let  =  1} a s  follows:  w and  v_ l  l  vertices adj v  be c a l l e d  L  a  u  to  v„, v, , ... , v  for i =  p  w  such  1, 2,  p.  cycle.  1.5 G i s said  t o be c o n n e c t e d  there exists  i f f o r any  a path  from  pair  of  u t o v. ,.  1.6 G  be  {v, , v ,  A(G)  [0,  to  v,  of d i s t i n c t  u, v e 7(G)  Definition  x V (G)  € V(G), a path o f l e n g t h p from  u to u w i l l  graph  vertices  V(G)  we  1. 4  any  v„ =  3 on  relation  r1  sequence  V (G) =  be  E(G).  i t ; and  adjacency  adjacency ^ f u n c t i o n  a  to  k.  From  is  said  (u, v) €  by deg v ,  vertices  degree  i f  are  t  graph  . .., v „ } . Then t h e  z  = fa  a  i  ]  with matrix  vertex  set  4 where a a  = 9(v ,  L  c  Definition The  V;) «  i s called  c h a r a c t e r i s t i c (jn i n i m a l | ; g o l y n o f f l i a l o f a g r a p h G ;  p o l y n o m i a l o f A ( G ) , and minimal The are  G.  1.7  w i t h a d j a c e n c y m a t r i x A(G)  the  the adjacency matrix of - —  i s the c h a r a c t e r i s t i c  will  be d e n o t e d by f (G)  (minimal) (p(G)  for  polynomial).  characteristic  roots  (or e i g e n v a l u e s ) o f a  t a k e n t o be t h e c h a r a c t e r i s t i c  graph  r o o t s o f A (G).  P e f ij5iii2IL_ 1 8 i  The  i-  index of a  graph  G,  denoted  d e f i n e d t o be t h e l a r g e s t c h a r a c t e r i s t i c  Definition  2  =  G, £  graphs 2  2  i f  2  isomorphism, (u, , u ) z  there  from 6  Def i n i t i o n _ 1 _ 1 . 0 i  &  n  root of  Thus G onto  is  G.,  exists  V(G,)  =  and  t o be i s o m o r p h i c , d e n o t e d a  t o V(G )  E (G, ) i f f  ( V ( G , ) , E(G,))  2  {?>,),  bijection such  f»  called  an  by an  that  T(u )) 2  E(G ). 2  ( c f . . [ 16, p. 161 ])  automorphism o f a graph G i s a p e r m u t a t i o n o f  v e r t e x s e t V(G)  of  G,  ( V ( G ) , E{G )) are s a i d G ,  r = r{G),  1.9  Two G  by  which  preserves adjacency.  a u t o m o r p h i s m o f a g r a p h G i s an  itself.  the  isomorphism  5  We G  note t h a t  forms  a group  multiplication. automorphism will  'Definition  G = an  under This  G,  =  i f  u , v 6 V{G,)  any  G  of permutation  permutations and e a c h  graph  is  the  of  r<G)  subgraph  of  subgroup  automorphisms.  V(G,)  i f e =  implies  e  E(G,)) C  ¥(G)  <u,  v)  set  will  be  is and  a E(G ) (  e E(G)  C  E (G) . G  such  (  is  that  6 E(G,).  subset S C V(G), the  s e t V(G)\S  Definition  denoted  (s) t h e n o t a t i o n  induced  subgraph  by G - S.  G - s will  be  with  When S i s t h e employed.  1.12  A subgraph if  of  ff{G,),-  inducedsubgraph  singleton  of  of a  1. 1,1  ( V ( G ) , E (G))  vertex  group  a group.of  graph  For  the usual operation  P(G)  group  be c a l l e d  A  the s e t o f a l l automorphisms  G,  of a graph  G is called  i t i s a maximal c o n n e c t e d s u b g r a p h  of  a- component o f G G.  Def i n i t i o n 1 . 1 3 Let denoted e =  G =  (V(G) , E ( G ) )  be a g r a p h . Then i t s complement,  by  G,  graph  (u, v) e  E(G)  is  the  whenever  G =  u # v and e  (V{G), 1(G)) I E(G).  where  6 D e f i n i t i o n 1..TJJ The  simple  distinct graph  vertices  on  n  complement  Definition  adjacent and  v  2  e  It  graph  n  is  will  which e v e r y  called  be  the  denoted  a l l vertices  ( o r empty  in  two  complete by  K„. I t s  are non-adjacent,  graphV  on  n  is  vertices.  1.15 G  into to  v  i s b i p a r t i t e i f the v e r t i c e s two  2  sets  V,  and  V  i m p l i e s f v , €•••¥,• and  such  z  v  a  *  o f G can that  v,  be is  vv ] o r f v , c  v  a  v, ].  Definition A  order  adjacent  K „ , i n which  graph  partitoned  are  of  vertices.  called the void  A  graph  t  1 16 9  S i c l e C „ on n v e r t i c e s  is  a  connected,  2-regular  graph.  Definition  1.17  ft s u b d i v i s i o n r e p l a c e m e n t o f an where w i s a new  of  edge  an  edge  ( u , v)  |u, v) by two  vertex i n the  edges  refers  to  ( u , w),  the  (v, w)  graph.  Dgfisiiion_1 18 J L  Two  graphs  G,,  G  2  there e x i s t s Gj such t h a t G  3  by  a sequence  are G,  said  and G  2  of subdivisions of  t o be homeomorphic i f c a n be edges.  obtained  from  7 Definition The the  1.19 c h r o m a t i c number  0({G) o f a g r a p h  minimum number o f c o l o r s  v e r t i c e s o f G so t h a t  that  G i s defined  as  i s required t o c o l o r the  no two a d j a c e n t  vertices  have  the  v e r t e x c u t o f a g r a p h G i s a s u b s e t V* o f V{G)  such  same c o l o r .  l?ff=S=£ion_1. 20 A  that cut  G - ?'  (See [ 2, p.421)  is  d i s c o n n e c t e d , ft k - v e r t e x c u t i s a v e r t e x  o f k elements.  nonadjacent minimum define  I f G has a t l e a s t  vertices,  k f o r which /C(G) t o be  The  this  G has a k - v e r t e x  notation  will  z  b, , b ,  * z a  '  ••••»•  permutations  e will fe}  the  identity For of  of G i sthe  otherwise,  we  also  be u s e d  consistently  be used t o d e n o t e  an n — v e c t o r  b„ a s t h e c o o r d i n a t e s .  z  <  cut;  distinct  thesis:  (b, , b , ... , by,) ' w i l l with  K(G)  connectivity  of  | V ( G ) | - 1.  following  throughout  the  one p a i r  < r  »n>  will  generated  be u s e d t o d e n o t e  trivial  permutation  denote by  the the  the identity group  group  of  permutations  p e r m u t a t i o n and  containing only the  permutation. any g r o u p  H,  |HJ w i l l  be used  t o denote  the order  H. D„ w i l l  be u s e d t o d e n o t e  the  dihedral  group  on  n  8 e l e m e n t s and For  S„  any  the symmetric matrix  characteristic  B,  group  on n  f(B) w i l l  polynomial  of  B  elements.  be used t o denote  and  p(B)  the  the  minimal  p o l y n o m i a l o f B. I„  will  be  used  to  denote  o r d e r n. When the o r d e r i s c l e a r subscript  1.2  will  this  well-known  the  context,  the  the^^utomgrphigm^gronp  section  automorphism  from  matrix of  be o m i t t e d .  Basic., P r o p e r t i e s ..of In  the i d e n t i t y  group results  we  of  a are  discuss  b a s i c p r o p e r t i e s of the  g r a p h . / The obvious  following from  the  <r be a p e r m u t a t i o n on t h e v e r t i c e s  of a  three relevant  definitions.  Theprem_1.1 Let and  Pg. i t s c o r r e s p o n d i n g p e r m u t a t i o n m a t r i x . Then <r i s an a u t o m o r p h i s m  where A =  Theorem  rm  of G i f f e\ r  =  AP^,  A <G).  1.2 =  r e  5  ) .  Theorem_J^3  where  i s t h e symmetric  group  on n e l e m e n t s .  graph  G  9 Definition;, Two §JBl|ar  1.21  vertices  x  d e n o t e d by  f  automorphism of  G  y  r  x ~  € V(G) y,  of  a  graph  G  i f there exists  mapping x t o  are  said  to  at  least  be one  y.  D e f i n i t i o n_-li 2 2 The  automprghism^Bartitjoning  partitioning the  same c e l l  Hence precisely  the  the  vertices  i f and  the  Definition  only  orbits  graph  is  vertices  x and  is a  y are  in  y.  partitioning  of  G  gives  of  a graph G i s a v e r t e x f i x e d  by a l l  G.  called x and  an  y are  identity.graph  if  no  two  similar.  1.25  graph  vertices)  if x~  G  1.24  Definition A  G such that  graph  1..23  Definition  distinct  a  of  a u t o m o r p h i s m s of  A  of  automorphism  fixed-point  a  the  of  of  is  i f every  Thus f o r partitioning iiie=§y.|imetric  point—symmetric two  vertices  x and  a point-symmetric is  (or  y are  graph G  V (G) . S i m i l a r l y  we  transitive  say  ;  ;  the  similar.  the  automorphism  that  a  graph G  (or t r a n s i t i y e _ p n . t h e - e d g e s ) ' i f . f o r ;  on  is  every  10 pair  of  edges  p  and  automorphism o f G endpoints  of  g,  there  mapping  the  exists  at  least  one  endpoints  of  p  the  to  g.,  fhegrem_1.U I f u, v a r e two G - u S G We graphs  and  will and G,  Va  and  G = G,  0 G  E = E,  0 E .,  G  consider  has t  joining F o r any  The 7,  be  2  graphs  j o i n G,  • G  product  Consider v =  (v, , v ) 2  x G  u,  a d j v, }. ,  the  z  Let  H  set  X =  permutation Y -  G, x G  graph  {y, , y i z  2  E ,  7 = V,  The  and  2  union  edge  U G  c o n s i s t s o f G,  2  G,  we  w r i t e nG  set  and a l l  2  -  vertices  and  u  a permutation  (x, , x , 2  of  . r y l . The  2  u =  2  adj v  z  3  (u, , u )  The  and  2  v are adjacent i n o  r  f a  and  let  degree  e  acting  H + K  is  = v  Q  group o f degree  x^},  sum  x V .  follows:  2  i  graph  G.  x V . Then u and v  f o r the  v e r t e x s e t 7 = 7,  i s d e f i n e d as  2  i n 7 = 7,  e  U 7  V,  vertex sets  respectively.  2  has  two  group  p,163])t  isomorphic with x G  any  be  and  o p e r a t i o n s on  2  whenever [ U i  G,  then  7 .  connected  edge s e t E o f G,  and set  and  following  with d i s j o i n t  vertex  w i t h n components each The  the  (see [ 1 6 , p. 21  edge s e t s E,  2  2  edges  now  and  G,  v.  groups  Let  s i m i l a r v e r t i c e s of a graph  K  d acting be on  a  a n < 2  *  on  another the  set  permutation  11 group  which  elements and  p  acts  on  the d i s j o i n t  union  X U Y a n d whose  in  K,  written  by oi • f  permuted  (<* * B)  The  Any e l e m e n t  z of X 0 Y i s  z € x  C oi z , ( T )  =  <  V- pz,  cartesian  permutation  * + ^.  z « Y.  product  group  which  H x K acts  of  H  and  K  o(  in  p) <x,  The  y) =  t f\ »  X x Y.  For  permutation  such t h a t  (x, y) o f  as f o l l o w s :  each  « H  permutations in  p, 2  ...»  H[K] w r i t t e n  K  also  and in  acts  any  K,  on  seguence  there  is  a  (e<; p,,. |3 , ..., yS^) 2  automorphism  f A ) (x , y^) = (olx |S- y^) .. L  if  are results  between o p e r a t i o n s  on  concerning the r e l a t i o n s h i p  graphs  and  operations  on  their  groups.  Theorem  1.5 [ 1 8 ]  If  G, , G ,  G =  i n K. The e l e m e n t  of  t  following  connected  o( x ^ ,  f o r ( x , y. ) i n X x Y:  (4; p,, The  a  {4x, |Sy).  •••» y^.) •'°f  unique  ^  p r o d u c t Hf" K 1 o f H a r o u n d  wreath  set  and  by oi x &  X x Y i s permuted x  H  is  on t h e s e t X x Y and whose  permutations are a l l the ordered p a i r s , written permutations  H  according to the rule:  '  the  vi i n  are a l l the ordered p a i r s of permutations  2  ...» G  g r a p h s and n T ffli,G , k=1 * k  then  w  are  pairwise  non—isomorphic,  12  r<G>  =  i s [F(G > i. k=1 k  Corollary,1,1  [ 1 6 , p.166 3  + G ) =  no,  if  K  w  r<G,)  2  and o n l y  component  •  r(G > 2  i f no component o f G ,  of G  Theorem_1 .6  2  i s  isomorphic  with  a  .  ([ 32 3; f 1 6 , p . 166 3)  J!  r<G, x G ) = n s , ) x r<c ) 2  2  if  and  [16,  1.3  only  G,  i f  and  G  4  are  r e l a t i v e l y prime (see  p. 1663 o r [ 3 2 3 f o r a d e f i n i t i o n o f p r i m e  graphs).  Motivation  From  Theorem  permutation  solution  to  structure  the c o n s t r u c t i o n  group o f a graph G i s e q u i v a l e n t  automorphism all  1 . 1 , we s e e t h a t  matrices  this  problem  A (G) .  of  that  commute  obviously  The  minimal  depends and  Hence we e x p e c t t o o b t a i n  automorphism of  i t s minimal The  a  group  graph  problem. I n  on  characteristic properties of  properties  of  the  polynomials.  o f d e t e r m i n i n g t h e automorphism  closely fact,  the  o f a g r a p h by s t u d y i n g t h e p r o p e r t i e s  and c h a r a c t e r i s t i c  problem is  some  finding  & ( G ) . The  with  p o l y n o m i a l s o f A ' ( G ) r e f l e c t , t o some e x t e n t , A(G).  to  of the  i t  related is  to  known  the that  graph the  group  of  isomorphism automorphism  13 partitioning  problem  graph  isomorphism  that  can  i s algorithmically eguivalent  problem.  That  means, g i v e n  s o l v e t h e automorphism  partitioning  can use i t t o s o l v e t h e graph isomorphism versa.  i n Section  Applications which  is  example,  all  problem  represented formulas,  chemical  graphs  isomorphic  be f o u n d i n r e t r i e v i n g  graphically.  be  structural  substructure.  This  chemical  Chemical  we  and v i c e will  be  by g r a p h s c o r r e s p o n d i n g  compounds t h a t problem  representing to a given  information  compounds,  and we may d e s i r e  to  have a g i v e n  involves finding the chemical  for to  identify  r a d i c a l or  subgraphs  of  compounds w h i c h a r e  graph.  Sussenguthf39] describes  of  problem,  4.3.  can  stored can  the  the  algorithm  Hore d e t a i l e d t r e a t m e n t o f t h i s c o n n e c t i o n  considered  their  an  t o the  an  algorithm  s t r u c t u r e s . The a l g o r i t h m  for  matching  uses v a r i o u s  properties  t h e v e r t i c e s o f t h e two g r a p h s t o p a r t i t i o n  the vertex  sets.  In chemical  atom  and  bond  represented edges.  structures, types.  a  substructure. identifying difficult  Actually  properties  these  include  p r o p e r t i e s c a n be  by means o f l a b e l s on v e r t i c e s and w e i g h t s  Sussenguth*s  whether  these  algorithm  chemical He  note  isomorphic  compound  can a l s o  the  graphs  is  than matching chemical  be u s e d t o c h e c k  contains  that  on  general  a  problem  considerably  structures.  certain of more  1•^  S t a t e a e n t of _Problems The f o l l o w i n g (i)  characterization from  (ii)  two p r o b l e m s  will  be s t u d i e d :  o f t h e automorphism  group  o f a graph  p r o p e r t i e s of i t s adjacency matrix,  construction whose  of  the  adjacency  automorphism  matrices  groups o f graphs  share  some  common  properties. We graphs will  shall  concern o u r s e l v e s mainly with f i n i t e  (as d e f i n e d  also  Literature  m  In  in  Section  be c o n s i d e r e d  1.1).  Various  simple  extensions  i n Chapter IV.  Review this  results that  section,  we  are related  are  to  going  the  t o review  problems  briefly  mentioned  in  S e c t i o n 1.4. The  problem : o f t h e e x i s t e n c e  g r o u p was posed by K t t n i g f 2 1 ]. I n that  for  any  finite  Later  connected  the  regular  Sabidussif33 ] c e r t a i n given of  same  Sabidussi*s  1938  Frucht[11]  group H t h e r e e x i s t  graphs w i t h automorphism H.  of graphs with a given  groups a b s t r a c t l y  authorf101  graphs o f degree  generalized  this  extended three. result  infinitely  many  isomorphic  to  this result to Then to  i n 1957,  graphs  p r o p e r t i e s . The f o l l o w i n g i s t h e main generalization.  proved  with result  15 Theorem, 1. 7 Given a f i n i t e j,  1 < j < 4,  connected  as  > 1  and  exist  many  non—homeomorphic  infinitely  fixed-point-free  automorphism property  there  group H o f o r d e r  graphs  G  such  g r o u p o f G i s i s o m o r p h i c t o H,  P; , where t h e p r o p e r t i e s  P-  an  (j =  integer  that and  (i) the  {ii} G has  1, 2,  3, 4)  are  follows: •T-J»e-- conneet'iV'±'ty-'0'f-G"-is'--k-,- *her«'--k--i»-an---"i»teger >  1.  P : The  chromatic  2  integer P : 3  other  graph  i s to construct  particular  classes  o f t h e automorphism  of  generalized  Graver  Petersen  integers  and  edge  n and  set  {u , 0  given  Watkins  automorphism  [12]  a,,  E ( G ( n , k))  defined  on t h e  class.  considered  the  groups  the  as  k w i t h 2 < 2k < n, t h e has been  Usually  g r o u p s depends  graphs which a r e d e f i n e d  g r a p h G ( n , k)  V ( G ( n , k)) = and  integer  graphs.  problem o f c h a r a c t e r i z i n g t h e automorphism  Petersen  the  of the s t r u c t u r e o f graphs i n t h a t  Frucht,  For  an  Y.  problem  construction  knowledge  o f d e g r e e k, where k i s  G i s spanned by a g r a p h I homeomorphic t o a  groups of c e r t a i n the  G i s k, where k i s an  3.  connected  The  of  2.  G i s regular >  :  >  number  t o have  of  follows:  generalized vertex-set  ..., u„_, , v., v, , ..,, v„_, J c o n s i s t i n g of a l l edges o f t h e  16 form  (u , u L  integer  t + 1  ),  (u , v ) , t  and a l l s u b s c r i p t s  However  classes  construction  of  a  of  this  ),  where i  with  an  common  matrices  characteristic  steps*.  a graph i n c r e a s e s r a p i d l y  gets  larger.  Hence  decompose t h e g r a p h construct of  the  i t  as  will  into  those  with  t h e n Mowshowitz*s  most 2  i n constructing  the  polynomials). I f G i s  w i l l c o n s t r u c t t h e automorphism  of  algebraic  for  (i.e.  type with n vertices  difficulty  an  groups of graphs with  algorithm  The  is  modulo n.  algorithm  automorphism  adjacency  m i n i m a l and  graph  graphs  describes  identical  i+ | t  considered.  the  non—derogatory  t  a r e t o be r e a d  of  p r o p e r t i e s c a n a l s o be Rowshowitz[24]  (v , v  t  T(G)  i n at  the automorphism  group  the  group  number  of  vertices  be  desirable  i f  we  can  smaller  component  graphs  and  automorphism  group o f the graph  from  those  t h e component g r a p h s , Harary  groups  of  and  Palmer f 1 8 ]  p r o d u c t graphs  g r o u p s o f t h e component  studied  in relation  the to the  automorphism automorphism  graphs.  Another approach i n c h a r a c t e r i z i n g group o f a graph i s t o f i n d  the  i t s automorphism  * [ p ] denotes as u s u a l t h e g r e a t e s t  i n t e g e r < p.  automorphism partitioning.  17  Weichseir40] the The  considered  a p a r t i t i o n P o f the v e r t i c e s of  graph G which i s r e l a t e d partition  P  to  i t s automorphism  group.  i s c a l l e d a s t a r p a r t i t i o n o f G and i s  d e f i n e d as f o l l o w s :  £®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 satisfies  the  following: (i) I f  Afe-P,  then  a l l elements  of A are o f t h e same  degree. ( i i ) Let a « A € P and b fe B fe P with  a  adjacent  to  b.  f o r each a* e A there i s b» fe B such t h a t a* i s  Then  adjacent t o b*.  The f o l l o w i n g theorem  i s given i n [ 4 0 ] :  Theorem, 1. 8 Let trivial, singleton  G be a graph whose only partition sets).  in  automorphism  partition  i s the  ( i ^ e . /the p a r t i t i o n whose elements a r e  Then G i s an i d e n t i t y  An a l g o r i t h m ?forr f i n d i n g a described  star  £40]. It  star  graph.. partition  i s worthwhile  is  also  t o note t h a t the  p a r t i t i o n o f a graph G i s a s t a r p a r t i t i o n o f  G and the a l g o r i t h m produces only the c o a r s e s t o f a l l s t a r partitions.  A l s o the a l g o r i t h m does not y i e l d anything f o r  a r e g u l a r graph s i n c e i n t h i s case the s e t o f a l l v e r t i c e s of the graph forms the c o a r s e s t s t a r p a r t i t i o n . ,•  18  The  r o u t e t h a t we  characteristic  are  polynomial  going and  adjacency  matrix  o f t h e graph.  are  roots  of  the  totality graph.  list  of  the  The e i g e n v a l u e s o f a  graph  graphs with  i s given  following  theorems are r e s u l t s  v i a the of the  polynomial  and t h e  the s p e c t r u m  eigenvalues  vertices  i s  polynomial  the c h a r a c t e r i s t i c  polynomials o f connected  the  take  minimal  of a l l eigenvalues i s c a l l e d A  between  to  and not  of  the  characteristic more  than  six  i n T a b l e s I and I I o f t h e A p p e n d i x . The  eigenvalues  concerning  o f a graph  the  relations  and i t s a u t o m o r p h i s m  group.  fhgoggj^l^f f 3 6 ] If  t h e automorphism  transitive simple  on  the  eigenvalue  group o f a connected  edges, then  two  non-zero simple  Theorem  r ( G ) and - r ( G )  eigenvalues  G  is  positive  eigenvalue. are  the  only  o f G.  1 ..10 [ 27 ]  Let  G  be  a  graph  A = A (G) , and a u t o m o r p h i s m group  t h e r e i s b u t one  o f G and i t i s t h e l a r g e s t  I f G i s b i p a r t i t e then  graph  of  permutation  e i g e n v a l u e s , then  every  course, implies that The  following  of o r d e r n with g r o u p P=  matrices).  Tt )  {regarded  6  If  adjacency  A  P i n V has order  has two  matrix as  a  n distinct (which,  of  T i s Abelian).  theorem  i s an e x t e n s i o n o f t h e p r e v i o u s  19 one.  1.1.1  Theorem Let  f 3]  G be  undirected,  a finite  with  adjacency  or  matrix,  It  then is  digraphs [17].  (in the  the  not  graphs.  i t  complex  characterize  number  field)  its  are  a  graph  polynomial completely. are  called  Some e x a m p l e s o f c o s p e c t r a l g r a p h s by  can  Harary, be  King,  easily  example t h a t c o s p e c t r a l g r a p h s isomorphic  be  i t s automorphism group. I f  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  are given  Also  be  A = A (G)  or  i s Abelian.  G  does  with  cospectral  P<G)  loops),  (directed  w e l l known t h a t t h e c h a r a c t e r i s t i c  o f a graph Graphs  T ( )  with n v e r t i c e s  without  and  the eigenvalues of A distinct,  graph  automorphism  groups.,  Mowshowitz and  seen do  not  from  and  Read i n  the f o l l o w i n g  necessarily  have  20 Figure  HG,)  = D  1.1; ft P a i r  o f _ C o s p e c t r a l Graphs  r<G ) S s  4  z  character i st i c polynomial = characteristic =  X  s  -  From  4X3  =  the  polynomial  X3 (X  -  2) (X  previous  i n f o r m a t i o n from  chapters  p r o p e r t i e s of the  group.  G  z  we  the c h a r a c t e r i s t i c  the  of  of  example  us t o d e t e r m i n e  polynomial  G,  2)  does not enable following  of  a  minimal graph  4  we  that using only  polynomial  of a  graph  the automorphism group.  are  going  polynomial reflect  see  those  and  t o study  how  In the  characteristic  of the  automorphism  21 IT.  MINIMAL POLYNOMIAL OF THE ADJACENCY MATRIX  In  this  between of  a  chapter,  we  t h e automorphism  will  study  the  relationship  group and t h e minimal  polynomial  x)  denote  graph. We  will  use  characteristic graph  f(G;  polynomial  and  G i n the indeterminate  indeterminate the u s u a l The minimal  i s clear  notation following  polynomial  and  from  p ( G ; x)  minimal  to  polynomial  the of a  x. When t h e d e p e n d e n c e on t h e the context,  we  will  employ  f ( G ) and p ( G ) . theorem  gives a characterization  o f any  of the  graph..  Theorea_2a.1 The  minimal  distinct i.e. the  polynomial  irreducible  the m u l t i p l i c i t y minimal  polynomial  o f any g r a p h  polynomials  o f any f a c t o r  G i s a product of  over  the  integers,  i n the expression  for  i s one.  Proof Let  A  symmetric  also  the  t h e minimal  irreducible is  be  adjacency  matrix  polynomial  of A consists  f a c t o r s over  a product  of  G. S i n c e  t h e r e a l number f i e l d .  of distinct  Ais  of d i s t i n c t Hence  i t  i r r e d u c i b l e f a c t o r s over the  integers.  From polynomial  the of  characteristic  above a  theorem  graph  can  polynomial.  we be  For,  see  that  determined  t h e minimal by  the  i f we have computed t h e  22 c h a r a c t e r i s t i c polynomial of a into  irreducible  simply the Hence  factors  and  decomposed  then the minimal  product of the  cospectral  graph  distinct  graphs  also  theorem  by  polynomial i s  irreducible  have  the  i t  factors.  same  minimal  polynomial. The  following  sufficient  condition  Mowshowitz £24]  f o r a g r a p h t o be an  gives  identity  a  graph.  Theorem_2j 2 L  If  the  characteristic  polynomial  i r r e d u c i b l e over the i n t e g e r s , of  the graph  of  a  graph  then the automorphism  is  group  is trivial.  In t h e next s e c t i o n , i r r e d u c i b l e minimal  we  shall  study graphs  that  have  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  e n t r i e s and on  matrix  a  graph c o n s i s t s o f 0,  hence i s a n o n - n e g a t i v e  non-negative  matrices  m a t r i c e s o f g r a p h s . The in  of  can  following  be  matrix. applied  section.  results  to adjacency  a r e c o n c e p t s and  t h e t h e o r y of n o n ^ n e g a t i v e m a t r i c e s t h a t  in this  Thus  1  are  results relevant  23  !^f^£ill£&£i2*Jr ( c f . [81) ,-, ;  An if  n x n  m a t r i x A (n > 2) i s s a i d  no p e r m u t a t i o n A  PAP-* =  (1  matrix P e x i s t s A  0 where A„ , A  2 2  such  t o be  irreducible  that  (2  A  2 2 J  a r e square m a t r i c e s .  ;  2h®2£§S_2±.3 ( F r o b e n i u s — P e r r o n t h e o r e m [ 8 ] ) Let has  A be an i r r e d u c i b l e  a characteristic  (i)  there i s associated  (ii)  r > 0 such  root  r i n c r e a s e s when any e l e m e n t  (iv)  r i s a simple  Let is  polynomial  Then  A  eigenvector x„;  o f A, JeC| < r ;  of A increases;  root.  p be t h e m i n i m a l  irreducible  matrix.  that  to r a positive  i f ©<. i s any c h a r a c t e r i s t i c  flii)  p  root  non—negative  p o l y n o m i a l o f a graph  of degree  and h a s d e g r e e  and assume  m. I f f i s t h e c h a r a c t e r i s t i c  n, t h e n mjn and  f = p> where k =  n/m.  Theorem_2 ii i  If  G i s a graph  characteristic  w i t h f and p d e s c r i b e d  above  as i t s  and m i n i m a l p o l y n o m i a l s r e s p e c t i v e l y ,  G i s the union of k c o s p e c t r a l connected with c h a r a c t e r i s t i c  and m i n i m a l  identity  p o l y n o m i a l s = p.  then graphs  24  Proof  (By If  Frobenius-Perron G  is  obviously  connected,  root  characteristic  Let  G,  is  the  characteristic  the but  every  Hence G  Then s i n c e f < G , ) | f ,  that  1 < h < k.  1. T h e r e f o r e e v e r y  is  p,  Since  r o o t r, of  component  which  of  implies  we G,  f(G,) G  has  that  the  cospectral.  Theorem 2.2,  identity  maximal  simple;  maximal c h a r a c t e r i s t i c  G are  A is  1.  polynomial  i f p is  graphs.  characteristic of  is  a component o f G.  s i m p l e , so h =  are  f  f o r some h s u c h  h  connected,  By  of  matrix  r o o t o f f i s o f m u l t i p l i c i t y k.  be  components o f  the adjacency  Therefore  r  only i f k =  have f ( G , ) = p is  then  irreducible.  characteristic  connected  Theorem)  irreducible  Since  polynomials  f  is  the  the  components  product  o f t h e components,  the  c f the number  components i s k.  Before  we  study  with i r r e d u c i b l e  the  minimal  the f o l l o w i n g simple  automorphism  p o l y n o m i a l s , we  groups of  graphs  shall first  prove  lemma.  Lemma,, 2.1 If G,,  G,  i s an  identity  t h e r e i s o n l y one  graph  and  isomorphism  G  z  from  is G,  isomorphic to  to  G*.  Proof Let  <r, ,  <r  z  be  two  d i s t i n c t i s o m o r p h i s m s from  G,  to  25 G » 2  0~,  *2  #  <rf <r, # e where e l  implies  i s  the  identity  permutation. Take denote  ( u , v) 6 V (G,) x V(G,)  any  the vertex sets of  E(G,),  E{G )  denote  a  respectively. (u,  v) € E(G,J--,-:!££  ff cr,  is  _,  2  contradicts lemma t h e n  and  the  G  edge  t  V(G ) 2  respectively.  2  sets  of  G,  Let  and  G  a  Then  iff So  G,  where V ( G , )  an  the  (<J7«,  o^y) e E(Ga)  (ffi-i<r; u,  automorphism fact  that  erf* <r, v) t E (G, ) . of  G,  G,  <r-^cr, * e  and  i s an i d e n t i t y  g r a p h . The  follows.  Corollary._2 J[ I  If  G, , G , . . . , G 2  k  are  isomorphic  identity  graphs,  then f{G) = tHG)  S , t h e symmetric  group  k  1  on k e l e m e n t s and  = 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 t h e c h a r a c t e r i s t i c  p o l y n o m i a l o f t h e graph  26 where k i s a p o s i t i v e  i=1  integer.  Then*  i  ana IPCG) | = k, ! k ! ... k ! , 2  for  y  some k, , k ,  k  2  k  k| ^ k  =  r  such  that  •**..-, •+ k y •  2  Proof By collect  Theorem  2.4,  the  components  isomorphic groups  k  graphs  with  k,,  G c o n t a i n s k components. Now  and  into  groups  l e t us assume t h a t  k ,  k  2  connected  r  of  l e t us  mutually  t h e r e a r e r such graphs  in  each  group. Consider vertices set S  the  set  of  automorphisms  except t h o s e o f graphs  i n the  that  i-th  fix all  group.  This  i s isomorphic to . Therefore  k  i r<G)  = S.  + S.  + ...  + S.  and  ir<G) i = k, ! k ! ... k 1 2  w i t h k, +• k He least  x  note  K  • ...  + k-  k.  Y  t h a t Theore  2.5  assumes t h a t  r c o s p e c t r a l connected i d e n t i t y  * See f 1 6 , p.1631 o r S e c t i o n on p e r m u t a t i o n g r o u p s .  1.2  there e x i s t  graphs.  for definitions  of  at  When a l l t h e  operations  27  components a r e i s o m o r p h i c , following  Theorem  such  any p o s i t i v e  that there graphs  Theorem_2 7  For  any  T h u s we  i n t e g e r k, t h e r e  n  positive  are  non—isomorphic,  Reducible,Hinimal  Since  integer  automorphism led  to  connected the  same  minimal raonic  are k cospectral  that  connected  polynomial  there  exist  identity  graphs  i s irreducible.  of the adjacency  matrix of  t o z e r o , we s e e i m m e d i a t e l y  polynomial  o f a graph  polynomial  x and t h i s  i s a void  graph.  we c o n s i d e r  quadratic.  k there  Polynomial  i ft h e graph Next  an i n t e g e r  a l l having  conjecture  the diagonal entries  must be t h e  is  The  group.  cospectral,  a r e always equal  the  exists  k non-isomor phic  vertices  w h o s e common c h a r a c t e r i s t i c  only  1.  polynomial.  graphs with given  if  to  [ 2 2 ]  I  graph  equal  i n [ 2 5 ] and [ 2 2 ] ,  are at least  with  characteristic  a  r  2,_6 [ 2 5 ]  regular  2.2  have  theorems a r e proved  Given n  we  t h e case  that  i s linear  then i t  i s  i f and  true  when t h e m i n i m a l  polynomial  28 Thgorem_2.8 Let graph n/(1  p = x  G with  • ax + b  2  n vertices.  be  Then  - b) c o p i e s o f c o m p l e t e  the minimal  polynomial of a  b < 0  G  consists  of order  1 - b and  graphs  and  of  (x + 1) (x + b ) . ,  p = Proof If  A i s the adjacency  m a t r i x o f G, we  have  p = xz • ax + b and A  * a A + b i = 0.  2  Let then  B = [ b ^ ] = A*;  (i) h  = degree  iL  <ii)  b : t  of vertexi ,  = number o f v e r t i c e s a d j a c e n t t o b o t h i and j  0"  * j) •  Ci Since  B = -aA - b i  r e g u l a r o f degree Let i  and  a-^ = 0,  <i)  implies G i s  -b and s o b < 0.  E(G) be t h e edge  set  of  # j , t h e n t h e number o f v e r t i c e s  j e q u a l s 0; and  i f  ( i , j) 4 E ( G ) ,  G. , I f  adjacent t o both  ( i , j ) e E{G),  then  the  i and  number  of  v e r t i c e s a d j a c e n t t o b o t h i and j e q u a l s - a . Now  take  4  <i, j )  S;, =  a n y two v e r t i c e s  E(G).  i and j ( i # j ) s u c h  that  Let  (k| ( i , k) € E ( G ) } ,  S-^ =  {kf ( j , k) € E <G)} .  Clearly Si  A  <p.  S^ =  Take any two v e r t i c e s (k, 1) 4  E  ( )  adjacent t o both  G  implies  k, 1 e S . .. t  that  t h e number o f v e r t i c e s  k and 1 i s 0, b u t i i s a d j a c e n t t o both k  29 and  1,  so  (1c,  we  must  1) fe E(G) .  Therefore A l s o every S  t  U  -a, the  every  vertex {i}  Since is  of order  pair  in  of v e r t i c e s  i s adjacent  i s a complete  the  in S  order  o f S^  f o r S^  0  but  adjacent.  to i ; hence  graph.  f i } i s -a +  t o both  k and  1  2.  0* { j } .  G c o n s i s t s o f n/(2 2 - a;  is  t  number o f v e r t i c e s a d j a c e n t  Similarly So  have  - a)  c o p i e s of complete  G i s regular of  d e g r e e -b,  graphs  so  -b = - a *• 1. Therefore  G c o n s i s t s o f n/(1  graphs of order Now  -b =  copies of  complete  1 - b.  -a +  Therefore  - b)  p = =  1, so t h a t x  + ax  2  a = b +  • b = x  2  *  1. (b +  1)x  • b  (x * 1) (x + b ) .  Corollar2_2^2 If graph  p =  G with  (x +  1) (x + b)  n vertices,  i s the  minimal polynomial  of  a  then*  res) = s w rs,_ i b  1-b  and  | T(G) ! =  (n/(1  - b))!((1 -  * See [ 1 6 , p. 164] o r S e c t i o n p r o d u c t A [ B ] o f A a r o u n d B.  1.2  b)!)V(i-b).  for a definition  of the  wreath  30  Now  let  defined  in  us  consider  Section  characteristic  some o p e r a t i o n s  1.2)  and  their  on  graphs  (as  on  the  effects  p o l y n o m i a l s o f t h e component  graphs.  D e f i n i t i o n , 2. 2 A to  graph  G i s said  have i n t e g r a l  t o be i n t e g r a l  spectrum)  (or, e g u i v a l e n t l y ,  i f a l l the eigenvalues of G are  integers.  It  f o l l o w s from D e f i n i t i o n  characteristic only  polynomials  of l i n e a r The  Theorem  theorem  t o Sachs [ 3 4  G  be  vertices,  then  f(G;  x) =  Corollary._2i3  The  an  integral  minimal graph  and  consist  on  complements  of  regular  1.  2._9  Let  If  that the  factors.  following  g r a p h s i s due  of  2.2  a  regular  (-1)"  graph  f  o f d e g r e e r and  (  G  .  _  x  .  with n  1 ) #  j- i g ]  a regular  graph G  following results  i s integral  t h e n s o i s G.  a r e p r o v e d i n [ 3 5 3 and [ 1 9 ] ,  31 Theorem_2 .10 [ 3 5 ] i  Let the  f ( G ;  x) = 7 T ( x -  characteristic  TT(x - yUj)  X ) a n d f { H ; x) = L  polynomials  of  two  be  G and H.  graphs  Then* x H; x) =  f  A H; x) = TT]T(x -  (G  * H; x) = T T T T ( x  f<G  Corollary  G,  A  *i  TTTTCx -  f(G  Kfo  -  - Ai  .  2.4 [ 1 9 ]  If  G,  G  and  z  Xifo)  G  and G,  G  *  2  are  2  then s o a r e G , x G  integral,  2  ,  .  Theorem_2 1J [ 3 5 ] i  If and  G, and G  with  are regular  z  n, a n d n  2  vertices  graphs  o f degrees  respectively,  r  and r  (  2  then f <G, ) f (G ) 2  f(G,  + G ; x) = 2  (x* - (r, + r )x + r, r z  A  - n, n ) , 2  x  y  x  _  y  .  C o r o l 1 a r _ 2^.5 [ 1 9 ] 2  The and  join  G, • G  o n l y i f both (r,  - r  2  )  2  2  o f two r e g u l a r  G, and G + 4n, n  2  4  graphs  i s integral i f  a r e i n t e g r a l and  i s a perfect  * See [ 3 5 ] and [ 1 6 ] f o r d e f i n i t i o n s g u o t e d i n t h i s theorem.  sguare.  o f t h e o p e r a t i o n s on  graphs  32  with ( ) 1  Next,  we  are  linear  factors i n their  Complete^graphs  going  to c o n s i d e r f a m i l i e s o f graphs minimal p o l y n o m i a l s .  and v o i d _ g r a p h s  L e t n be > 2. Then f <K„; x) = (x - n + 1) (x + 1 p ~ , so t h a t l  P(Ky,;  The  x)  =  (x  *  1) (x -  complement K  of  w  n  K  +  1) .  i s  M  the  void  graph  on  n  vertices. fiKy,; x) = x" and p {K„; x) = x. Therefore K„  a l l f a c t o r s o f t h e minimal p o l y n o m i a l s of  and K„ a r e l i n e a r f o r n = 2, 3, .... A l s o  only  void  connected  g r a p h s can have l i n e a r graphs  with g u a d r a t i c  minimal minimal  we know  that  p o l y n o m i a l s , and polynomials  are  complete. , Since  =  r<KJ and  (ii)  Let f16,  ITCK,,) I = n!.  bipartite K  p. 17])  W ) 1  gra£hs  denote  the  on V, and V  2  f C K ^ ^ ; x) =  (x  -  2  complete  where  S c h w e n k [ 3 5 ] h a s shown  which  , we have  = TtKv,) •= S*,  IRKJ I =  Complete  and [-(*„) =  bipartite  | V, j = m,  graph (see  |V | = n. Z  that  mnjx™*"-  2  implies pCK^ ^ ; x) = x ( x Therefore K „  B  2  - mn)  f o r m • n > 2.  i s integral  i f and o n l y  i f  mn  i s a  33 perfect  square.  Also  i f m - n,  K  m  ^ and K  W j W >  are both  are  actually  integral.  f(K«,, ; w  and  X) =  (X -  B + 1)2(X + 1 ) Z " - 2 ,  x) =  (x - • • 1) (x + 1) .  for m > 1 P<K„  ;  # W 1  Since  „ = K  particular If  M  + K , w  t h e above r e s u l t s  cases of C o r o l l a r y  2.5.  m # n, t h e n by C o r o l l a r y 1 . 1 ,  r(K  M > w  ) = T(KJ  • R K « ) = S „ + S,..  Therefore  i T f K ^ , ) I = n!n!.. If  m = n, =  2K r(K  Hence  and- IRK*,, J I When claws  m =  implies  m  m > w  =  J  m < w  = n^, )  )  =  w  =  S J S J .  S [S ] 2  W  f r ( K . « ) l = 2(m!)2.  1,  (or s t a r s ) .  n i s a perfect  r(K  w  n > 2, The s t a r  the r e s u l t i n g K,  s q u a r e , i n which  graphs  i s i n t e g r a l i f and o n l y i f c a s e we have  P ( K „ ; x) = x ( x * - n) , 1(  r(K ana (iii)  ir(K  l>w  l(Y  ) = s„,  ,) \ = n!.  Cubes Let  Q  w  denote  are called  t h e n — d i m e n s i o n a l cube.  Then  34  n terms It  h a s been  f (Q„;  x)  =  proved  i n [35] that  <x - n + 2 i )  T T  and  i=0 n P(Q :  x) =  n  (x - n + 2 i ) .  T T  i=0 Thus Q„ i s i n t e g r a l  f o r a l l n.  Since  o f degree n f o r  have t h a t  Q Q  w  i s regular i s integral  M  By Theorem f  2.9,  n  have  (x - 2  also  * n • 1)  <">  "  , +„ + ,  x  we  f o r a l l n.  x - z * y, + ,  <Q«! > = =  we  a l l n  TTl-x - 1 - n • 2i) T T  (x + 1 • n - 2 i )  i=1 For  n =  1, p (Q, ; x) =  n = 2, p ( Q ; 2  x) •=  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 (for [16,  a  following definition  t h e o r e m has been p r o v e d of  the  exponentiation  by  Palraer[29]  group,  see  p. 1 7 7 ] ) .  Theorem If  2.12 G  is  product defined  connected  and  p r i m e <with r e s p e c t  i n Section  1.2), t h e n  t o the  35  nc*)  r.  = trie)  Coro!lary__2. 6  HQ*) ana  =  = fS 1  T(QJ  | HQJ I =  a  I T(Q J I = n ! 2 . w  Proof This  f o l l o w s i m m e d i a t e l y from  the  fact  that  K  2  is  p r i m e and It B 1 I =  | AJ • fBJ*  A  where group  d  is  t h e s i z e o f t h e s e t on w h i c h t h e p e r m u t a t i o n  A acts. When n = Q  2, K  = 2  K  X  2  =  2  C . 4  Therefore f <c4;  i\)  2  TT (x - 2 + 2 i )  x) =  i=0 = x * ( x - 2) (x + 2) , and  p ( C ; x) = x ( x - 2) (x + 2) . +  S T( 4)  Also  C  =  on f o u r e l e m e n t s ,  T{C ) 4  = [S ] z  2  =  D , 4  the dihedral  group  and hence  | R C ) I = ir<C ) I = 8. 4  (iv) T r e g s o f diameter  4  3  If T i s a tree that  w i t h d i a m e t e r 3, i t  T's c e n t e r i s a p a i r  is  easy  of adjacent v e r t i c e s .  T i s completely characterized  by t h e d e g r e e s  of  to  see  Moreover, the  two  36  center  vertices.  The the  following  characteristic  proved  theorem c o n c e r n i n g t h e c o e f f i c i e n t s of polynomial  of  an  arbitrary  tree  is  by Mowshowitzf 2 5 ] .  Theorem_ 2 ..13 Let k-th  T  be a t r e e  coefficient  a  fe  o f o r d e r n, t h e n f o r 0 < k < n, t h e  of  n f (T) i=0 is  g i v e n by (-1) h <T), V  r  i f k = 2r f o r some r > 1;  LO, o t h e r w i s e , where  h ( T ) = number r  of  collections  of  r  nonadjacent  edges i n T.  If  T  is  a  tree  of  diameter  degrees o f the c e n t e r v e r t i c e s f (T; x) = x  m + v ,  -*(x»  -  3, and m, n a r e t h e  then  (m + n - 1 ) x * +  {m -  Proof h, (T) = number o f e d g e s i n T = m + n - 1 . Obviously, h  2  (T) =  (m - 1) (n - 1)  and  h (T)  for  a l l r > 3.  r  =0  Therefore  1) (n - 1 } ) .  37 f(T;  x) = x + » w  -  x  W  +  -  r , _ 4  (m + n - 1) x^ *"1  t  4  X  Figure  _  (rn  +  n  -  * (m - 1) (n -  2  1)x  *  2  (m  -  1)  (n  -  1)x*+"-» 1}).  2. 1 : \ A , T r g e o f _ D i a f f l e t e r 3 i  i-i  £orollarj_2 8 A  If degrees only (i)  diameter  3,  of the center v e r t i c e s , then  i fthe following <m + n - I ) for  (ii)  T i s a tree of  2  are the  2  k, and k then  ((m + n - 1) • k)/2 and ((m + n - 1) perfect  n  T i s i n t e g r a l i f and  1) (n - 1) = k  i f <i) h o l d s f o r some i n t e g e r  are  m,  are satisfied:  - H{m -  some i n t e g e r  and  k)/2  sguares.  Proof Obvious In theorem.  from  t h e c h a r a c t e r i s t i c p o l y n o m i a l o f T.  particular,  i f  m = n  we  have  the  following  38 Theorem  2.14  If center and  T i s a t r e e of diameter  3, and t h e d e g r e e s  v e r t i c e s a r e b o t h e q u a l t o m, t h e n  of the  T i s i n t e g r a li f  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 If  m = n = p  2  • p • 1 f o r some  positive  integer  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 - 4 p  s  (2p +  Let  k = 2p • 1. Then  <{m  + n - 1) + k ) / 2 =  = and  4pz • 4p + 1 =  I) . 2  (2p  2  2p + 1 + 2p + 1)/2  (2pz * 4p + 2)/2 = pz + 2p + 1 = (p • 1 ) z ,  (<m + n - 1) - k) /2 = = p z , which Now  (2pz • 2p #• 1 - 2p - 1)/2  implies T i s integral.  suppose T i s i n t e g r a l .  (m + n - 1 ) =  2  2  Then  - 4 (m - 1) <n - 1)  (2m - 1 ) z - 4 (m - 1) z  must be a p e r f e c t Now  square.  (2m - 1) z - 4 (m - 1)  = 4m  z  - 4m * 1 - 4m  2  2  + 8m - 4  = 4m - 3. If ((m  4m - 3 = kz  + n -  perfect  1)  k)/2  sguares.,  for and  some  positive  integer  {(m • n - 1) - k ) / 2  k, t h e n  must  be  39  Let tin  + n - 1) + Je)/2 =  - 1) + k ) / 2 = q  <{2m  <(m • n - 1) - k ) / 2 = ((2m - 1) - k ) / 2 = p for  some  positive  integers  p  2  2  and q. O b v i o u s l y  we  have  g > P. Then and  p q 2  2  p  • q  2  p  2  1,  =  ((2m - 1 )  =  (4m  2  - 4m + 1 - 4m • 3) /4  =  (4m  2  - 8m + 4 ) / 4 = m  Therefore and  = 2m -  2  + q  2  2  - 4m  + 3)/4  2  - 2m • 1 =  1,  so t h a t  which  of  the  integral center  Appendix. tree  unegual  v e r t i c e s a r e more d i f f i c u l t  a l l integral trees  of  + p • 1.  2  trees of diameter 3 having  f o r the center  of o r d e r  From  implies  q = p + 1.  Hence m = pq + 1 = p (p + 1) «• 1 = p Integral  2  m - 1 = pg  = 2 ( p q • 1) - 1 = 2pq * 1,  (p - g ) 2 =  (m - 1) ,  to find.  < 500 i s g i v e n  this  o f diameter 3 with  we  see  degrees A  list  i n Table I I I  that the smallest  unequal degrees  f o r the  v e r t i c e s i s one w i t h  m = 5 1 and n = 99. The be  automorphism  determined  havinq  group o f a t r e e with  quite e a s i l y .  center  vertices  I f T i s a tree of  = s _, m  I T"{T) ! =  diameter  3  o f d e q r e e s m and n r e s p e c t i v e l y ,  then  pro  diameter 3 can  + s„_,,  (m - 1) ! (n - 1) ! f o r m * n;  no  and  n?)  S  S [S .J 2  1r(T) J =  (v)  Subdivision Let  G  M  2<(m  2  g r a p h s of s t a r s  for m =  are  2.2:  going  ly  Subdivision to  use  n.  K,  denote the s u b d i v i s i o n  M  Figure We  - 1)!) ,  the  graph  Graph  of  K,  o f K,  following  4  theorem  by  S c h w e n k [ 3 5 ] to compute f { G „ ; x ) .  Theorem  2.15  Let collection  v  be  a vertex  o f a g r a p h G and  of c y c l e s containg  f{G) •= x f (G -  V)  -  l e t C(v)  v. Then  2  f (G - V  -  u ad j v where V(2)  2  Z  Z6C  f(G  - V(Z))  {V)  i s the set of v e r t i c e s contained  i n Z.  be t h e  41 Corollarj_2 9 j L  f ( G „ ; x) = x ( x  2  - n - 1) (x - 1 ) " - i ( x  • 1)"  Proof Let  v be t h e v e r t e x  consists  o f degree n i n  of n copies of K . a  G-„.  Then  G», - v  Therefore  f (G„ - v; x) •= (x - 1 ) " (x + 1 ) . . w  For  any  isolated  u  adjacent  v e r t e x and n - 1  t o v, G„ ~ u - v c o n s i s t s copies of K . . a  Hence f (G„ - v - u; x) = x (x - 1)* -» <x + 1 p 1  Since there are n v e r t i c e s Z  o f an  adjacent  .  t o v,  ftG,, - v - u ; x) = n x ( x - 1>*>-»(x •  I)"  -  1  .  u adj v S i n c e G„ i s a t r e e , So we  C{v) = <f>.  have  f ( G „ ; x) = x ( x - 1 ) " (x + 1 ) - n x ( x - 1)"-»(x w  + 1)* ~  l  = x (x - 1)" - i (x • 1)* - i ( ( x - 1) (x + 1) - n) = x{x - I)*--*<x  +  1)"- (x l  Thus G^ i s i n t e g r a l i f and o n l y square,  i . e . when n = p  I t i s obvious  2  - n -1).  z  i fn + 1 i s a  - 1 f o r some p o s i t i v e  perfect  i n t e g e r p.  that  r<G„) = S„ a n d i r ( G „ ) I = n!. Obviously, not them  fall  into  are  there are other  any o f t h e above  i n t e g r a l graphs mentioned  which  families.  do  Seme o f  composite graphs o f i n t e g r a l graphs such as t h e  one shown i n F i g u r e 2. 3.  42  K, + 3K  f (K,  + 3 K ; x) =  (x - 1 ) { x + 1 ) 3 (x + 2) (x - 3) 2  2  Some o t h e r i n t e g r a l classified  a  graphs  which  a r e shown i n F i g u r e 2.4  (i)  have  not  (see a l s o  yet  been  [19]).  (ii)  <  o  f(C ; 6  x) = (x - 1 ) { x + 2  1)2(x  - 2) (x * 2)  f (G; x) = x (x + 1) (x - 1 ) (x + 2) ( x - 3) 2  Figure We  note  2.4: ,..,Tvo_Hore_Intggral_graphs  that  C  design with parameters Obviously  2  many  6  = TT{3, 2, 1 ) ,  t h e symmetric  block  v = 3, k = 2 and A = 1.  graphs  that  have  both  linear  and  non-linear described  factors  and  l e t C(uv) The  by  Schwenkr35]  We  of G j o i n i n g the v e r t i c e s  be t h e s e t o f a l l c y c l e s  containing  and this  satisfies  2 2 f (G - V(Z) ) Z«C{uv)  i s the set of v e r t i c e s contained  shall  use  characteristic (n > 3)  this  theorem  to  j o i n i n g any 2. 16, we  f (Ry\ - uv) = f + 2 =  two  vertices  compute  the line  u and v.  have + f (K* - u - v)  Z f l K * - V(Z)) Z*C (uv)  (x - n + 1) (x + 1 ) " - *  + (x - n + 3) {* • 1) ~ 11  + 2 Z be  i n Z.  p o l y n o m i a l o f K „ - uv where uv i s t h e  By Theorem  Let  u  = f (G - uv) - f{G - u - v)  where V (Z)  M  a theorem  c h a r a c t e r i s t i c polynomial of G  -  K  (v) above.  the c h a r a c t e r i s t i c polynomials o f a  uv d e n o t e a l i n e  f(G)  in  o f graphs  2.16  let  line.  i n families  of graphs.  Theorem  v  found  a r e going t o s t a t e  use i t t o compute  family  be  i n ( i i ) , ( i v ) and  Next we and  can  a cycle  £ f (K„ Z6C (UV) of length  3  V(Z)).  k + 2 containing  uv.  Then  ffK„ - 7 ( Z ) ) =  <x  Obviously f (K,, - uv)  =  - n • k •  there  t,_2.P  are  (x - n + 1 )  3) (x +  (x  k  1 ) * -  K  - 3 .  such c y c l e s ;  * 1)"-*  +  therefore  (x - n + 3) (x +  n-2 + Using equivalent So  we  f (K  M  2 I k« <"-*) *= 1  induction  we  <x  - n  can  t o x (x • 1 ) * - 3 ( x 2 -  • k + 3) (x + 1 ) " - ~ 3 . k  show t h a t t h i s (n - 3) x -  expression  2 (n - 2) ).  have - uv)  =  x(x  • 1)"-3{x* -  (n - 3) x - 2<n  - 2)) .  is  45 III.  ADJACENCY MATRIX AND AUTOMORPHISM GROUP  Two main t o p i c s First  we w i l l  spectral  will  look a t graph  properties of  relationship adjacency  be  studied  in  and  chapter.  properties that correspond  the  adjacency  matrix.  between t h e c h a r a c t e r i s t i c  matrix  this  the  Then  polynomial  automorphism  group  to the  o f the  will  be  examined.  3.1  S p e c t rum_of _a_Grap_h  As d e f i n e d i n S e c t i o n the  set  adjacency  of  a l l eigenvalues  matrix;  the l a r g e s t  the index  characteristic  that  spectrum.  o f a graph  repetitions) G, d e n o t e d  be  theorem, r i s a s i m p l e  polynomial  this section,  can  (with  o f a graph i s of the  by r , i s  v a l u e i n i t s spectrum. I f G i s connected,  by t h e F r o b e n i u s — P e r r o n  In  1.5, t h e s p e c t r u m  root of the  o f A.  we w i l l  characterized  consider by  the  The f o l l o w i n g theorem i s  graphs with s m a l l  then  a  graph  properties  properties simple  of i t s  result  for  index.  Theorem 3.1 If  r < 2,  If  G, i s a component o f G w h i c h i s n o t a t r e e t h e n  then every  component o f G i s a t r e e .  Proof  contains a cycle, Let  b  G,  s a y v, , v , ...» v , v . 2  p  (  be t h e e i g e n v e c t o r f o r A(G,) c o r r e s p o n d i n g t o  46  r, , t h e i n d e x entries  o f G,,  such  b  in  that  b, , b , 2  corresponding  to  ...,  b  are  f  the  v, , v , ..., v , 2  p  respectively. By t h e F r o b e n i u s - P e r r o n Theorem, a l l e n t r i e s o f Jb a r e positive,  and s i n c e ( i ) v, (ii) and  (iii)  to v , v , t  p  Vp i s a d j a c e n t t o v, , v _, , p  f o r i = 2, 3, ... , p - 1, Vi  we  i s adjacent  i s adjacent to v _, , v t  i+ )  ,  have r , b, > b  and  t  +  bp  r, bp > b,  •  b _,  r, bj, > b _ ,  • b  p  t  f o r i = 2, 3,  £+ l  p - 1.  Hence p p r , i b i > 2 j b,  i=1  i=1  w h i c h i m p l i e s r , > 2; b u t r,  < r i m p l i e s r > 2. So f o r r < 2 e v e r y Smithf36]  proved  component o f G must be a t r e e ,  a stronger r e s u l t  as stated  in  the  f o l l o w i n g theorem.  The component in  index  of  a  graph  o f G i s a proper  F i g u r e 3.1.  is < 2  subgraph  i f and o n l y i f e a c h  of one o f  the  graphs  47 (a)  (b)  (c)  (3)  (e)  (f)  Fiqqrg 3 1?,^Graplis_jg4tfe-l5i§3?,2 m  The  Theorem  following  be  r  (ii)  be  the  n vertices, the  minimum,  vertices. (i)  g*,  theorem  i s qiven i n [ 5 ] ,  3.3  Let with  A  ih  2cos  index  and l e t g  mii>  averaqe,  Then t h e f o l l o w i n g < q < r < q T .  We w i l l  m  of a f i n i t e , , q and and  q  connected  m a - x  maximum  inequalities  t  graph G  respectively,  degree  of  the  on  the  hold;  „ ,  <r < n - 1.  now p r e s e n t some o t h e r  inequalities  48 index  of  attain  equalities.  Theorem  a  graph and c h a r a c t e r i s t i c  those graphs  which  3.4  If  k  i s t h e maximum  d e g r e e * o f a c o n n e c t e d g r a p h G,  t h e n r« > k > r . J  Proof From Theorem  3. 3, we have k > r .  Now l e t A(G) be t h e a d j a c e n c y m a t r i x o f G w i t h set  {v, , v , . .,, v„} i n w h i c h v, i s o f d e g r e e 2  {a, b  b , ..., b „ ) *  zt  3  associated  Z  UK  [i \ v  Therefore  eigenvector  of  A(G)  = a +  b  c  i s a d j a c e n t t o v, }.  c  |K| = k.  Now f o r e a c h rb;  the  k. A l s o l e t  with r .  Then r a = where K =  be  vertex  Z  i  t K,  b;  where K- = { j j v- i s a d j a c e n t t o v , j # 1}. t  L  Hence r i b ' i*K  =  Z a + Z i€K i«K  Z  b;. K  L  By t h e F r o b e n i u s - P e r r o n Theorem, a > 0 and b  * T h e maximum d e g r e e o f a g r a p h G w i l l C o r o l l a r i e s 3.1 and 3.2.  ;  > 0 for  a l s o be d e n o t e d b y  k  in  us  ^] — 2 j  3^  «* • r  n*  Therefore r a  > ka  2  and  r  > k.  2  Corollar2_3 J i  G is  a  is  a connected  graph w i t h r  2  = k i f and o n l y i f G  claw*.  Proof I f G i s a claw  with  n vertices,  k = n - 1 and f ( G ; x) = x - ( x h  r r  = «/n - 1, and  2  then  - n + 1). T h i s  2  implies  thus  = k.  2  Now  assume t h a t  r a  = ka +  2  £ i€K  r  •= k. Then we  2  £ b; , w h i c h jeK  have  implies  L  2 Z L = 0. From t h i s ifcK jfeK *• b  i t follows  that  i f K•  * </>  L  for a l lj 6  bj_ = 0  K , i t K. L  Since G i s connected s o t h a t K-  L  v,  = <f> f o r a l l i * K, and v  for a l l i Therefore  {v, 3 0  * See p.33  b^ > 0 f o r a l l j = 2 , L  3,  i s adjacent  n, only  to  K. the  induced  {v | i * K] i s a L  f o r the d e f i n i t i o n  subgraph  claw.  o f a claw.  with  vertex  set  50  deg v, = k , deg v^  Now that  no  other  vertices fact and  vertex  i n {v, } U  = 1,  in  G  for  a l l i £ K  i s connected  [v^ j i t K} ; but t h i s  that G i s connected.  Hence V(G)  =  implies  t o any o f t h e  contradicts  the  {v, } U f v | i e K} , c  G i s a claw.  Corollar2_3i.2 G i s a connected regular  graph with  r = k i f and o n l y i f G i s  o f degree r.  Proof If Now  G  is  r e g u l a r o f degree r , then  obviously  assume r = k , d^ = d e g r e e o f v e r t e x  adjacency Also associated  matrix  of G  with  vertex  (b i  with  r . Then we  d, = k , and s e t {v, , v , 2  •  b , • •  let  $  V j _ with  4  be an  2  have  a,, b,  +  a  •  b,  2 l  h  a a  l 2  2 2  b  2  b  a  +  . • •+  • . . .*•  a  a  a  .» b,, 2 v ,  b  «  =  rb, rb  4  •  • a«, b, Rewriting  K we  + . . .+ have  a„„b„  rb„.  k  is  the  v }.  eigenvector  M b , , b , . • •» b ) » = r ( b , , b , ...» b,,)' i.e.  k = r.  M  51  (a,,  - r)b, +  a , b,  •  a*,  •  a  bi  a (a  i a  2 l  a  b  2  - r)b  H 1  4  b  + .... +  a  l h  * ... *  a  2 ) )  + ... +  t  b b  B  = 0  h  = 0  (a„„ - r ) b„ = 0.  Clearly, n (( £ a , ) - r ) b , • i=1 v  n  M ( I a  i  h  i=1  This  )  i=1  KX  4  - r i b , = 0.  (d  2  - r)b  Now r = k i m p l i e s b  L  2  • ...  1, 2,  ...,n.  > 0 f o r a l l i = 1, 2, ..., n ,  In Theorem  3.3,  we  n.  know  graph G s a t i s f i e s  2 c o s ^-TT  ( d * - r ) b „ = 0.  r > d^ f o r a l l i =  d; = r f o r a l l i = 1, 2,  connected  - r ) b • ...  implies  (k - r ) b , +  Since  n  {{ I a )  that  the  the following  index  not  is  a  ^ r < n - 1.  not a t r e e .  a tree  of  ineguality:  By Theorem 3.1, t h e l o w e r bound c a n be r a i s e d G  r  Hence, f o r any c o n n e c t e d g r a p h  to 2i f which i s  we h a v e  2 < r < n - 1. Obviously possible  f o r any g r a p h w i t h n v e r t i c e s , t h e  degree  is  n - 1 .  So  i f  r = n - 1,  maximum then  by  52 Corollary  3.2, G i s r e g u l a r o f d e g r e e  Now  any  for  graph  must be a s u b g r a p h uv  4 E (G) By  G which of  i . e . G = K„.  i s not t h e complete  K„ - uv  for  some  uv  such  Probenius-Perron  Theorem,  we know t h a t t h e  index  of G i s l e s s than or equal t o the index of  which  i s equal t o (n - 3 • Vfn  - 3)  • 8 (n - 2)} /2  2  So we h a v e t h e f o l l o w i n g graph G which  The should  that  . the  r  graph, G  inequality  i s not t h e complete  < (n - 3 + V ( n - 3 ) spectrum  (see  K  h  - uv,  S e c t i o n 2.2).  f o r t h e index r  of  a  qraph:  + 8 (n - 2) }/2.  2  o f a q r a p h c o n t a i n s t h e i n d e x and hence  p r o v i d e more i n f o r m a t i o n  on t h e  structure  as stated  i n f 7 1,  of  the  graph. The  following  how a r e g u l a r  theorem,  indicates  g r a p h c a n be r e c o g n i z e d by i t s s p e c t r u m .  Thgorem_3,5 Let graph if  { X, = r , X  * , 3  Z T  A,,} be t h e  spectrum  of  a  G, where r d e n o t e s t h e i n d e x o f G. Then G i s r e g u l a r  and o n l y i f n 1=1  More  results  on  means o f i t s s p e c t r u m The  foregoing  the c h a r a c t e r i z a t i o n  o f a graph  by  c a n be f o u n d i n [ 5 ] , [7"I and f ^ 1 ] »  results  on c h a r a c t e r i z a t i o n  of a  graph  53 by  means  of  computation Usually  i t s spectrum  of the  some  i n computing  its  spectrum.  graph  2  =  U = i»  u ,  be  graph.  o f a graph  will  p o l y n o m i a l , and  the  8e  a  p  that (Vv„ , v + I  calculation  will  graph  2  the w + 2  ,  2 w  j = 1» 2,  7, =  }  are  Up}.  4  , vp  M  sets v  (u, , u ,  t  the  the  thus  symmetrical p r o p e r t i e s of a  show  of  the  one method i n  with  u ; v,, v , •>., v ; v  2  (v  That  vertex  ,, v  m+  > n+ 2  ,  ,»,, v  set l m  }  fv, , v , ...» v^,}  and  z  symmetrical i s  to  about  say,  for  m, € E(G) i f f ( v  < ^ , + e E(G) and  the  polynomial,  G  such V  [5],  on  c a n be done.  Let fu,,  of  of the structure  have been used t o s i m p l i f y  this  depend  roots  i t s characteristic  In  characteristic which  characteristic  knowledge  help  obviously  w+ i  ,  V w ) 4  .) 6 E(G),  i f f i v ^ , v^ )  c  E(G),  f o r any v e r t e x u € U, (v , L  u) € E(G) i f f (v^ , +l  Hence we can p a r t i t i o n follows: "c  A =  C = P = Q =  R  R"  R»  P  Q  . R«  Q  P.  3 1 3  u) € E ( G ) .  t h e adjacency matrix  A(G)  as  54  E = and  C;  1  i f u  0  otherwise,  1  i f v  •{0 9 ii  L  t  i s adjacent  t o U: ,  i s adjacent  i,  1  i f vi i s a d j a c e n t  0  otherwise,  1  i f u  0  otherwise,  to v  m +  j =  to  1, 2 , . . , , in;  ., i ,  i s adjacent  2, ..., p;  to v^ ,  otherwise,  t  1,  i ,j =  j = 1, 2, ...,  m;  , i - 1, 2, p, j 1, 2, «.,, m, =  Let  I be t h e i d e n t i t y  matrix  xlp det(xl  -R  - C  - A) = d e t  o f o r d e r 2m -R  xi*, - P -R» xl  = det  -Q xl  m  -R  - P - Q  -Q  x l  -R*  XI*, - P - Q  m  - C  -H»  XI  m  polynomial  of  A  is  reduced  - P  - P - Q  -Q  0  x l  fxlp  of  the to  w  - P • Q  - C  -R« calculation  m  -R  = d e t (xl„ - P + Q ) d e t  the  X l  -2R  0  Hence  " P.  -2R  -R»  xlp = det  -Q  - C  p  • p. Then  -2R X l  m  - P - Q  characteristic calculating  the  55 characteristic matrices. method  polynomials  o f two  following  example  The  more  ( t h r e e i f E = 0) will  illustrate  clearly.  Example 3.1 Consider  t h e g r a p h G shown i n F i g u r e 1  3.2.  2  4  3  F i g u r e . 3 . 2 : ,A ,Graph_with_Symmgtry Here U =  {5} , V  =  { 1 , 4}, V  =  C =[0], 0  1  .1  0  0 .1  1 1  P =  Q =  det(xl  2  =  fx I,  x  0  0  x + 1  - P + Q) = d e t  - C  •  -2R  det -E'  X(X  x l  2  - P - Qj  1) ,  smaller  {2, 3 ) ; s o  this  56  x  -2  -2  = d e t -1  x  -2  1-1  -2  x3  =  - x  x - 1  - 8x + 2.  z  Therefore f (G; x) = x ( x + 1) ( x 3 - x = x(x + 1 ) ( x 2  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  In  this  section  characteristic graph  will The  Theorem  - 8x + 6)  - 2x - 6 ) .  and , Automorphism Group o f a Graph  the  relationship  be s t u d i e d  group  the of a  in detail.  theorem  i s p r o v e d by Howshowitzf 24 }.  3.6 D  be  automorphism  a  group  digraph T,  with  adjacency  and c h a r a c t e r i s t i c  n; and l e t k be t h e number o f  there e x i s t s For  a p o l y n o m i a l o f degree  simplicity  sake,  we w i l l  discussed  in  we w i l l  need  of  restrict  lemmas.  T .  Then  ourselves to  to digraphs w i l l  n e x t c h a p t e r . B e f o r e we p r o v e some  A,  k dividing f.  graphs; the g e n e r a l i z a t i o n the  matrix  polynomial f of  orbits  undirected  theorem  between  p o l y n o m i a l and t h e a u t o m o r p h i s m  following  Let  degree  2  2  be  the next  57 Lemma_3.1 If  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, and i f  B, S (R may for  v- , v^ t  the  be e q u a l t o S) a r e any two o r b i t s o f 6  H,  then  B,  number o f v e r t i c e s i n S a d j a c e n t  t o v-  - t h e number o f v e r t i c e s i n S a d j a c e n t  t o v•.  Proof If  V;, ,  v- e R,  then  there  Take any w e S s u c h t h a t (V , L  and  since  =  w) 6 E CG)  exists  i f f (Vj , <r{w)) € E ( G ) ,  <r(w) e S, we  have t o V;_  number o f v e r t i c e s i n S a d j a c e n t  t o j. *  We d e f i n e  that  (v^ , w) € E (G) , Then  number o f v e r t i c e s i n S a d j a c e n t  Now  <r e H s u c h  v  l e t H be a g r o u p o f a u t o m o r p h i s m s o f a 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  graph  G.  as f o l l o w s :  Dsf inition_3.i_1. Let t a k e v- e «{H) with m i,  v  j = 1,  P, , P , 2  ... , P  k  be t h e o r b i t s o f H. F o r e a c h P-  t  P; t o be i t s r e p r e s e n t a t i v e . = C  3,  = number 2, .  The m a t r i x  of  vertices  in  P-  adjacent  k, i s c a l l e d t h e o r b i t - m a t r i x  to  of H  v^, (with  58 respect  to  {v, , v ,  ...»  2  called  the  G)*.  The  weighted  v )  and  arc  k  orbit-digraph  Obviously  the  digraph  weights  of  with  (v , v)  vertex = m..  L  orbit-matrix  and  orbit-digraph independent  choice  make t h i s  clear  by  representatives.  the  following  ,  is  of  any  H.  group of automorphisms of a graph are of  set  We  will  of  the  definition  example.  Examp.le_3._2 Let {1},  G =  and  , the  H =  <(25),  a u t o m o r p h i s m s o f G. f3,  4} . L e t  M(H)  and Figure  =  the  1,  c l a w on (31) >.  The  2 and  '0  2  2  1  0  0  .1  0  OJ  corresponding  vertices  Obviously  orbits  3 be  five  the  H  of H are  with is  {1},  representatives.  orbit-digraph  is  centre  a group {2,  of  5}  and  shown  in  Then  3.3.  * The p h r a s e i n p a r e n t h e s e s c l e a r from the c o n t e x t .  will  be  omitted  whenever t h e  terra i s  59  F i g u r e , 3. 3 K  t  and  4  Now H  2  Associated  i f H,  a subgroup  H,  with  orbits  with  A  i s a group o f H, , a n d  sizes  b, , b  , A , . . . ,  u  sizes  a  , a,  u  '  a ai  a  ki  Orbit-digraph  '  a  a  ,  2  l  2  a  of automorphisms B, , B , z  , ... A  b »  r  k  ...,  B  k  a,  a p j 2  a  respectively.  k p  Ic The  A^  and  a ^ t  satisfy  the  of a  respectively,  ;  p  (34) > graph  are the orbits  ;  ,  k2*  o f < (25) ,  relations  then  H  z  G, of has  60  P•  P •  x  1  U  f t  ' x iL  a  i L  = b  i = 1, 2, . . . ,  t  T = I ^ i j . 1 be t h e k x k m a t r i x d e f i n e d  Let tj:  I  = &i and  = number o f v e r t i c e s i n B: a d j a c e n t vertex  to a  o f H,. ,  S be t h e m a t r i x p a r t i t i o n e d i n t o k  where t h e i j — t h  and  by  i n B^,  C l e a r l y T = M(H,), t h e o r b i t - m a t r i x Let  2  submatrices,  subraatrix  s<^i-> -= number o f v e r t i c e s i n A^, a d j a c e n t in  L  Z  Now  Lemma  vertex  i s the orbit—matrix  we h a v e t h e f o l l o w i n g  p- .  of H . 2  lemma.,  3.2 The  i.e.  to a  &u »  1 = 1, 2, ...» p ; m = 1 , 2 , . . . , S = H(H )  k.  c h a r a c t e r i s t i c polynomial of T divides  that  o f S,  d e t ( x l - T) J d e t ( x l - S ) .  Proof P  A . C B; and  Since i, and  j  L  =  k,  1, 2,  the A ^ ' s are mutually m  P  D  J  m= 1 Now  1  \J A= B; m=1 «" *  disjoint,  we have  .. s<^> let  i , j = 1, 2, . . . , k .  = t : L  (z, , z , z  z^) '  be  an e i g e n v e c t o r  of T  61 corresponding  t o t h e e i g e n v a l u e A. Then we  have  k H iL l j=1 *" t  z  =  Consider  p  f  o  r  a  1  1  1  =  1  *  the  *  2,  k.  expression  terms  p  terms  p.  terms  i-1  The  (  k Z -j=1  p  ( 2  j  *  s« <h')z  =  i  '  m=1  L  k _T t-- Z : 1=1  *  = Xz. .  "  X i s a l s o an e i g e n v a l u e  Hence follows  + l ) - t h t e r m , where 1 < 1 < p. , i s  p-  j=1  of  S,  from  which  it  that  det ( x i - T) | d e t < x l - S) . The n e x t theorem  Theorem  follows  3.2.  r e a d i l y from L e s s a  3.7  Let  H,,  H,  H|  z  g r a p h G w i t h H,  =  for  1,  all  i =  orbit—matrix  fe) , H^  o f H-  f ( T j ) If < T j _ , ) ,  tf  be g r o u p s o f a u t o m o r p h i s m s =  T(G)  and H^  2, ... , q - 1 . t h e n we  If  a subgroup o f T  = M(H ),  t  L  of a H  i + 1  the  have  f <Tj_ , ) | f ( T | _ ) t  f  f ( T ) If (T,) 2  = f (G).  CorpJ.lary._3_3 If  H i s a g r o u p o f automorphisms  o f a g r a p h G and i f  H has k o r b i t s , t h e n t h e r e e x i s t s a p o l y n o m i a l o f d e g r e e k that  d i v i d e s f (G) .  62 The c o n v e r s e as  of C o r o l l a r y  3.3  i s , however,  not  true  shown by t h e f o l l o w i n g example.  Example^^S Consider Figure  the  3,4.  The  x (x - 1) (x + 1) ( x of  the  2  - 3)  group  1 •  on  and  has  as  shown i n  polynomial  is  H =  {e,  is  subgroup  (15)(24)},  the  itself. 3 •  3.4:  three  vertices  the only n o n t r i v i a l  group  2 • Figure  five  characteristic  automorphism  automorphism  H  path  4 •  5 •  The.,,, p a t h .on . F i y e V e r t i c e s  orbits  {1, 5},  {2, 4}  and  {3}.  The  o r b i t - m a t r i x o f H w i t h 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 ,0  1. 2  0.  The x(x  z  characteristic  - 3) .  not e x i s t x + 1, (x -  Hence  by  polynomial  Lemma 3.2  2  -  3,  1) (x + 1} o r  polynomial  x(x - 1), (x • 1) ( x  2  which  x(x • 1), - 3)  this  o r Theorem  a group o f automorphisms x  of  as  the  3.7  matrix there  has  x,  (x -  1) ( x  does  x 2  1,  - 3),  characteristic  of i t sorbit—matrix.  The f o l l o w i n g t h e o r e m  is  i s g i v e n by Yap i n [ 4 2 ] .  63 Theorem.3.8 The A  characteristic  of  a  weighted  automorphism group characteristic  p o l y n o m i a l o f the a d j a c e n c y  digraph  b  =  V i  v  t  L  t  - a  .  k,  1  SYn  i f v .  r  two  factors  W?' ltlg-B fe t  polynomial  the  symmetric  polynomial  Let  G  P  r  the ft  that part  of  pf„A,  characteristic A  C(H) w h i c h  eguals  the •  i s analogus to  and H a n o n t r i v i a l s u b g r o u p o f t h e 2  and v  i n computing  the  p a r t o f A.  be a graph  H,  and  the  a u t o m o r p h i s m g r o u p o f G; a l s o l e t P, , P , of  characteristic  of the o r b i t — m a t r i x of  d e f i n e a matrix  t h e complementary  L  the_cpmfilgmentarY_gart  happens  now  ,of,.  ar  It  characteristic  P ,  • • • y n *• R •  respectively.. of  e  fc+  gharactgristic__olyno_ia^_pf  used  two m a t r i c e s .  o f T.  the  ESlY 6li§l-:2l-1r} ?,. p  k +  1| 2 |  called  We w i l l  the  d e f i n e d by:  i , j = 1, 2 ,  ^.  k + L  x^ 3 Yap  whose  i s the product o f  i s the representative of the i - t h o r b i t ,  c- - = a  orbits  vertices  c  k = number o f o r b i t s <2)  n  polynomials of the following  _£ a.. v «P  *  with  T i s non-trivial  B = [b-^ ], C = f C i j . ]  C)  D  matrix  t |  H (H).  , v  zi  ,  v  k (  ...» P  k  be  the  the representatives  64 Let  P, =  K,  , v,  v  }  1 r  2  'k where p  L  low p  c  and  JP^J. Let B =  we assume  {i | p  > 1} and  L  |B| = b.  ( r e l a b e l i n g i n d i c e s i f necessary)  that  > 1 for 1 < i < b p. = Also  the  =  1 f o r b < i < k. l e t 3 ( u , v) be t h e a d j a c e n c y  orbit-complement-matrix  of H with respect  and  to G will  function  o f G. Then  orbit—complement—digraph  be d e f i n e d  as  follows.  Definition_3.2 Let  C(H)  be  the  partitioned  s u b m a t r i c e s such t h a t  the i j - t h  where c < ^ >  , v.  = 5(v 1  —  i / £ + 1  1,  21  Y n + (  2  submatrix  ) -  ^(v., , V j ,  w + 1  )  p- - 1; and  j t B.  Then C(H) i s c a l l e d the weighted  b  t  r  and  with  • • •, p - ~ 1;  m = 1, 2, ... i,  matrix  the orbit—complement-matrix  digraph with vertex set  o f H,  65 b i=1 and  weights  given  by  orbit-cpmplement-digraph  Then  of  C(H)  is  called  the  H.  we h a v e t h e f o l l o w i n g  theorem  (cf. ,[42]).  lll§o£em_3_ _9 i  Let group  of  H be a n o n — t r i v i a l a  graph  orbit-digraph  G  with  and  respectively.  subgroup o f n  the  vertices  automorphism  and  D, , D  orbit—complement-digraph  of  2  the H  Then  f (G) = f (D, ) f (D ) . 2  Proof The  proof  is  essentially  t h e same a s t h e p r o o f o f  Theorem 2 i n [ 4 2 ] . Let v,  t  v ,  P, , P , 2  v  z  adjacency {v, , v , z  ... , P their  k  matrix v ; k  v  be  k  orbits  representatives. of  k + |  the  , v  G k + i  ,  with v„] , we  of  Then  H  and  i f a i s the  vertex have  set  66  x - a. -a  f(G)  =  -a x - a 11  2 l  -a  - a ,kz  -a  "  -a.  where a ^ If  a  ... x - a  k - M , i  = ij-th  • ••  -  =  a  k - n  f c k  x <  t  -a  -a i , k + i  -a  in  -a.  -a  kw  "  k + (  Q  R  S  i ,j =  —b i k -b » k  ai  P =  -b k i b^•  ^E.  -b a^p  K 1  ... x - b i# j  —  ™ cL  k+l, r<  x - a.  1, 2, ..., n.  j , j < k, a l l c o l u m n s  ... x - b  .  a  where  -b,  • » •  k+.,M.,  a  , t h e n we can w r i t e f (G) as  P  -a,  I, K + I  ~ *>,lc+t  e l e m e n t o f A,  we add t o column fe  -a  i k  -a  *  -a  such t h a t f(G)  -a  fc|t  1/ 2/ •. . # k.  1 > k * 1,  follows:  67  -a  . - ai n  ~ »,k+2  , k+i  a  Q =  -a k,fc+i H = f r r• =  ~  a  -a fcn  k,K+z  ] where r ^ i s t h e i - t h row o f B and  L  (0, 0, ...  0, x, 0, 0, ...» 0) f  r  t-th (Note t h a t t-th  (b  t |  , b  b  t t  the e n t r i e s  row i n P  position t k  )  i fv ^  i n r- a r e t h e same t  whenever v., . e  3 -  1# 2,  t  as t h o s e o f  the  . »•,  k,  P...) k+v, k+z  ~ k+2,k+i a  x  ~  a  k+*,k<-2  ... . ™ a • • -a k+2,w  S =  -a n,  -a Now  for  the  x - a,  k+2  i - t h row i n [ B  SJ, i f ^  indeterminate x i n the t - t h position, it  P .  because  k+  and  e  t h e t - t h row o f [ P Then  Q ].  then  contains the subtract  from  68  f (G)  P  Q  0  T  with T = xl„. u - W where W - [ w ^ ]  !1  Obviously f(G)  =  ™"  automorphism  • * • y  n "~* K • .  S e t P = f ( D ) and d e t W = f ( D ) and (  ( d e t P) x  Therefore,  2^  If  z  (det W) , which i f  group  we  2  o f a graph t h e n t h e c o m p u t a t i o n  polynomial w i l l  characteristic  polynomials  We  f(D,)f(D ).  know a n o n t r i v i a l s u b g r o u p  characteristic  digraphs.  i m p l i e s f (G) =  will  be r e d u c e d of  illustrate  two  this  of i t s  t o computing smaller  by  of the  the  the  weighted following  example.  Example  {e,  3.4  Consider  the  (12) (34)}  is  corresponding with  1,3  given  and  graph a  G shown i n P i g u r e 3.2. O b v i o u s l y  group  orbit-matrix  of and  automorphisms  '0  2  1*  2  1  1  .2  2  0,  the  orbit-complement—matrix  and 5 a s t h e r e p r e s e n t a t i v e s  by:  and  of the  orbits  are  69  0  0  .0  -1 J*  The and  characteristic  x(x +1} f (G)  respectively.  = x<x  + 1) ( x  = x(x • Note t h a t  2  - x  2  - 8x - 6  - x* - 8x - 6)  3  1) <x  3  Hence  2  - 2x - 6) .  t h e method used i n S e c t i o n  c a s e o f Theorem  3.3  polynomials are x  3.1 i s a s p e c i a l  3.9.  Gr______ith__a_els  We w i l l attached  now  t o them.  graphs with  Definition  where  the  i s a precise  with, l a b e l s i s an o r d e r e d  (V{G) , E(G) ,  V(G),-  number  E(G)  d e f i n i t i o n of  6  are  of d i s t i n c t  1Q(U)  triple  the usual  v e r t e x s e t and edge s e t  and 1^ i s t h e l a b e l i n g f u n c t i o n  #  v $ 7(G) , t h e n The  labels  1 )  t o a s e t o f l a b e l s , s a y ( 1 , 2,  If u,  The f o l l o w i n g  have  3.3  respectively, V{G)  g r a p h s whose v e r t i c e s  labels.  A graph G =  study  IQCV)  defined  on  p} where p > 2 i s  labels. f o r every p a i r o f d i s t i n c t  we c a l l G a l a b e l e d  vertices  graph.  n o t i o n o f a u t o m o r p h i s m s o f g r a p h s c a n be e x t e n d e d  70 to  graphs with  labels  as f o l l o w s .  Def i n i t i o n _ . 3 . 4 IF all  u,  i s an a u t o m o r p h i s m  v) fe E(G)  Q  Obviously The  the  the  usual as  of  corresponding  Definition Let  for  E(G)  automorphisms o f G a l s o form a polynomial  - A (G)). i n order the  vertices,  o f a graph G i s  to take  we  group.  will  into also  account label  the  3. 5 G =  ..»,  V{G)  fv,, v ,  p}  (V(G), EJG), and  vertex v^;  2  T  6  indeterminates.  £1, 2,  such  i f f (<7-{u) , <T{v))  characteristic  aet<xl  labels  =  i f  = 1<. (<r(u)) .  l {u)  defined  (V (G) , E (G) , 1^)  v fe V ( G ) t  (u, ana  of G =  vv- Vi  that l^(v,  +  ) =  + |  '  1Q(V ) 2  i )  with  &  label  set  set v^  7 k  =  +  |  ,  v ^  +  z  ,  i y- vi +  ...  +  =  4 2  '  1 ^(v^ ) = 1  Vy,}  1,  71  T  is  n  characteristic  e  the determinant  We n o t e  polynomial  o f G, d e n o t e d  of  that the c h a r a c t e r i s t i c  with l a b e l s i s a p o l y n o m i a l t h e number o f d i s t i n c t  polynomial  labels.  H  be  a  non—trivial  (V (G) , E (G) * . 1Q)  and  D, ,  D  v, , v_, , . . . ,  vertices  z  P, , P , a  v„  ...» v  are  k  ...» P  be  k  the the  o f H with  H  the  z  of  v,  t o graphs  with  group of automorphisms o f  orbit—complement-digraph  f  where p i s  3.10  Let  v,  graph  as f o l l o w s :  Theorem  G =  of a  i n p indeterminates  Theorem 3.9 can o b v i o u s l y be e x t e n d e d labels  by f ( G ) ,  orbit-digraph  respectively., of  representatives  G of  Also  such  and let that  the o r b i t s  72 <v ) = l L  Then f <G)  i =  t  1,  2,  . ... , n.  = f (D,) f ( D J ,  where f ( D , ) = t h e  determinant  of  x. - M (H)  0  f{Di)  and  = the determinant  *k+1  of  0 x, -a  k+2 -  C{H)  n Now  we  have t h e f o l l o w i n g  Corollary  3.3.  Corollary  3.4  If G = k^  H  is  a  group  (V(G) , E ( G ) , 1^) orbits  that  with  whose e l e m e n t s  p o l y n o m i a l of degree divides  A list  of  k  t  result  which i s a n a l o g u s  automorphisms  of  a  p t y p e s o f l a b e l s , and  to  graph i f H  has  have l a b e l i , t h e n t h e r e e x i s t s a i n xj. ( f o r  a l l  i =  1,  2,  . •.,  p)  f (G) .  o f graphs  four vertices  w i t h two  types of l a b e l s  i s g i v e n i n T a b l e IV o f the  and  Appendix.  at  most  73  IV.  EXTENSIONS AND  APPLICATIONS  Various considered the  and  i n t h i s chapter.  concepts  digraphs  4.1  extensions  of  In p a r t i c u l a r , we  adjacency  and n o n — s i m p l e  applications  m a t r i c e s and  will will  be  extend  automorphisms to  graphs.  Digraphs  As d e f i n e d i n S e c t i o n ordered of  pair  D =  that  (u,v)  with  each e.e  the  E(D)  important  following  Let  D be  V (D) = MD>  =  consisting  of order  a set of  v , t  lines  E (D)  ordered  pair  u, v € V(D) .  concepts  a digraph  n i s an  o f a nonempty s e t  i s i d e n t i f i e d w i t h an  definitions.  {v,,  a digraph  | V (D) | = n and  of d i s t i n c t v e r t i c e s Certain  in  (V ( D ) , E(D))  v e r t i c e s V(D)  such  1,1,  of a digraph w i l l  be  given  ;  with vertex v }. h  The  set matrix  [a. 1 L  where 1 i f there i s a l i n e 0 is  c a l l e d the  The polynomial  i n E<D)  from  v  t  to  V;  otherwise. adjacency  characteristic p(D)  matrix  of  G.  polynomial  of D are given  by  f ( D ) , and f(A(D>)  the  and  minimal p(A<D)),  respectively.  Definition4,_ 2  f  i s  an  permutation  automorphism  of  a  digraph  on t h e v e r t e x s e t V(D) s u c h  D  i fy i sa  that  implies  The digraph  main d i f f e r e n c e  between t h e a d j a c e n c y  and t h a t o f a g r a p h  symmetric.  i s the fact that  matrix of a  the l a t t e r i s  I f , i n a d i g r a p h D,  (u, v) i E(D) i f f ( v , u) € E{D), then  h (D)  will  be i d e n t i c a l  t o k (G)  where G i s  the  graph  h a v i n g t h e same v e r t e x 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,  since the  nonnegative,  a l l the  matrices o f graphs assumption  adjacency  that  matrix  foregoing  hold equally the adjacency  of  results  a  digraph on  adjacency  well f o r digraphs matrix  i s  i s symmetric  i f the i s not  required. We w i l l extended  now e x p l i c i t l y  t o digraphs.  s t a t e some o f t h e  results  as  75 Th§oreni_4 Let digraph H  H,,  H , v..,  D with  H,  for a l l i =  t + 1  f  l ?  %  ) | f  Corollary If is  be g r o u p s  2  =  fe} ,  =  1, 2,  f{D)  g -  o f automorphisms o f a  and  1. I f T  a =  L  subgroup tt(EJ  then  f (T )|f(T )  ( T j _ , ) , f (T^_.) |-f ( T ^ _ ) , 2  of  4  (  =  f<D).  4.1  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 ,  T( )  then  n  trivial. By v i r t u e  analogous  to  of C o r o l l a r y Theorem  4.1  2.4.  we  We  expect  will  t o have a  need  the  result  following  concepts f o r a digraph.  Definition^U^  ( c f . {16,  p. 198])  A p a t h o f l e n g t h p from sequence v  0  of  = u, v, , v  2  ,  <v. _ , v ) fe E(D) k  (  said v.  u to w in a digraph  L  distinct v _, , v p  p  for a l l i =  t o be r e a c h a b l e f r o m  = w  are  mutually  that  A  from  u  to  i f every  two  strongly, connected  connected  subdigraph  D. We  have t h e f o l l o w i n g  analogue  a  p. A v e r t e x v i s  u i f t h e r e i s a path  component o f D i s a maximal s t r o n g l y of  such  1, 2,  reachable.  is  vertices  A d i g r a p h i s s a i d t o be s t r o n g l y . c o n n e c t e d  vertices  D  of Theorem  2.4.  76  Theorem If  4,2 D  is  a  digraph  with  p o l y n o m i a l , and c h a r a c t e r i s t i c has  k  strongly  identity  connected  digraphs  an  irreducible  polynomial  f = p ,  minimal then  D  components which a r e c o s p e c t r a l  with  characteristic  and  minimal  p o l y n o m i a l s p. The  following  illustrates  is  Corollary  an  example  of  4.1 and Theorem  a  digraph  which  4.2.  ___________ The digraphs  digraph  D shown i n F i g u r e 4.1  which a r e c o n v e r s e s  be  o b t a i n e d from  all  the lines.  i s the union  o f one a n o t h e r ,  t h e o t h e r by r e v e r s i n g  Obviously  digraphs  that  i . e . one  adjacency  are  m a t r i c e s a r e t r a n s p o s e s o f one  Figure  converse  ___________________  and  itsConverse  i___ol_n__ial  to  because  another.  4_1  _iik_lE__d_cj^le_C]^ract_ri_t  can  the d i r e c t i o n s of  e a c h o t h e r have 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 their  o f two  77 Now  f(D) =  and  p (D) = x* - 2x2  The  (x* -  two  identity  2x2  strongly  1)2  - x -  1.  - x -  connected  components  d i g r a p h s b e c a u s e b o t h o f them have  characteristic  polynomial,  and  this  of  p(D)  D  are  as  the  polynomial  is  irreducible. As i n t r o d u c e d simply  a  3.2,  a weighted  digraph with weights attached  adjacency  m a t r i x A (D) o f a w e i g h t e d  set  z  fv, , v , A(D)  v„3  i s given  a- ^ = <  is The  vertex  by  there i s a line  t  ^0  lines  to i t s lines.  digraph D with  /-the w e i g h t on t h e l i n e  The  digraph  = fa-^1  where  4.2  in Section  from  i f t h e r e i s no l i n e  edge s e t o f a w e i g h t e d  which  have n o n z e r o  from v-^ t o v- i f v  to  L  from v  v^, L  t o v^ .  d i g r a p h w i l l be t h e s e t o f  weights.  Non-simple.Graphs  If  we  allow  l o o p s and m u l t i p l e  graph, then t h e defined  graph  i n Section  will  edges  be  a  i n t h e edge s e t o f a non-simple  graph  as  1. 1.  Definitior^i^a The G =  adjacency function  (V (G) , E (G) , fa  )  i s defined  of as  a  non-simple  follows:  graph  78 for  u, v  e  ^(u,  V{G) v) = number o f edges  i n E(G)  joining  Then t h e a d j a c e n c y m a t r i x o f a n o n - s i m p l e be  defined  function. graph  Note  viewed  as  A l s o we a  w e i g h t on t h e l i n e  from  Graph. I s o m o r p h i s m  The  non—simple  hence  most o f t h e  in this we  how  a non—simple  graph  can  weighted d i g r a p h i n which  between  and  the  graph isomorphism  the  automorphism problem  will  be  section. assume  t h e automorphism  non-simple  Problem  problem  First,  show  a  u to v i s ^{u, v ) .  relationship  partitioning discussed  note that  symmetric  will  w i t h t h e above a d j a c e n c y  that the adjacency matrix of  well.  v.  graph  i n C h a p t e r I I and C h a p t e r I I I a p p l y t o  g r a p h s as  4. 3 The  1.6  i s a l s o n o n n e g a t i v e and s y m m e t r i c ;  results  be  as i n D e f i n i t i o n  u and  that  partitioning  we  h a v e an a l g o r i t h m  of a  t o use t h e a l g o r i t h m  graph;  to solve  then  graph  to we  find will  isomorphism  problems. L e t G,  and G  2  components o f G, whenever G,  must  and G  t h e c a s e when G, Let orbit  G,  o f T(G} Now  U G  be two  2  correspond  chosen  to  graphs. Since  components  are isomorphic, i t s u f f i c e s  and 2  arbitrarily  G  2  = G.  we  G  2  to consider  are both connected. Then  G, =  c o n t a i n s elements  assume t h a t  of  h a v e an  G  2  i f and o n l y  o f V(G,)  and  algorithm  i f each  V (G ). 2  to  solve  the  79 graph  i s o m o r p h i s m p r o b l e m . F o r any two v e r t i c e s x , y o f a  graph  G, form  assigning  t h e graph  x  label  G  orbit  vertices  automorphism  partitioning  note t h a t  Algorithmic  4  t o screen  that  simple  graph.  done by s l i g h t  i n Section  be the  means  o f an  isomorphic.  isomorphic 3.2, w i l l  the orbit-digraphs  graphs a r e  an  partitioning  the  graph  Extensions  will  then  a l s o be a c t as  isomorphic.  algorithm  for  constructing  o f a graph.  G  being  t o deal  considered  with  other  i sa  We  will  finite  graphs can  modifications.  1: F i n d t h e c h a r a c t e r i s t i c factorised  Step__2: L e t f ( G ) ! I  obtain  by  are  will  f o l l o w i n g i s an o u t l i n e o f t h e a l g o r i t h m .  assume  Step  can  of a l l  o u t n o n - i s o m o r p h i c g r a p h s when t e s t i n g  now d e s c r i b e  automorphism The  set  orbits  graph  2.  G^.  the  other we  a  by  Considerations  He w i l l the  defined  Hence c o m p a r i n g  whether two g i v e n  •  of  =  x  be  when two g r a p h s  orbit-digraphs,  filter  Hence  labels  v e r t i c e s of G l a b e l  will The  of  f o r t e s t i n g whether two g r a p h s a r e  isomorphic. a  x x.  similarly.  Also  4  to  constructed  their  types  Then x ~ y i f f G  containing  similar  algorithm  two  1 and t h e o t h e r  G^ i s formed s i m i l a r l y . The  with  x  polynomial  f (G) i n  form.  have k- f a c t o r s o f d e g r e e i . Note t  that  be  80  n, where n i s t h e o r d e r o f  G.  i Find MP  =  the s e t  {I  i * *  Si  :  L  are i n t e g e r s ,  0 <  i i.e.  the s e t o f the degrees  nontrivial Let Step  P be t h e t r i v i a l  3: L e t p be so as the  Step  factorizations  <f: Check  the  pair  the  same c e l l  C,,  the  number o f v e r t i c e s  of d i s t i n c t  may  have C  h o l d s , go  by  merging  If  not, replace  Step Ste2_6:  in P  e q u a l t o p.  Call  2  that  u, v i n  are  to u  t o Step  cells  in C  2  adjacent to  6.  with p c e l l s  o b t a i n e d from  h a v e been c h e c k e d , P  f  o b t a i n e d from  v.  = C, .  2  Ste__5: I f a l l p a r t i t i o n i n g s  cells  {e}.  Merge c e l l s  vertices  in a cell C  - t h e number o f v e r t i c e s  (*)  H =  condition:  For every  If  n).  f  P».  {*)  H e r e we  t  o f f (G) .  number o f c e l l s  following  < k }\{0  of a l l p o s s i b l e  partitioning,  partitioning  adjacent  L  t h e maximum v a l u e i n HP.  t o make t h e  new  S  by a n o t h e r P by  go t o S t e p  partitioning  merging  cells.  Go  P 7.  with  p  to  4.  Search  f o r an  automorphism  will  h a v e P»  such  a <r, s e t H t o <H,  f o f G such t h a t  as the s e t of o r b i t s . I f t h e r e <r>,  s e t NP  <H, <r> exists  t o NP\(p}, s e t  81  P to P», and go t o Step 3. I f not, go t o Step 5. Step 7: I f p = minimum v a l u e 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, s e t NP t o NP\fp) , and go t o Step 3. , We  will  illustrate  the  algorithm by the f o l l o w i n g  example.  Example ft.2 Consider the graph G as shown i n Figure 3.2. The  algorithm,  when  applied  to  G,  will  run  as  follows:  Step_1:  f (G) = x(x • 1 ) { x 2 - 2x - 6). 2  Step_2:k,  = 3, k = 1, z  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 partitioning  obtained  from P by merging c e l l s and the number o f c e l l s i n P» i s 4. Step.4:  1 and 2 are adjacent t o 3, 4 and 5; 1 and 2 are not a d j a c e n t , hence the c o n d i t i o n (*) i s satisfied.  Step..6: The only p o s s i b l e candidate i s (12)  and t h i s i s  82  indeed  Ste__3:  an  automorphism;  H = <{12)  >,  NF  2,  =  {1,  P =  [ 1 , 2},  p =  3,  P'  =  3}, {3},  (1, 2,  3},  three c e l l s _te__4: In  {1,  2,  adjacent Step  5: V  1  -  {1,  {4},  {4},  4;  Step, 5;  In  p,  [5).  {5}  o b t a i n e d from  3},  t o 3 o n l y ; hence 2,  2,  4},  4},  [3},  {5}  obtained  t o 4 o n l y , hence  P  2,  =  {1,  P by m e r g i n g  5},  {3},  {4}  t o 1 and  (*)  is  from  P by  to  (*)  cells.  2 but 2 i s  partitioning merging  1 and is  with  violated.  i s another  4 i s adjacent  adjacent f  i s a partitioning  3 i s adjacent  with t h r e e c e l l s Step  hence  2 but  cells. 2 is  violated.  i s another  candidate  partitioning. S t e p 4:  {*)  i s violated  the c e l l SteE_5:  P'  =  {1,  ( 1 , 2},  2,  when c o m p a r i n g  vertices  2 and  5} .  (3, 4},  (5}  i s another  candidate  partitioning. ______:  Ste__6:  1 and  2 a r e both  adjacent  4 and  5.  3 and  4 a r e both  a d j a c e n t t o 1, 2 and  5.  Hence  (*)  (34)  i s satisfied.  i s an  automorphism t h a t s a t i s f i e s  requirements; H = <(12) , NP  =  {1,  t o 3,  he^ce  (34)>,  2},  the  5 in  83 P  =  ( 1 , 2} , {3, 4} , {5}.  S t e p 3: p = 2, P' =  {1, 2, 3, 4}, {5} i s a c a n d i d a t e  partitioning. Step  4: (*) i s v i o l a t e d cell  S t e p _ 5 : P» =  when c o m p a r i n g  vertices  2 and 4 i n  {1, 2, 3, 4}. ( 1 , 2, 5}, {3, 4} i s a n o t h e r  candidate  partitioning. Step_4:  (*) i s v i o l a t e d cell  S t e p _ 5 : P' =  when c o m p a r i n g  vertices  2 and 5 i n  (1, 2 , 5 } . ( 1 , 2}, {3, 4, 5} i s a n o t h e r  candidate  partitioning. Step_4:  1 and 2 a r e both 3,  4 and 5 a r e a l l a d j a c e n t t o 1 and 2.  Hence S t e p 6:  a d j a c e n t t o 3, 4 and 5.  (*) i s s a t i s f i e d .  (354) i s an a u t o m o r p h i s m t h a t requirements;  s a t i s f i e s the  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 t h e o n l y c a n d i d a t e  partitioning. Step_4;  (*) i s v i o l a t e d  when c o m p a r i n g  2 and 5 i n c e l l  {1, 2, 3, 4, 5}. S t e p _ 5 : The o n l y p a r t i t i o n i n g merging  cells  w i t h one c e l l  i n P has been  checked.  obtained  from  84  p = 1 = minimum value i n HP,  Ste__7:  P =  {1,  [3,  2),  4,  hence  5} i s t h e automorphism  p a r t i t i o n i n g o f G. We  will  now  consider  the  number  r e q u i r e d f o r the a l g o r i t h m . As noted i n characteristic 0(n  3 - 3 1  )  polynomial  operations.  of  a  The  of  operations  [20, p.56 0],  matrix  the  can be found i n  factorization  of  the  c h a r a c t e r i s t i c polynomial presents some problems. However, we note t h a t the f a c t o r i z a t i o n of a polynomial over where  p  is  0 ( n ( l o g p) 3  2  a  prime,  • n (log p) 2  factorizations  3  will  can  )  done  operations.  then  in These  give some idea of the p o s s i b l e  f a c t o r i z a t i o n of the polynomial over process  be  GF(p),  the  integers.  This  does not y i e l d a polynomial bounded a l g o r i t h m f o r  complete f a c t o r i z a t i o n o f a polynomial over the However,  since  we  integers.  are o n l y i n t e r e s t e d i n the degrees  p o s s i b l e f a c t o r i z a t i o n s , we  may  of  stop t h i s process when the  number of primes c o n s i d e r e d i s too l a r g e . The most time consuming Step 6.  The  number  of  operations  partitionings  are that  Step 4 have  and to be  c o n s i d e r e d i n Step 4 depends on the f a c t o r i z a t i o n s o f  the  characteristic  the  polynomial  automorphism  group.  automorphism  group  The of  and worst  a  graph  the case G  structure occurs  of  when  does not c o n t a i n 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 G  is  completely  reducible  the  i n t o l i n e a r f a c t o r s . In  of this  85 c a s e we refine  may  have t o  t h e automorphism  generator  of  assignment  the  which  partitioning. required A  list  4.5  partitioning  an  g r o u p . The s e a r c h by  first  number  for a f o r an  making  i n the previous  reduce the  that  and t h e n s e a r c h  done  i s impossible  of  a l l partitionings  automorphism  This w i l l  to find  connected  over  i n S t e p 6 c a n be  automorphism  in  check  an  admissible  of  operations  automorphism.  t h e automorphism  p a r t i t i o n i n g s of  simple  g r a p h s w i t h n o t more t h a n s i x v e r t i c e s i s  given  Table V of the  Appendix.  Conclusion  He  have  established  automorphism  group  polynomial.  We  of  have  some  a  connections  graph  seen  how  and  its  the  reducibility  minimal p o l y n o m i a l of a graph r e f l e c t s t h e g r a p h and i t s automorphism the  relationship  between  subgroup o f t h e automorphism factorization  of  the  g r o u p . We  the  between  group  of  i t s characteristic  characteristic of the  properties  have a l s o  number  the  of a  studied  orbits graph  of  and  of  a the  polynomial. Although  t h e r e s u l t s h a v e been p r o v e d f o r s i m p l e g r a p h s , e x t e n s i o n s to  o t h e r graphs a r e immediate. He have a l s o  automorphism  partitioning  characteristic computation  considered  of  to c o n s t r u c t the  o f a g r a p h by making  polynomial. the  an a l g o r i t h m  The  algorithm  characteristic  use o f  the  reguires  the  polynomial  and  its  86  factorization;  hence t h e e f f i c i e n c y o f t h e a l g o r i t h m  will  a l s o depend on these computations. Also s i n c e the f a c t o r i z a t i o n polynomial the  is  related  of  the  characteristic  t o the o r b i t s of the subgroups of  automorphism group, we would  expect  results  on  the  automorphism group of a graph to a s s i s t i n the e x p l o r a t i o n of vice  the  properties  versa.  of the c h a r a c t e r i s t i c  polynomial, and  87 BIBLIOGRAPHY  1.  N. B i g g s ,  Algebraic GraphTheory.  Mathematics  6 7 , Cambridge  2. J . A. Bondy  and  Applications,  Cambridge  University  P r e s s , London,  U. S. R. M u r t y ,  Macmillan  Press,  Tracts  1974.  Graph_Theory  London  and  in  with  Basingstoke,  1976. 3. C. Y. Chao,  A  note  Combinatorial 4. C. Y. Chao,  on  the  eigenvalues  of  a  g r a p h , J..  T h e o r y S e r . B 10 (1971) . 301 - 302.  On  groups  and  graphs,  T r a n s . Amer. Math.  Soc^. V18(1965) , 488 - 497. 5.  L. C o l l a t z Abh.  and  U.,Sinogowitz,  Graphen,  Math. Sem. U n i v . Hamburg 21(1957), 63 - 77.  6. G. C r i s c u o l o , C M . Connections  Department Columbia,  Group  of  the of  Computer  Minimal  a  Graph,  Science,  Polynomial Technical  and  the  Report  77-18,  of  British  University  V a n c o u v e r , 1977.  D. M. C v e t k o v i c , Publ.  Kwok, A. Mowshowitz and R. T o ^ t o r a , Some  between  Automorphism  7.  Spektren e n d l i c h e r  Graphs  Elektrotehn.  and  their  spectra,  Univ.,TBeograd  Fak. S e r . Mat. F i z . 354_-_356 ( 1 9 7 1 ) ,  1-50. 8. G. Debreu  and I . N. H e r s t e i n ,  Iconometrica 9. N. Deo,  21(1953),  Graph  Theory  Computer_Science, 1974.  Nonnegative  sguare  matrices,  597 - 607. witij^ABBlisatloPs.to^Ejtgln^erigg.ana-  Prentice-Hall,  Engiewood  Cliffs,  N. J . ,  88 10.  R.  Frucht,  Graphs  of  degree  g r o u p , Canad______ath_ 11.  R.  Frucht,  12.  R.  Gruppe,  F.  70(1971),  R.  Gantmacher, New  F. H a r a r y ,  211  The  F. H a r a r y , Four in:  Recent  Czechoslovak 1975, 16.  249  -  F. H a r a r y ,  -  abstract  378.  Graphen  nit  E. W a t k i n s ,  graphs,  vorgegebener  The  -  250.  groups of the  P r o c . Cambridge  Philps.  218. of.Matrices,  Vol. 1  and  2,  1959.  determinant  g r a p h , SIA___ev_ 15.  -  M.  The T h e o r y  York,  with a g i v e n  C^)_p_.sito_Math_ 6 (1938) , 239  Petersen  Soc_  Chelsea, 14.  von  F r u c h t , J . E. G r a y e r and generalized  13.  1 ( 1 9 4 9 ) , 365  Herstelung  abstrakter  three  of  4 ( 1 9 6 2 ) , 202 -  the  adjacency matrix of a  210.,  d i f f i c u l t u n s o l v e d problems  i n graph t h e o r y ,  Advances  i n Graph  (Proc.  Sympos.,  Prague,  Theory 1974),  Second  Academia,  Prague,  Reading,  Mass.,  256.  Graph  Theory,  Addison-Wesley,  1969. 17.  F. H a r a r y , C. graphs 321  18.  -  K i n g , A. Mowshowitz and  and  digraphs.  Bull.  R.  C. ,Read,  Cospectral  London Math._ Soc^  3(1971),  328.  F. H a r a r y and composite  E. M.  Palmer,  On t h e a u t o m o r p h i s m  group  g r a p h , S t u d i a S c i . Math. Hungar. 3 ( 1 9 6 8 ) ,  of  a  439  -  441. 19.  F. H a r a r y and spectra?,  A.  D.  E. K n u t h ,  Which  graphs  i n : L e c t u r e ,,,No t e s in_M a t he ma t i c s  Combinatorics, 20.  J . Schwenk,  have  integral  4 0 6 l S£a_bs_and  45 - 51. The  A r t o f C: p m pu t e„ _ P r pgr a m m i n_,  V o l . 2,  89 Addison-Wesley, 21.  D.  KSnig,  Reading, Massachusetts,  1969.  Theorie,.der_endliche_n_und_un  Akademie  Verlag,  Leipzig,  1936  and  ,  C h e l s e a , New  York,  1950. 22.  7.  K r i s h n a r a o o r t h y and and  digraphs  K.  with  H.  Marcus  and H.  I neguaj.it i e s , 24.  A.  Mowshowitz, The graph,  in:  given  Mine,  Allyn  Parthasarathy,  and  Bacon,  Boston,  matrix  A. Mowshowitz, The Combinatorial  26.  A.  Mowshowitz,  -  J..  213. Matrix  1964.  and  the  group  of  D i r e c t i o n s i n the Theory o f Graphs  F. H a r a r y ) , A c a d e m i c P r e s s , New 25.  204  graphs  group,  A S u r v e y o f M a t r i x ^ T h e o r y and  adjacency  New  Cospectral  automorphism  S e r . B .19(1975),  CombinatorialTheory 23.  R.  characteristic  Theory Ser. B Graphs,  York,  a  (ed.  1973.  polynomial o f a graph,  VI (1 972) , 177  -  J..  193.  g r o u p s and m a t r i c e s , i n : P r o c e e d i n g s  of the Canadian Mathematical Congress  (June  1971) ,  509  -  522. 27.  A. Mowshowitz, has  a l l  Graph 109 28.  0.  -  distinct  g r o u p o f a g r a p h whose a d j a c e n c y m a t r i x eigenvalues,  in:  Proof_Technigues_in  Theory (ed. H a r a r y ) , Academic P r e s s , New  York,  Ore, T h e o r y p f . G r a p h s , Amer. Math. Soc. C o l l o g .  E. M.  Palmer,  1968),  Ann  Publ.  38,  1962. The  exponentiation  group  as t h e  g r o u p o f a g r a p h . P r o o f T e c h n i g u e s j n Graph Second  1969,  110.  Providence, 29.  The  Arbor  Graph  Academic P r e s s ,  New  automorphism  Theory  (Proc.  T h e o r y C o n f . , Ann  A r b o r , Mich.,  York,  131.  1969,  125 -  90  30. G. C. E. P r i n s , On t h e Automorphism Group o f a T r e e ,  Ph. D.  T h e s i s , U n i v e r s i t y o f Michigan, 1957. 31. J . Riordan,  An I n t r o d u c t i o n _p_Cpmbinatprial A n a l y s i s , John  R i l e y 5 Sons, 1958. 32. G. S a b i d u s s i , Graph  m u l t i p l i c a t i o n , Ma_k____  72(1960), 446 -  457. 33. G. S a b i d u s s i ,  Graphs  with  given  t h e o r e t i c a l p r o p e r t i e s , Can.ad _J, y  34. H. Sachs,  Dber  Debreccen  and  given  graph  Math. 9(1957), 515 -525.  selbstkomplementare  Graphen,  Ptibl,. Math.  9(1962) , 270 - 288.  35. A. J . Schwenk, Computing graph,  group  the c h a r a c t e r i s t i c  polynomial of a  i n : Lecture Notes i n Mathematics 406_ Graphs_and  Combinatorics,  153-172.  36. J . H. Smith, Some p r o p e r t i e s of the spectrum o f a graph, i n : Combinatorial S t r u c t u r e s and t h e i r _ A p p l i c a t i o n s (R. K. Guy, e t . a l . , eds.) , Gordon 1970,  and Breach,  New  York,  403 - 406.  37. L. S p i a l t e r ,  The  characteristic  atom  connectivity  p o l y n o m i a l , J__Chem__np^umej_t  261 - 274; J__A_er__C_____Spc_ 38. D. A. Suprunenko Academic  matrix  4(1964),  85(1963), 2012 - 2013.  and R. I. Tyshkevich, Commutatiye M a t r i c e s ,  P r e s s , New York, 1968.  39. E. H. Sussenguth, A graph t h e o r e t i c a l g o r i t h m chemical  and i t s  s t r u c t u r e s , J . Chem. Documentation  f o r matching 5(1965), 36 -  43. 40. P. M. Weichsel,  Mlhi.  A  note  on  10 (1971) , 234 - 243.  asymmetric  graphs,  Israel_J_>  91  41,  P. J .  Hilson,  On  the  adjacency  matrix  of  a  Conference  on  Combinatorial  Combinatorics  (Proc. o f the  Hath,,  at the H a t h . . I n s t i t u t e , Oxford, 1972,  held  by D. J . A. Welsh and D. H. Woodall), I n s t . Southend-on-Sea, 1972, 42.  graph, i n :  H. P. Yap,  The  295  -  characteristic  Math.  edited Appl.,  321. polynomial of the  matrix of a m u l t i - d i g r a p h , Ianta_Matlu  8(1975),  adjacency 41 -  46.  APPENDIX Table_I S p e c t r a o f S i m p l e C o n n e c t e d G r a p h s up__to  !--+-  Graph  T  T  Index 1  A A  n_=_6_Vgrtices  1. 4142*  J  1  Other -1 0  values o f the spectrum J T "  | +-  I  -1.4142  -1  -1  1.6180  0.6180 -0.6180 -1.6180  1.7321  -1.7321  -2  2. 1701  0.3111  2.5616  -1  15 I  1.7321  -1  -1.4812  -1  -1.5616  -1  -1  -1  -1.7321  L  * N o n — i n t e g r a l v a l u e s a r e rounded  to 4 decimal  places.  i—r-  J Index  Graph — T  |  Other v a l u e s of the spectrum  1  1. 84 78  r  T  0.7654  0  T  ^7  -2  2. 1358  0.6180  0.6180 -1.6180 -1.6180  0.6622  -0.6622 -2.1358  2. 21 43  -0.5392  2. 30 28  0.6180  2. 3429  0. 4707  -1  2.4812  -1  -1.8136  -2.4495  0.6889  2.5616  x.  -1.6751  -1.3028 -1.6180  2.44 95  i  ^  -0.7654 -1.8478  -A-  -1.1701  -1  2.6412  0.7237 -0.5892  2.6855  0. 3349  j  -2  -1  -1.5616  -1  -1.7757  -1.2713 -1.7491  I—T  n|  1~  T  Graph  | Index  Other  1  values  o f t h e spectrum  2 • 8558  0.3216  2. 9354  0.6180 -0.4626 -1.4728  -1  -1  3.0861  0.4280  -1  3.2361  3.3234  -1  -1.2361  0.3579  I  -2.1774  -1.6180  -2  -1.5141  -2  -1  -1  -1.6813  -1  -1  -1.6458  -1  -1  + 3. 6458  -1  c J A  \  1.8019  1.2470  1.9021  1.1756  1.9319  0.4450 -0.4450  -1  -1.2470 -1.8019  •1. 1756 -1.9021  0.5176 -0.5176  -1  -1 I  L  -1.9319  -2  95  S  I  |n|  1  T  Graph  | Index T  \  1  Other values  r  T  2.07 43  0.8350  of t h e s p e c t r u m  r  T  0  \  1  +  -0.8350 -2.0743  2.2361  -2.2361  4-  o  -1  2. 1149  <_>  -2  0.6180 -0.2541 -1.6180 -1.8608  2. 1753  1.1260  2.2283  1. 3604  -1.1260 -2.1753  0.1859  -1  2.2361  ci  -1  -1  -1.7746  -1  -2.2361  2.2470  0.8019  2.2784  1.3174  2.2882  0.8740  -0.8740 -2.2882  2.3342  1. 0996  0. 274 2 -0.5945 -1.3738 -1.7397  2. 3799  0.5550 -0.5550 -0.8019 -2.2470  -0.7046  0.2914 -0.7510  -1  -1  -1.8912  -1.9202  96  I—T  n|  Graph  H  A  1  "1  T  T  | Index  |  Other values 1  x.  1  0.6180  0.6180 -0.4142 -1.6180 -1.6180!  2.4458  0.7968  -1.3703 -1.87231  2.5141  0.5720  2.3914  0.7729  -1  0.6180  1.7321  -0.4142  2.4383  1.1386  0.6180  2.5035  1.2644  2. 5243  0.7923  2.5.3 95  1.0825  2.5576  0.6772  -2.0861  -1.6180 -2.16421  0.4142 -0.4142  2. 4142  2. 5616 i  1  2.4142  2. 4142  <  of t h e spectrum  1  -1  -1  -2.4142i  -1  -1.7321  •0.8202 -1.6180 -1.75661  -0.5767  -1  -2.1911  -0.7923 -2.5243!  0.2611  -0.5406  -1.2061 -2.1364!  -0.6772 -2.5576!  -1.5616  -2  j  97  I  In  T""  T  Graph  T  | Index -I  J  | T  O t h e r v a l u e s of t h e s p e c t r u m :  ,  r  r  J X  1  <3  2.5991  0.7661  0.4669 -0.3848  -1, 3053 -2.1420  i4  2. 62 87  1.2297  0.1397  -1.3198  2.6554  1.2108  2.7056  1.0561  Y A  -1  -1  -1  -0.5600 -1.3504  -1.6783  -1.8662  -1.8513  2.7093  0.1939  -1  -1  -1.9032  2.7093  0.1939  -1  -1  -1.9032  2.7321  0  -0.7321  -1  -2  2.7537  0.7727  0.3064 -0.6093 -1.3293 -1.8942  2.7913  0.6180  -1.6180 -1.7913  2.8136  0.5293  -1.34 29  -2  —I 2.73 21  0. 7321  2.7321  1. 4142  -0.7321 -2.7321  -0.7321  -1.4142  -2  98 1  ) rt f  Graph  1  T  Index '  |  Other values of t h e spectrum 1  T  1  \  1  "I  +  2.7411 I 0.71031 0.6180) -0.2314 -1.6180 -2.22001  2.79 13 1  1  I 0.61801  2.7964  | 0.8532j  0  2.8136  I  1  I 0.52931  2.8284  I  0  |  I  0  j  2.84 22 | 1. 5069|-0.5069  4S>  2.8529  -1.6180 -1.7913}  0  1-1. 1955 -2.4541J  -1  -1.3429  0  -1  -2  |  0  -2.8284J  -1  -1.8422J  1 1. 0554| 0. 1830| -0.6611 -1.2718 -2.1584}  2.8951 1  2.9032  -1  1  I  | 0. 8061|  0  1 -0.6027 f  0  1  0  2. 9327 I 0.72721 0. 3088| -0.6 570  2. 9439 J 0.6648|  0  !  2.9474  0  !  | 1.15931  0  -1  -1  -1.7093  -1  -2.2924}  -2  |  -2.31171  -1.3684 -2.24031  -1.2859 -1.8208J  99  I—T  § xi | J  T  Graph  T  | Index  L  *  |  Other values  ,  of t h e spectrum  —1  ,  0  I  1-  1  "J  -0.7062 -1.5371 -1.7796  2.9809  1. 0420  3.0113  0.8481  0. 1967 -0.7248 -1.4780 -1.8563  3.04 37  0.6 180  0.3285 -0.5482 -1.6180 -1.8241  3.0478  0.8214  3.0965  1.1169 -0.5089  3. 1020  0.3443  3. 1642  0.6180  3, 1774  0.6784  -0.7562  -1  -1  -2.1129  -1  -1.7045  -1.3228 -2.1235  0.2271  -1  -1  -1.3914 -1.6180  -1  -1.8558  -3  -2  3.0868  1. 1558  3.0922  0.7020  0.1096  -1  -2  -1.1736 -2.1787  -1.2855  •2.5086  100  i — r  n| —H  Graph  1  •»  | Index 1  | 1  13.1149  |  0.7459] 0.61801 - 0 . 8 6 0 8  |3.1413  |  0.4849!  | 3. 16 92 I  0.7282I  0.2798! - 0 . 4 6 6 3  -1.50581 - 2 . 2052J  | 3.1819 |  1.24701- 0 . 4 4 5 0 - 0 . 5 9 3 6  - 1 . 5 8 84] - 1 . 80191  | 3.18 88 J  0.83471  I 3.2227 1  ! 3.2 361 |  | 3.2361 1  1  L-  1  Other values 1  1  I  of the spectrum  1  o  0  i  1  0  \ -0.6272  0.1124'  -1  0.6180] 0.6180! - 1 . 2 3 6 1  1  I  0  -1  -1  1  -1.61801  -1  -1  -2  f-  1  I - 2 . 6262!  ! - 2 . 3962|  - 1 . 5 2 6 6 ! - 1 . 80851  -1 .6180! - 1 . 6180J  - 1 . 2 3 61  I 3.2618 I  1.3399|  | 3. 2814 |  0.77191  0  -0.5125 -1.5408  I 3.2948 J  0.73471  0  -0.5975  | 3.3234 10.3579 ]  0  0  -1  \  -1  2  1  - 1 . 6017J  2  1  - 1 . 2 9 2 7 - 2 . 1392)  -1.6813  2  1  101  n| _H|  Graph  T  1  | Index  f  1  »  Other values  r  1  3. 3 539  1  —r  -0.4765  of t h e s p e c t r u m 1  -1  3.3723  3.38 39  0.7424  3.4037  0.4 897  0.2512  3. 3723  J J-  1  -1  -1.8774  -1  -2.3723  -1  -1.3279 -1.7985  -1  -1.2827 -1.8619  -1  -1  -2.3723  3. 3885  0.8019  0.1873 -0.5550 -1.5758 -2.2470  3.39 23  0.3254  3.4495  0.6180  0.6180 -1.4495 -1.6180 -1.6180  3.4609  0.3493  -1.3387 -2.4715  3.4679  0.9128  3.4979  0.7299  3.5141  0.6694  -1  -0.7989 -1.5818  0.1505  -1  -2.7177  -2  -1.1876 -2.1907  -0.5284 -1.4782 -2.1769  102  1 — T  ri 1 —+  Graph  1  T  1 Index  |  1  1  Other values  T  13.53 44 j  »  1. 0827| -0.40711  1  T  J  -1  1-1. 5111|- 1 . 6 9 9 0  -1  1  -1  |-1.61801 -1.7515  1  -1  1  -1  I -2.1413  | 3. 69 03 j 0.75341 -0.5784!  -1  I  -1  I -1.8653  13.7105 | 0.44081  -1  1-1.3842! -1.7670  13.5616 |  1  |-0.5616J  | 3. 5926 \ 0.6180!  I3.6262 | 0.51511  |  0.1589|  0  -1  I  -2  0  |  0  ! -0.4 829 J-1.61801 -2.230 7  ^  13.7136 | 0.61801  13.7321 I 0.4142'  13.7664 J  0  0.2679!  -1  J  -1  |-2.4142  !  0  1  0  13.7785 | 0.7108!  0  I  -1  1-1.98931  13.8201 | 0.4594  0  1  -1  1  -1  I -2.2795  i  -1  I  -1  I -1.8284  I3.8284 | i ±  of t h e spectrum  1  -1  1-1.2828! -2.4836  -2  103  , —  1  1  Graph  | Index  j  Other values  of t h e s p e c t r u m —  3. 8590  0.7792 -0.3791  3.8951  0.3973  4.0514  0. 4 827  -1.4758 -1.7832  -1  -1  -1  -1.2924  -1  -2  -2  -1.5341  -2  4.0678  0. 3616  -1  -1.2446 -2.18481  4.1190  0. 6180 -0.4316  -1  -1.6180 -1.68741  4. 1623  4.2015  0. 5451  -1  4.3723  4.4279  -1  -1  -2.16231  -1  -1  -1.74661  -1  0.3757  4.7016  -1 I L.  +  -1.3723  -2  -1  -1  -1  -1.8035!  -1  -1  -1  -1.70161  -1  -1  -1  -1  104 Table_ll 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 -Simple,••Connected up t o n = 6 _ V e r t i c e s I—T"  |n  Graph  |  Characteristic  Polynomial  h X  =  A A  2  (X  -  1  -  1)  x3 = x(x  =  2x -  2  2)  - 3x -  x3  1)  •  (X  {x - 2)  2 1)  +  (X  2  x* - 3 x 2 + 1 (X  - x -  2  x* x (x 2  X  4  = x  2  2  (X  -  3)  X  - 4x  2  + 2)  - 2x  + 1  (x • 1) <x3  - x  x* - 5 x  4x  x*  1)  2  (x - 2) <x  = x{x  • x -  2  4 2  -  x* =  3x  1)  2  -  + 1) ( x - 6x  2  2  - 3x  + 1)  - x - 4)  2  - 8x  - 3  (x - 3) (x + 1) 3  = X  5  -  = x(x X  S  -  = x{x*  U 3 X  1) U 3 X  + (X  3x +  1)  • 2x  - 4 x 2 + 2)  (X  2  3)  Graphs  1  105  I—T~  In|  Graph  Characteristic  1 X  =  x  - 5x3  (x -  X{X  x«  =  -  X  5x3  -  1)  •  6x  -  X3( 2 s  -  = x{x x  =  2)  2x2  + 4x  -  2x2  -  3) (X2  -  2x2 -  (X3  +  u  <x3  -  2x  -  2)  s  - 6x3  1)  42  -  1) 2  •  (X  -  42 - x3  X  -  6x  4x  -  = x (x +  - 6x 7 3 X  -  3  -  1) ( x 3  (X  +  2  -  z  2  4x  2)  +  2)  - x -  4)  + 4  2  X  x  2  •  5x2  2 •  +  x  2x •  +  n 2  -  2x  • 3x  X  1) (x*  s  +  x  • 5x  X  +  x  1)  -  4x  -  2  •  -  2)  2x  2x2  X  = x(x*  X  -  (X  -  3  3  - 6 3  s  •  6x +  4x  3x  + x  + 2  -  1) ( x 3  (X  =  1) 2  6)  s  x  2  -  X  X  + -  3  -  2x  1) (x +  2  X (X  xs  +  - 5x3  xs  =  5x  2)  + x -  (X*  - 5x2  -  X*  •  + 5x  - 5x3  s  x(x*  =  3  2) {x  (x - 2)  =  =  -  x3(x  xs  =  IX  -  s  Polynomial  2) 2x - 6x  +  2)  2)  106  Graph  |  Characteristic s  x  =  (x  =  =  1)  X  +  1)2{x  -  8 x  X  s  X  2  s  -  8 x  (x  •  1)2{x  X*  - 9x +  X (X  s  -  {x -  x  2  x*  -  6  - 5x*  x*  L_l_  -  +  2)  +  2)  2  5x  6x  - 2x  _  •  -  6) - 4  1) <x  1 1)  (x  3  + x  -  2  2x -  5x2 +  5)  + 5x2  - 5x*  x2 <x*  2x2 -  - 2x *  - 5x*  -  -j  + 1) (x* - 4x2 +  4x  +  - 5x2  1) <x -  3x2 +  +  1)  2  1) (x +  - 5x*  - x +  6x2  - 5x2  x2 (x -  4)  14x2  •  x2  (x*  -  3 - 20x2 - 15x  - 5x* 3  4x  (x + 1} •  4)  (x x  X  2)  2  2x  -  3  X  0  -  5x  2)  2x2 -  -  1) 2 ( 2 1  -  x2  {x +  +  10x2  -  3  2  8x2  -  3  1)  -  3  2) ( x 2  *  (X  -  3  8x2  -  3  (x  +  3x  \  -+  6x2  -  X  +  2  (x +  (x  x*  K  3)  7 3  (x  A  -  7 3  -  x*  A~\  •• x -  s  x  =  - ex  X  (x -  x  =  7 3  -  x2  x  =  2  s  x  =  -  Polynomial  3)  2)  (x +  2)  1)  107  I—T"  |n|  rH  •5^ Graph  o  |  Characteristic  I  -+  =  x*  -  x*  (x  x*  -  6x*  (x  -  1)2*x  x*  -  6x*  (x  -  1} ( x  x*  -  6x*  x  ( x «  -  6x  -  6x*  -  +  1) (x*  -  6x*  =  =  =  2  x* =  (x x  =  =  i =  =  -  *• 9x2 «+ 2  * 2  2x2 6x*  • -  2  -  *  -  6x  {x  2x  +  -  1) <x3  -  8x  4x  x  -  +  2}  1 4x  -  -  1  6)  2x3  •  -  2x3  -  3 a  1) ( x  2  -  +  2  X  +  6x  2x  2  -  •  -  x  +  1 1) ( x 3  +  -  5}  x3  +  7 2 X  -  *  5x  u  2  +  -  3x  •  4-  4)  -  2x3  •  7 2 X  +  2x  -  1  x*  -  6x*  -  2x3  •  g 2  +  2x  -  1  (x  -  1)  x*  -  6x»  -  2x3  2x  -  1) < x  2  -  -  4)  2  6x*  (x  x  x  -  •  1)  2  x*  {x  1)  2  •  4x 2  2)  -  2x3  1) ( x * 6x*  x (x*  -  -  8x2  5x2  •  4  2  5x  1) ( x  -  1) <x  6x  •  6x*  -  x(x  5)  2  -  6  -  2  -  6  x« =  5x*  (x  2  (X3  X  =  6  x x  <  Polynomial  T  X  1) ( x «  +  2  6x •  5x -  2  x  -  -  2  2x  1 1)  2  +  1)  1)  108  In| \—\  Characteristic  Graph  I  Polynomial  -+  —  x* = x  - 6x* <x«  2  x*  - 6x  - 6x*  = x (x  +  2  x  x*  1) <x3  -  s  -  + 7x  X  (x • x*  =  <x  - 7x*  = x(x 6  = x  2  *  2  -  • x -  2  +  4x 2  - 7x*  +  2  x* = x  X  2  6  (x* - 7 x - 7x* (x -  7  X  +  3x 2  +  - 2x3  - 2x3  -  5x  +  11 2 X  +  4)  1) ( x  X  2  +  -  •  2  2  -  4  2x  2  4x • 4x  +  2  4) + 8x  2  + 2x  - 1  - x -  4)  2  3) +  8x  *  2  7 2 X  2  -  3  1)  2x  - x3 - 5 x  + 2x  2  -|2x +  - 2x  2  i r  1) (x + 2) ( x 4  3)  - 2x -  2  + 8x  •  x*  +  2  - x3 - 6 x  _ 2x3  = x  4x  3) ( x  - 2x3  _ 7 * X  -  *  -  s  x  - 5x  1) {x*  (x* - 7 x  a  z  1) ( x  2x3  1) <x*  - 7x*  3 x  - 1  2  X  2  7x»  2  4 3  1) (x  -  x*  x  -  7 4  x  5)  1) (x3 - x  (x - 1) (x + x  X  +  -  + 9x  - 7x*  5 2  - 2x ••  2  * x -  2  +  - 2x3  - 7x*  6  = x{x  =  - 2x3  1  4)  •  4)  -  1)  109  I  T"  |nj V—I  Graph  Characteristic x*  i d  7x* - 4x  -  |= (x + 1) (xs x*  = x(x • 1 ) ( x 2  4S>  x* i=  x(x x*  =  A  Y  - 2x  3  7x* - 4x  -  7x  -  s  x*  7x* - 4x  •  - X2 -  3  1) <X + 1 ) 2 ( X  x*  7x* - 4x  -  3  5 X + 1)  5 X + 1)  X2 -  + 6x2 + n  3  x  |= x{x - 1) (x + 1) (x + 2) <x  - 2x - 2)  2  x* - 7x* - 4x  3  * 6x2 * 2x - 1  7x* - 4x  3  + 5x  X  6  X  X  -  (X2  2  6  +  7 4  _  X  X  -  1) < X 2  4x  3  2  -  + Ix  X  -  3  x  6  X  + 2)  - 8x* +4x2  X2 ( X  x*  5)  2  x2 {x + 2) ( x - 2x2 - 3  |=  6)  + 7x2 + 4x - 1  3  (X -  + 6x  2  - 4x  2  7x - 1)  +  2  • 7x2 + 4x - 1  3  1) ( X + 1 ) 2 ( x  |=  • 2x  + 7x + 4)  2  (X -  3  + 7x2 • 4x  3  - 4x  3  7x* - 4x  -  + 8x  3  + 6x - 1  2  6x  - x* -  7x* - 4x  -  + 9x  3  Polynomial  2  - 2x - 2)  - 8x* - 4 x  3  (x2  2x - 2)  • 12x2 • 8x  = x ( x • 2) (x2 - 2) (x2 - 2x - 2) x* |= ( x i  L-  - 8x* - 2 x 2  3  • x - 1) (x*  + 10x2 - 2x - 1 - x  3  - 6x  2  +  3x + 1)  110  Graph  •T~  I  X  6  _ 8x*  (x x« x  2  (x*  1) <x  - 8x2  -  8)  X*  -  8X*  -  •  1)2 (x*  -  8x*  -  4x3  •  - 8x*  -  4x  •  x(x  1) (x  - 8x*  x2 (x  - 8x*  (x  •  x*  - 8x*  x« x(x«  + 4x  -  - 2x3  1)  - 8x*  3  •  1)  4x3  -  4  - 2x2  - 3x  - x*  -  -  +  6x  (X*  -  - 8x3  3  -  4x  7x2  +  4x  7x  -  4)  4x  +  4)  8x  -  + 2x  - 7x3  +  +  3  +  3x2  3x  6)  + 8x  6x2  - 1  2  + 92 x3  - 1  6x2  6x  4)  2  X  -  6x  •  X  4 +  6x  9x2  + 4x  •  X  +  (x3  •  *. 14 5 2  2x2  4x3  4x3  -  •  -  - 8x2  - 8x* *  -  + 11x2  6X3  (x3  1) (xs  x2 (x*  X(X  -  * 2)  x*  x*  5)  8x*  -  x*  - x -  2  7)  • 1) (x + 2) ( x 3  -  x«  + X  (X2  6  1) ( x  5  X  • 11 2  X*  -  f  7 2  2x  - 4x3  1} {x  +  • x -  2  +  -  x  43  4x  + 12x2  x«  (X  L-  - 4x3  - 2x3  - 8x*  (x -  I  Polynomial  1) (x +  - 8x*  x*  Characteristic  +  8x  +  7x2  +  +  2  8x  X  6x  +  6)  +  8)  -  1)  2)  111  I  i I  T  |n|  H  Graph  |  Characteristic  Polynomial  T-  X  6  -  x* =  (X x*  8 x *- 6 x 3 + 7 2  - 8 x * - 6 x 3 + 6 x 2 + 2x - 1 + X -  2  - 8x*  = X(X * x* =  6  = x  2  x* =  4^  =  X3 -  - 6x3 + 5 x  1) f X * -  1)2(x*  - 8x*  X  3  -  2  6x2 -  X  +  • 4)  X  X  3  3  - J O X •  - 2x3 - 5 2 • 4  - 6 x  1)  + 4x  7X2 +  + 6 2  X •  + 3)  X  + 3x2  (x* - 8 x 2 - 6 x + 3 ) - 8x*- 8x3 + 4x2 + 4x - 1  (X + x*  1) ( X » -  - 8 x * - 8x3  (X * x  • 4x - 1  X  1) ( x 2 + x - 1) ( X 3 -  2x2 _ 4  X  +  1)  - 8x*- 8x3 + 3x2 + 4x  X<X •  1)2{X3 -  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*  X  1 ) (x - 3 ) <X • 2 ) 2  (x -  9 4 - 6x3 • 11x2 + 8x - 1 X  (x  + 1 ) (x« - x* - 8 x 3 + 2 x  6  -  x2(x*  9 * X  q 3  * 9 x - 1)  *• 7 2  X  X  - 9x2 - 4x + 7)  x* - 9 x * - 6 x (x  2  • 2)  3  + 1 1 x • 4x - 4  <x* • x - 1) Cx  2  3  - 3x  2  - x • 2)  I n!  Graph  Characteristic x* - 9x* - 4 x x  2  (x + 1) ( x  - x  3  2  - 8x + 4)  2  3  • 8x  x  3  • 10x  - 9x* - 8 x  6  - x  3  x* -  x  2  (x -  x  -  2  6  - 9x* - 8 x  x(x X  6  2x - 4 ) ( x  - 10X  X  (x + 1 ) ( x 3  x  e  x  6  e  x  6  1)  *  2  - 9x* - 8 x - 9x  - g * x  3  - 8x  _ Qx  + 2) ( x  3  4x  - 2x  - 9x* - 1 0 x  (x - 1) (x +  +  3  2  1) {x 2  3  2x -  18x • 7 7)  2  + 2x +  2)  + 4)  2  - 5x  + 5x  3  -  + 4x  2  + 5x  2  2  + 4x  2  - 5x  3  • 5x  3  +  2  2  8x  - 3x +  2  * 6x  3  + 2) (x* - 2 x  x {x 2  3x  1)  • 6x - 4  2  * 9x  3  x  x{x* x  -  3  _ g * _ 8x  x{x  - 8x •  2  1) (x • 1) (x • .2) ( x  - 9 *  4)  + 8x - 1 8x  * 8x  3  2x *  2  • x -  2  - 2x - 1)  2  + 4x  2  + 9x  3  • x  3  - 8x  3  *• 9 x  3  + 12x • 3  2  2  1) (x * 1) (x* -  x* - 9x* - 8 x (x  + 6x  3  1) (x* - x  - 9x* - 8 x  6  + 2x - 1  2  - 6x - 3) ( x  9x* - 6 x  x (x +  a_  4x  x* - 9x* - 6 x  (x  i  •  3  Polynomial  2  - x  • 2}  + 10x «• 3 2  - 7x - 3)  4)  113  I  T"  |B| f~+-  Graph —  Characteristic _ g * ._ g 3  6  X  x  X3 (X  x  x{x  *  —  X  + 1) ( x  - 9x* -  6  x  Polynoaial  10x  + 1) (x* - 9x*  - x - 8)  2  -  -  + 4x  3  x3  10x  -  •  •  2  8x  6x — 2x •  2  6)  •  4x - 1  {x + 1) (xs - x* - 8x3  -  2x  x  z  •  8x  2  -  x -  + 9x  2  + 4x - 1  6  3  3x  2  5x  2  - 1)  +  -  6  10x*  -  - 1) (x  x(x x*  1) 2 { x  + -  8x3  - 2x2  -  5x  x* -  10x*  -  6x3  X2 (X  + 1) <X3  x*  10x*  {x x  6  x  2  3  -  - 2x -  2  e  x  -  10x*  -  -  • X  - J O X *  8x -  2  -  -  4x  8x  10x3  -  {x  * 1) ( x  x  -  6  X(X5  10x» -  +  10x* -  10x3 -  s  -  -  io *  {x  •  1) (xs  x  *  -  -  •  6x  X  -  8x  + 2x  2  6x2  +  H)  + 6x - 1 X  2  + 7  X  - 1)  * 4x  + 5X + U)  • 7 2 X  -  +  2  g 3  10X2  x*  2  2  + 5x2  3  12x3 -  8x  -  -  10x  10X3  6  x  5  + 8x -  + U)  + 2) (x* - 2x3  x«  1)  9X + 3)  + x - 1) +  3  x -  X  + 10x2 2  -  3 2  2  10x3  -  8)  + 1 ) ( X 3 + 2x2  5) ( x  (x* - 1 0 x  x(x  X  -  + 9x  3  10x*  (x  -  8x  + lax  9 x 3 - 3 x 2  + U •  10X  + 4)  114  Graph  Characteristic x*  - 10x* - 12x3 •  t  Polynomial + 12X + 4  5 2 X  ( x - 1) ( x + 2) ( x • 1) (x2 - 3x - 2) 2  x«  - 10x* - 12x3 +  (X  • 1) ( x  x  + x - 1) ( X 3  2  - 10x* - 1 2 x  6  -  3  2x2 - g  -  x  +  1  }  x2 • 4 x  + 1 ) ( x 3 - 2x2 - 7  x(x x*  4x2 + 6 x - 1  + n)  2  X  - 10x* - 14x3 + 8x • 3  (X • 1 ) 2 ( x * - 2 x 3 - 7 2 • 2 x + 3) X  x*  - 10x* - 1 4 x  x(x x  6  + 1) <x* -  = x(x 6  X  =  =  • x - 1) ( x  2  -  11 4 x  2  X  3  x  6  3  2  - 5 x + 4)  + 5x  2  + 4x  - x  - 9x - 4)  3  3  - 11  2  3x2 + 4 x - 1  • 2x - 1 ) ( x  2  - 11x* (X  + 4x  2  - 9x  - 12x3 •  (x • 1 ) . x x*  x3  - 11x* - 1 2 x  - x  3  12x3 - 12)  X  - 11x* - 14x3 • 4 x  2  * 8x  = x ( x + 1) {x * 2) ( x 3 - 3 x x =  X(X  X  =  6  I  A-  +  1)2(  X  3  -  2x2  - 11 4- 16 3 X  X  •  -  X  - 4 x • 4)  x  8x  3 2  2  •  4)  • I6x * 7  ( x - 1) ( X • 1)3{x2 - 2 x - 7 ) x»  =  - 1 1 x * - 1 4 x 3 + a.  6  - 4 x • 1)  2  - 11x* - 16x3 •  ( x + 1) (  X  S  X  2 *- 1 0 x *• 3  - x * - 10x3 -  6x2 • 7 x • 3)  r— T-  Graph  T"  C h a r a c t e r i s t i c Polynomial 6  X  _ ii »  - x ( x + 1) (x + 2) ( x x =  (x  +  1 ) 3 <  x*  -  12x* - 16x3  = X (X 3  X  X  X  x*  -  3  -  -  3x«  -  18x3 -  1} (X* 12x* -  X3 -  20x  X  2  - 4x + 2)  2 * 4x • 3  5x  +  3)  3x2  +  ax  11x2 -  a x • 8x + 3  -  3  7x + U)  2  (X •  1) <X2 + x -  1) (X3 - 2x2 - 8x -  x*  12x* -  - 9 2  -  20x  = X (X + 1)2 ( x 2  =  - 3x  x  4) (X + 2) 2  - 12 *  6  = X{X •  =  3  - 11x* - 20x3 _ g  6  n  - 16x3 - 2x2 +  x  2  3  -  X  2x - 9)  x*  -  12x* -  22x3 -  (x  +  1 ) 3 (  -  x  6  3  3x  2  -  6x  - 13x* - 24x3 _ i 2 x  = x <x 2  X  9 x 2 «• 6x + 4  + 1) (x + 2) ( x  2  •  4)  2  - 3x - 6)  x* - 13x* - 26x3 - 1 5 x • 2x + 3 2  = (x + 1 ) ( x 3 3  x*  3 x 2 - 7x * 3 )  - 14x* - 32x3 - 27x2 - 8x  = x ( x + 1 ) 3 ( 2 - 3x - 8) X  x« - 15x* - 40x3 - 4 5 x =  (x - 5) (x + 1) s  2  - 24x - 5  3)  116 Table I I I : Integral «  I  —T—  T~  1—  O r d e r | ffl |  T r e e s of Diameter  n  3 and O r d e r  < 50 0  Characteristic Polynomial  |  I —JJ  !  6  1  3  |  3  |  x*{x  I  1*  1  7  |  7  |  X  |  26  1  13  |  13  I  |  42  |  21  |  21  I  62  I  31  |  |  86  I  **3  |  114  I  J  146  \  -  *  1) ( x  -  2) ( x  •  2)  -  2 ) <x  •  2) (x  -  3 ) (x  +  3)  X22(X  -  3} ( x  +  3 ) <x  -  4}  (x  •  4)  !  X3 (X  "  4) (x  *  4) (x  -  5 ) (x  •  5)  31  |  X *(x  -  5} <x  •  5) ( x  -  6 ) (x  +  6)  |  43  |  X 8 2 (X  -  6) (x  +  6) (x  -  7 ) (x  •  7)  57  |  57  |  x*io (  I  73  |  73  f  X* *  150  |  51  |  99  j  X**  I  182  I  91  91  |  X  !  222  |  111  | 111  |  X  I  266  !  133 J  133  |  X ^2  I  314  |  157  | 157  J  |  341  I  148  |  193  |  X33 (X  |  366  |  183  | 183  |  X  |  422  I  211  |  211  I  482  |  241  | 241 i .  .j  I  10(  1) (x  X  8  s  X  -  7) (x  •  7 ) (x  -  8) (x  •  8)  2  (X  -  8) ( x  +  8 ) tx  - 9) (x  •  9)  6  (X  -  7 ) {x  •  7 ) (x  -  10)  (x  +  10)  (x -  9) {x  +  9 ) (x  -  10)  (x  •  10)  (X -  1 0 ) (x  +  10)  (x  -  1 1 ) (X  +  11)  -  1 1 ) {x  +  1 1 ) <x  -  12) (x  •  12)  ° (X -  12) (x  *  12)  (x  -  13)(x  •  13)  -  1 2 ) {x  +  1 2 ) (x  -  14)(x  +  14)  (X  -  1 3 ) (x  «• 1 3 )  (x  -  14)(x  +  14)  |  X**8<X  -  1 4 ) (x  +  14)  (x  -  15)(x  •  15)  |  X * * {X  -  15) (x  •  15)  (x  -  16)(x  +  16)  17B 2  *  8  2  (X  7  3  *  7  2  1  J  117 Iable_I_ Connected Graphs* with 2 t y p e s 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 P o l y n o m i a l s j f o r I—T~  n|  Graph  Characteristic  L_4_  x*  »y  +— - y - x  z  x{xy  x* y<  I  -+  xy - 1 x y  A,  Polynomial  - 2)  (x • 1) (xy - y -  2)  x y 3  - 2xy - x  2  • 1  x y  - xy - 2 x  2  + 1  x< 3  X'  x •-  x y 2  2  ~ Y  x y  2  - 3xy • 1  2  2  - xy - x  2  • 1  y-  * G r a p h s t h a t c a n be o b t a i n e d omitted.  by  interchanging  x  and  y  are  1—T"  |n |  Graph  \  x<  Characteristic (xy  X  -•x  y  •X  y  -*x  - x - 1) <xy  * x -  1)  + x + y) (xy - x -  y)  x(x y  - 2y -  2  X*  x  2  (xy -  Polynomial  x)  3)  •X •X  y ( 2 y _ y - 2x) X  xt  fx  x(x y  -  2  2x  -  2y)  *x X  (xy y y  xy(xy -  H)  *x X  (x • 1) ( x y 2  - xy  - 2y  - x • 1)  x  x3y - 2xy - 2 x  2  - 2x  + 1  Y  tx (x •  1) ( x y - xy  x y 2  -  (y +  1) ( x y  2  2  v2  - 3xy  2  - 3x  - 2xy  - y - x  2  + 1)  + 1  - 2x  + 1)  I  11  In i  Graph  Characteristic  \  Polynomial — +  (x • 1) (x*y - xy - 2y -  x(x*y  X  2y2  y{x  (x +  2x)  - 2y - 3x - 4)  -  y2 -  X  y  - y -  X  5  • 1) {xy - y - 4)  1 ) 2 ( x y - 2y - 3)  (x + 1) (y +  1) (xy - y - x - 3)  120 Table_V ftutomgrghism_Par^itioTtings_of Simple Connected Si?..tg., ,~ 6.. V e r t i c e s  Graphs  n  f  T  •i G  I2|  1«  i3 i i r  A ,A-  3*  JJ  *2  —  •  _  1  1  automorphism  1  Partitioning  \ (1,  2}  I P I » (2,  —  _  T  3}  —  1  Characteristic  |  \ 1  Polynomial of f o r F(G)  1 Orbit-digraph » I x-1  i I |  l  x2-2  |  I  x-2  )  |  \2  1*  ••2  4«  •3  j J fx Hi  >2  1  2  4« 1  1  •3  2,  I {1,  4} , [ 2 ,  l {1} , 12,  »3  1- 1  I {1,  | (1,  3}  3,  2, 3 ,  3}  f xz-x-1  1  4}  1 x*-3  1  1 x-2  1  1 X3-X2~3X+1  |  4}  14 I 2  I 0 ) , (2,  4< 1 1  N X ?A^ 1<  I  |  J  !5 | 5 L  X.  1<  [4}  >2 '3  I  3},  2  I P,  3} , [ 2 ,  4}  1  X2-X-4  1  i I 1 {1,  2,  3,  4}  1 x-3  |  1 X3-3X  1  4*  2 | [1, -1  2), 13,  5}, _  {4} !=x(x2-3) X _ _  _  | -J  121  »—T"  Characteristic  Automorphism  Polynomial of Partitioning Orbit-digraph {1, 5}, {2}, {3},  m  for  x*~ 4 x + 2 2  x -4 2  {1},{2, 3, 4, 5} = (x-2) (x+2) {1, 2, 3, 4, 5}  x-2  {1} , {2/ 43, {33 , {5}  x*-5x *2 2  x * - x - 4 x + 2x+2 3  {1} ,{2} ,{3, 4} ,(5}  2  = (x- 1) ( x - 4 x - 2 ) 3  x  3 -  2 _  x  3  X  {1, 2}, (3, 5}, {4} =x ( x - x - 3 ) 2  (1,  2} , (3, 4}, {5}  (1,  3, 4}, {2, 5}  f1}, {2, 5}, {3, 4}  x -x -4x«-2 3  2  x -6 2  x -2x -2x+2 3  2  x ~2x -3x+4 3  2  {1, 5}, {2}, {3, 4} = <x-1) ( x - x - 4 ) 2  (13,  (2,  4}, (3J , (5}  x*-x -5x +x+2 3  2  f(G)  122  Characteristic Automorphism Polynomial of Partitioning Orbit-digraph  f o r f(G> —  J  J & 3  :  1} , {2} , {3, 5} , [4}  x*-6x -4x+2  1, 2}, {3, 5}, {4}  x3-x«-6x+2  1/ 3}, {2}, {4, 5}  x  z  3- 2-5 -2 x  x  x - x-6 z  1; 3, 4}, ( 2 ,  5} = {x+2) (x-3)  1},{2, 3, 4} ,{5}  x3-2x -4x*2  1}, (2,  3, 4,  x -2x-4  1 ] , 12,  5 ) , {3, 4}  V  5}  3, 4}, {2, 5}  1, 2, 3, 4,  5}  1, 4}, {2, 3}, {5, 6}  1} , {2,  3}, {4} , {5}, {6}  z  z  3-2x -5x+2 z  X  x -2x-6 z  x-4  X  3- 2-2X+ 1 X  x s - 5x3+ 5x =x (x*-5x +5) z  «—i_  +  123  Characteristic  Automorphism  Polynomial of  n  Partitioning  f o r T(G)  Orbit-digraph 1}, {2, 5}, {3, 4}, {6}  x*-4x + 1 2  x -x-2 2  6/ 5*  *3  1, 2}, (3, 4, 5, 6} = <x+1) (x-2) 1}, (2, 3, 4}, {5} , {6}  x*-5x + 3 2  1« 1, 3, 4, 5, 6}, {2}  1  f  2, 3, 4, 5, 6}  x -5 2  x-2 x*-x -4x +3x+1 3  1, 4}, {2}, (3} ,{5,  2  6} = (x-1) ( x - 4 x - 1 ) 3  X -6x +6x s  3  1, 5 } {2}, {3} , {4} , (6} r  =x <x*-6x +6) 2  'U.  x -x*-5x +3x +5x-1 s  3  2  1, 6}, {2},{3},{U},{5} = {x+1) ( x * - 2 x - 3 x + 6 x - 1 ) 3  x - 5x 3  1, 4}, {2, 5} , [3, 6} =x(x -5) 2  1,  5*  1ft  43,  13 , 12)  (2, 3}, {5, 6}  , (3, 4} ,{5, 6}  x -2x -x+1 3  2  x*-x -5x *3x*4 3  2  2  I—T~  Cha r ac t e r i s t i c Automorphism Polynomial of  n  Partitioning f o r P(G)  Orbit-digraph  5^-^X4  }» (2, 3 } , { 4 , 6 } , { 5 }  x*-6x +4 2  } , ( 2 ) , {3} , { 4 } , { 5 } , { 6 } x * - 6 x * - 2 x + 7 x + 2x-1 3  5* s  «4  2  x5-x*-5x *3x *3x-1 3  2  }, {2}, { 3 } , { 4 } , f 5 , 6 } = ( x - 1 ) i x * - 5 x 2 - 2 x + 1)  •A  ,  2, 5}, {3, 4 , 6 }  x -2x-1 2  5 x -6x -2x +5x s  1  3  2  }, {2, 3}, { 4 } , { 5 } , { 6 } = x <x*-6x -2x+5) 2  }, {2, 3 , 4 } , { 5 , 6}  si 5^  £1  X  3- 2-5x4-3 X  ,  2}, {3, 6 ) , ( 4 , 5 }  x -x -5x*4  ,  3 , 4 , 6 } , {2, 5 }  x -2x-1  ,  2,  x ~2x-1  ,  5} , [2, 4 ) , { 3 } , [ 6 ]  x*-x -5x +2x>4  ,  5}, ( 2 , 3 } , { 4 } , { 6 }  x*-x -6x +4x+4  3 , 6 } , ( 4 , 5}  3  2  2  2  Jra  3  2  \  3  2  125  1— T~  1  1  Automorphism  Characteristic  Partitioning  Polynomial of f o r T{G)  Orbit-digraph H,  5M  H  <»3, {2,  3}, {5}, {6}  f l ) , {2} , {3}, W,  {13, {2,  {53, {63  3, 5 } {4}, {6} f  x*-7x +4 2  x*-7x*-2x +8x*+2x-1 3  x*-7x2 + 3 x*-2x -3x +4x 3  { I t  ^ 3 . C2}, {33 ,{5, 63  2  -x (x-1) ( x - x - 4 ) 2  {13, {23, {33, {43, {53, {63  x*-7x*-2x3 + 7x2-1  {1r  x -x*-6x +2x  63 , (23, {33,{4|, {53  s  3  5 3 , {23 , (33 , {4}, {6}  +7x- 1  x ~x*-6x +2x +6x s  {1,  2  3  2  =x (x + 1) ( x - 2 x 2 - 4 x + 6 ) 3  \  2  '  [13, {2} , {33, {4, 6}, {5}  {1,  3, 4, 6}, {2}, {5}  {1,  43, {2,  5 3 , {3, 63  xs-7x -4x2+7x+4 3  x -x -5x+1 3  2  x -x -5x+1 3  2  x+-x -6x +2x+4 3  in  {1,  5 3 , {2}, { 3 , 4 3 , {6}  2  = {x-1) (x*2) (x2-2x-2)  ^  ,  Characteristic  automorphism  P o l y n o m i a l of  In  Partitioning  1}, m,  {3}, m,  {5}, {6}  Orbit-digraph  f o r f(G)  x*-7x*-4x3*6x2+2x-1 x3-x -5x 2  1#  [2, 5 } , {3, 6}  1, 5 } , {2, 3}, f4},[6}  =x{x2-x-5) x*-7x2-4x+4 = (x+2) ( x 3 - 2 x 2 - 3 x + 2)  m i s  1, 2, 4, 5 } , {3, 6}  x -2x-2  1, 2, 4, 5 ) , (3, 6}  x -2x-2  1. 3}, {2}, {4, 6}, {5}  x*-x3-6x +3x+1  1, 2), [3, 6}, {4, 5}  2  2  2  X  3-2 2-4x+5 X  = (x-1) ( x 2 - x - 5 ) x -8x -2x2+7x s  1, 2], {3}, {4}, {5}, {6}  1}, {2, 6}, {3, 5 ) , {4}  3  =x tx*-8x2-2x+7) X  4-7 2-4x+4 X  = <x*2) (x3-2x2-3x + 2)  •£3  1, 2, 3, 5 } , {4, 6}  x2-8  1, 5), {2, 3}, {4}, {6}  x*-2x3-5x2 + 6x + 4  —  |  1  1  automorphism  Characteristic  Partitioning  Polynomial of  If;  ass  Orbit-digraph  cn,  m.  (33, m,  {5}, {6}  x6-8x*-4x +9x +4x-1 3  5}, {2}, [3} , {4, 6}  2  x*-x -7x +3x+4 3  ,  f o r fCG)  2  = {x-1) <x -7x-4) 3  ,  V\—T  2  m  2} , (3, 6} , {4, 5}  } , ( 2 } , { 3 } , { 4 } , r 5 , 6}  x -2x -4x+4 3  2  xs-x*-7x +3x *3x-1 3  X -8x -4x +6x 3  s  ,  5} , [2} , [3} , (4} , [6}  2  2  -x ( x 4 - 8 x - 4 x + 6 ) 2  ,  5}, (2, 3}, {4}, (6}  x*-x -7x *x+8 3  2  x*-8x*-6x +8x +6x 3  } . {2} , {3} , [4} , [5} , (6}  =x(xs-8x -6x +8x+6) 3  1 , C2} , [3} , [4} , f5) , [6}  ,  61, (2, 5}, {3}, {4}  ,  5 ) , {2, 6 } , {3}, {4}  },{2},{3},f4, 5, 6} t  X -  2  2  x * - 8 x * - 6 x « - 7 x + 4x-1 3  2  x*-x -6x -x+1 3  2  x*-x -7x +x+4 3  2  x*-2x -5x +4x+3 3  2  128  Characteristic automorphism Polynomial of Partitioning Orbit-aigraph  5 ^ 4  si  {1.  2, 5 ) , {3},  fl,  2}, {3, 6}, [4, 5}  x3-2x -4x+1  {1,  5, 6}, {2, 3} , {4}  X  [1.  2, 3, 4, 5, 6}  x-3  {1.  2, 3, 4, 5, 6}  x-3  CU  6}, {2}, {3},f4},(5}  x - x * - 8 x «-2x +9x-1  [H),  {6}  f o r f<G)  x*-8x -6x+3 2  z  3 - 2x -5x + 4 2  *4  s  3  2  x«-9x -4x +7x 3  (1} , (2} , {3} , {4, 6}, {5}  2  = x (x*-9x -4x+7) 2  x*-x -7x + 4 3  2  P I , [2, 4}, {3} , ( 5 , 6} = (x+2) ( x - 3 x - x + 2 ) 3  P,  L  L-  2}, {3, 6} , [4, 5}  2  x -x -8x+4 3  2  {1} , f2) , {3} , {4} , (5) , {6}  x -9x*-6x +8x *2x-1  {1,  x -x -6x-3  4} , [2, 5}, {3, 6}  6  3  3  2  2  129  Cha r a c t e r i s t i c Automorphism Polynomial of Partitioning Orbit-aigraph  f o r f(G)  1. 5 } {2, 4}, {3}, {6}  x * - x - 8 x + 2x + 4  1}, {2, 6}, {3, 5}, {4}  x*- 8 x - 8 x + 1  1, 3, 5}, {2,  x -2x-4  f  4/6}  3  2  2  2  x -3x -2x+4 3  1, 6},  [2,  2  5}, (3, 4} = (x-1) ( x - 2 x - 4 ) 2  1, 5, 6}, {2, 3} , {4}  x -3x -3x +7 3  2  x -9x -8x +6x+4 s  S3  3  2  1, 2}, {3}, {4} , {5}, {6} = (x+2) <x*-2x -5x +2x+2) 3  1}r  {2, 6}, ( 3 ) , {4}, {5}  1, 2, 5, 6} , {3} , {4}  2  x5-9x -8x +5x +4 3  2  x -2x -5x+2 3  2  x*-2x -6x +4x+3 3  2  1, 6}, {2, 5}, {3}, {4} = (x-1) ( x - x - 7 x - 3 ) 3  1,  2,  4, 5}, {3, 6}  2  x -x-8 2  xs-x*-8x3-2x *6x 2  1, 5}, {2}, {3}, {4}, {6} =x ( x * - x - 8 x - 2 x + 6 ) 3  2  130  I—T  Characteristic Automorphism Polynomial of Partitioning  EE  {1} , {2} , [3} , {4}, {5, 6}  xs-x*-8x3-2x2*5x-1  {1,  2, 4, 5} , [3, 6}  x -x-8  (1.  6}, [2, 5}, {3, 4}  x -2x -5x + 1  {1,  3, 5}, {2,  x -x -9x+3  {1,  2, 3, 5  2  1 5V  f  3  4 ) , {6}  3  6 ) , (4}  2  2  x - 2x-5 2  ( 1 / 3}, {2}, {4, 6}, {5}  x*-10x -8x+4  {V  3}, {2}, {4, 6 ] , {5}  x*-2x -6x +2x*4  {13 ,  {2}, {3} , {4, 6}, {5}  x - x » - 9 x - x + 7x-1  {1,  5}, f2}, {3}, {4}, [6}  xs-10x ~10x +5x+4  C l 3 r {2},  {1,  i x.  f o r T(G)  Orbit-digraph  2, 4  {3}, {4}, (5,  r  5 3 , {3, 6}  6}  2  3  2  s  3  3  2  2  xs-x*-9x -3x +10x+4 3  x -3x-2 2  2  Characteristic automorphism  Polynomial of  Partitioning  Orbit-aigraph 6 3 , {3, 5} ,{4}  G  x*-x -8x -5x+1 3  H3,{2,  for H )  2  = (x+ 1) (x3-2x -6x+1) 2  {1, 2}, {3, 6}, (4, 5}  f1}, {2,  5, 6}, {3}, {4}  [1,  5 ] , [2,  6},C3},{4}  [1,  4} , [2,  5),  {3,  {1, 2,  4, 5} ,{3,  [1,  5}  3,  ,12,  6}  6}  4} , [6}  X  3-2x2-7x+4  x*-2x -7x +2x+3 3  2  x*-x -9x -5x*4 3  2  x3-x -9x-4 2  x -4x* 1 2  X3-11X-12  x*-2x3-7x +4 2  (1,  2),  [1,  4, 5}, ( 2 ) , [3, 6}  {1, 2,  (1, i—i—  {3},  [4} , {5, 6}  4, 5} ,-{3, 6}  5}, {23, {3}, {4}, {6}  = (x+1) (x -3x -4x+4) 3  2  x3-2x -8x+4 2  x -2x-7 2  x -x*-10x3-6x +7x*3 s  2  ,  ,  ,  Automorphism  Characteristic  Partitioning  Polynomial of O r b i t - d i g r a p h f o r f( > x*-x -10x -6x+4 G  3  H,  5}, {2}, {3, 6}, {4}  2  = {x+2) <x -3x -4x+2) 3  {1,  2, 5, 6}, {3}, (4}  x -3x -5x +3  f1,  2, 3, 4, 5, 6}  x-4  f1}» {2, 6}, {3, 5} ,{4}  C2, 5} , {3, 6}  {1.  I  L  3  2  x*-x -11x -7x+4 3  2  x -2x -8x-3 3  2  {1,  3, 5} , [2,  [1,  3}, (2) , [4, 5, 6}  x -3x -6x+4  Pr  2,  x -3x-6  4, 6}  4, 5}, (3, 6}  {1}, {2, 4, 6}, {3, 5}  6^  2  p,  5}, 12, 3,  {1,  2, 3, 4, 5, 6}  4, 6}  x -2x-9 2  3  2  2  x -3x -7x+3 3  2  x -3x-8 2  x-5  

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