UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the isomorphism problem for a class of bipartite graphs Dixon, Anthony H. 1970

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

Item Metadata

Download

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

Full Text

ON THE ISOMORPHISM PROBLEM FOR A CLASS OF B I P A R T I T E GRAPHS  by  ANTHONY H. DIXON B.Sc,  University  of B r i t i s h  Columbia,  1968  A THESIS SUBMITTED IN P A R T I A L FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n t h e Department of COMPUTER SCIENCE  We a c c e p t t h i s required  thesis  as c o n f o r m i n g  to the  standard  THE UNIVERSITY OF B R I T I S H COLUMBIA October,  1970  In  presenting  an  advanced  the  Library  I  further  for  degree shall  agree  scholarly  by  his  of  this  written  this  thesis  in  at  University  the  make  that  it  p u r p o s e s may  for  for  is  financial  of  Computer  The U n i v e r s i t y o f B r i t i s h V a n c o u v e r 8, C a n a d a  October  14,  1970  of  of  Columbia,  British  by  the  understood  gain  Science  Columbia  for  extensive  be g r a n t e d  It  fulfilment  available  permission.  Department  Date  freely  permission  representatives. thesis  partial  shall  Head o f  be  requirements  reference copying  that  not  the  agree  and  of my  I  this  or  allowed  without  that  study. thesis  Department  copying  for  or  publication my  ABSTRACT The purpose o f t h i s isomorphism  thesis  problem f o r a s p e c i a l  c h a r a c t e r i z e d by i t s  i is  to i n v e s t i g a t e  c l a s s of graphs.  edge s e t , and a subgroup o f i t s  c a l l e d the c o l o u r group.  In  the  graph  Each graph  automorphism  p a r t i c u l a r , a simple, e f f i c i e n t  is  some b a s i c d e f i n i t i o n s  a  and lemmas r e q u i r e d  The concepts o f r e d u c i b i l i t y and r e d u c i b l e b i p a r t i t e graphs  are i n t r o d u c e d , and the p r o p e r t i e s o f the c o l o u r groups are  one i s  developed.  Chapter 1 p r o v i d e s i n the t e x t .  group,  algorithm  f o r d e t e r m i n i n g whether two graphs a r e isomorphic i f at l e a s t member o f the c l a s s  is  o f such graphs  investigated. Chapter 2 e s t a b l i s h e s  r e d u c i b l e graphs.  Conditions  some r e s u l t s  concerning the e x i s t e n c e o f  based on the e x i s t e n c e o f v e r t i c e s  p r e s c r i b e d p r o p e r t i e s are shown t o . p r o v i d e s u f f i c i e n t c o n d i t i o n s graph t o be r e d u c i b l e .  In the s p e c i a l  be both necessary and s u f f i c i e n t . of graphs,  based on t h e i r r a d i u s  with for a  case o f t r e e s they are shown to  Necessary  conditions  and diameter are a l s o  f o r the r e d u c i b i l i t y established.  Chapter 3 d e s c r i b e s an a l g o r i t h m f o r determining whether a graph  is  c o m p l e t e l y r e d u c i b l e , which i s  An i n v e s t i g a t i o n is  o f the speed o f t h i s  a p p l i e d to a t e s t f o r  algorithm  compared with an a l g o r i t h m o f D. C o r n e i l  isomorphism.  i s made and i t s  [ 5 ] , which t h i s  the best f o r a r b i t r a r y graphs i n the c u r r e n t l i t e r a t u r e .  efficiency  author  considers  TABLE OF CONTENTS  i i pp.  CHAPTER 1 :  CHAPTER 2 :  CHAPTER 3 :  The B i p a r t i t e C o m p l e m e n t and C o l o u r g r o u p  1.1  Introduction  1.2  The B i p a r t i t e C o m p l e m e n t a n d G r a p h  1.3  The C o l o u r G r o u p o f a B i p a r t i t e G r a p h  Reducible Trees  and  of a  graph.  1 Reducibility  3 7  Graphs.  2.1  Reducible Trees  14  2.2  R e d u c i b l e Graphs  20  An I s o m o r p h i s m  Testing  Algorithm for B i p a r t i t e  Graphs.  3.1  C o m p l e t e l y R e d u c i b l e Graphs  29  3.2  Graph  31  3.3„  Timing Considerations  Reducibility Algorithm  37  SUMMARY  42  BIBLIOGRAPHY  43  L I S T OF TABLES  i i i  PP1.  The Number a n d E x p e c t e d V a l u e o f t h e U n o r d e r e d P a r t i t i o n s o f t h e Numbers  one t o t e n .  40  L I S T OF FIGURES  iv PP-  1.1  A C o m p l e t e l y R e d u c i b l e Graph  7  1.2  A Partially  7  1.3  A Graph  1.4  G r a p h s w i t h r " * ( G ) a n d T(G)  t h e Same  10  1.5  Graphs  subgroup o f f ( G )  10  2.1  I r r e d u c i b l e Trees w i t h Seven V e r t i c e s  16  2.2  G e n e r a l i z e d TYPE 1 R e d u c i b l e T r e e  16  2.3  G e n e r a l i z e d TYPE 2 R e d u c i b l e T r e e  16  2.4  A R e d u c i b l e Graph W i t h o u t a . R e d u c i b l e Spanning  2.5  Bipartite  R e d u c i b l e Graph  Isomorphic  w i t h r*(G)  to i t s  B i p a r t i t e Complement  a'proper  Complement o f a R e d u c i b l e G r a p h  Without a R e d u c i b l e Spanning  2.6  2.7  Two N o n - I s o m o r p h i c  Graphs  R e d u c i b l e Spanning  Trees  Tree  20  21  Tree  A R e d u c i b l e Graph With Both R e d u c i b l e  and I r r e d u c i b l e S p a n n i n g  7  22  Trees  With I d e n t i c a l  2.8  A R e d u c i b l e Graph With Radius  3, Diameter 5  2.9  An I r r e d u c i b l e G r a p h W i t h . R a d i u s  3, Diameter 3  23  27  27  ACKNOWLEDGMENT  I wish helpful I  to express  my t h a n k s  and p a t i e n t a s s i s t a n c e  a l s o wish  t o Dr. A. Mowshowitz f o r  during the preparation of t h i s  t o t h a n k t h e Department o f Computer S c i e n c e ,  B r i t i s h Columbia, f o r providing c o u r s e o f my  v  studies.  financial  assistance  his thesis.  University  throughout  the  of  CHAPTER 1 The B i p a r t i t e C o m p l e m e n t and C o l o u r G r o u p o f a G r a p h .  1.1  1  INTRODUCTION An u n d i r e c t e d g r a p h , G , i s together with a set edges.  If  (i,j)  adjacent.  automorphism themselves  e E, t h e n t h e v e r t i c e s  of a graph  It w i l l group  of the  V(GtUG )  and G  p r o d u c t , GiX G , 2  2  w eV(G ) 2  2  (vi.wi)  2  t  o f the  that this  set  adjacency.  of a l l  onto  automorphisms  V(G)  = j. ( v )  forms  An  graph. {c  for all  l  c ,...,  s  v e  a group c a l l e d the  is  T h e i r sum, G ^ G ^  and E ( G i U G )  = E(Gi )UE(G )..  2  2  the graph w i t h V(Gi'X G ) 2  ffvi.va).-  w )]  (Wi,  and e i t h e r v i = w i and  E (Gi)  f o r v.-  one-one  2  the set of a l l y e r ( G ) ,  t h a t J (»f(v))  2  2  the V(G). colour  i  The g r a p h  the graph  Their  2  with  cartesian and  2  where  2  is  = V(Gi)XV(G )  (v ,w )eE(G )  vi,wieV(Gi), or v =w 2  2  and  }.  D e n o t e by G t h e g r a p h w i t h V ( G ) E(G).  a  t o be  of the v e r t i c e s  a function f :  We c o n s i d e r  be two g r a p h s .  = {[v,w] =  2  are said  called  graph.  2  E(Gi X G )  and j  a d j a c e n c y , and t h e s e t  group o f G, such  = V(Gi)UV(G )  2  of vertices  a one-one mapping  o f a graph G i s  be shown l a t e r  L e t Gi  v ,  is  , the set of colours.  automorphism  pairs  i f there exists  a g r o u p - c a l l e d - t h e group  An n - c o l o u r i n g n  isomorphic  i  s e t V=V(G) o f p v e r t i c e s  between t h e i r v e r t i c e s w h i c h p r e s e r v e s  which preserves  constitutes  c }  E=E(G) o f q u n o r d e r e d  Two g r a p h s a r e  correspondence  a non-empty  = V(G)  and E ( G )  = {(v^v^)  i  v.}. isomorphism  problem i s  one o f f i n d i n g e f f i c i e n t  o f d e t e r m i n i n g when t w o g r a p h s a r e i s o m o r p h i c . u s u a l l y meant c o m p u t a b l e a f t e r p  units  By."efficient"  o f t i m e where p i s  the  ways is number  2 o f v e r t i c e s , and K i s resulted  a constant.  i n the generation  w h i c h h a v e been s o l v e d , inapplicability  of several  is  graphs.are of this  not  uniquely  idea is  invariant  characterized. by S a b i d u s s i  [22]  isomorphicgraphs  some s u i t a b l e  o f a graph  by w h i c h  results  of a negative  nature  3  :  G is  regular  of degree  Pi+ .:  G is  spanned  by a s u b g r a p h h o m e o m o r p h i c  been  K,  Kagno [ 1 7 ]  K,  result regular  has  fruitful [4,5]  i f and o n l y procedure  K*3. to a given  t o show t h a t t h e r e graphs w i t h given  graph.  exist chromatic  group i t s e l f  determined the groups of  a n a l y t i c a l approach  is  graphs  who has  t o t h e p r o b l e m has  determined a procedure  with the.property  for  t h a t two g r a p h s  are  i f t h e y h a v e t h e same " r e p r e s e n t a t i v e is  not yet-  proved  partitioning of  the given  been  constructing  graph".  t o be d e t e r m i n i s t i c ,  on a c o n j e c t u r e t h a t t h e r e p r e s e n t a t i v e g r a p h s  found.  of:  vertices.  a "representative graph"  h a v e y e t been  one  K>2.  the c a l c u l a t i o n o f the automorphism  the automorphism  obtained  K?l.  number o f G i s  than seven  based  K,  extended t h i s  although  Although.the  have  is  P  isomorphic  of  g r o u p and p r o p e r t y . P . w h e r e  chromatic  made by C o r n e i l  set  extension  with given  :  The m o s t  An  hence  non-  2  with less  and  t h a t t h e r e a r e i n f i n i t e l y many  P  difficult,  exist  i t c a n be c o m p l e t e l y  connectivity of G is  Even  their  group,  finite  :  number.  of  who showed  i n f i n i t e l y many n o n - i s o m o r p h i c  is  that there  Pi  Izbicki. [15]  it  Frucht [7]  c h a r a c t e r i z e d by t h e i r g r o u p .  Partial  some  suggested  graphs w i t h a given  that of finding  properties  has  has  problem.  the r e s u l t of  i n f i n i t e l y many n o n - i s o m o r p h i c  for solutions  r e l a t e d problems,  and whose s o l u t i o n  to the o r i g i n a l  Among t h e s e  The s e a r c h  graph,  no  since  exhibit  counter-examples  This is  thesis  defines  and i n v e s t i g a t e s  shown l a t e r t o h a v e p r o p e r t y t h a t i t s members  c h a r a c t e r i z e d by t h e i r c o l o u r g r o u p , of vertices. members  the  F i n a l l y , an a l g o r i t h m  o f the c l a s s ,  and p r o v i d e s  1.2  a class  determines  o f graphs  which  are uniquely  number o f e d g e s ,  a n d number  i s provided which  determines  w h e t h e r t w o members  s u f f i c i e n t information to construct  are isomorphic,  t h e c o l o u r group o f  graph.  THE B I P A R T I T E COMPLEMENT AND.GRAPH R E D U C I B I L I T Y A graph  i s b i p a r t i t e i f i t s v e r t i c e s c a n be p a r t i t i o n e d i n t o t w o  d i s j o i n t sets  Vi.uV  such t h a t every  2  Vi and t o one i n V .  Denote  i n V i , and n v e r t i c e s  in V .  2  2  edge  i s incident to a vertex i n  by G ( m , n ) a b i p a r t i t e g r a p h The b i p a r t i t e c o m p l e m e n t o f  d e n o t e d by G ( m , n ) i s a b i p a r t i t e g r a p h  w i t h V ( G ) = VxUV  {(v Wj), v^VijW^.eVz ( v ^ w . . ) f- E ( G ) j [6]. it  o f a graph  G with n vertices r  a.. U  =  i f  ( i , j ) i E(G)  1  i f  ( i , j ) e E(G)  Since G i s undirected  (i,j)eE(G) implies  Therefore A(G) i s symmetric. in V  and E(6) =  The a d j a c e n c y m a t r i x , A ( G ) ,  i s an nxn ( 0 , l ) - m a t r i x  0  2  G(m,n),  such  that:  \  .  the v e r t i c e s  with m vertices  x  Further  ( j , i ) e E ( G ) and hence  i f the graph  are labelled l,2,...m,  s  a..=a...  i s b i p a r t i t e , and  and t h o s e  in V  2  are labelled  m+1,m+2,...m+n, t h e n t h e a d j a c e n c y m a t r i x A ( G ) h a s t h e f o r m B"  '0 A(G) B  T  0  Hence t h e b i p a r t i t e g r a p h G ( m , n ) c a n b e c h a r a c t e r i z e d b y t h e s m a l l e r mxn v e r t e x m a t r i x B, c a l l e d t h e b i p a r t i t e m a t r i x o f t h e g r a p h .  4 Let  Gu and G  one m a p p i n g ^  1,2  be two g r a p h s ,  of V(Gi)  vertex sets, l,2,...n,  2  i f / i s  ^ can n.  and suppose t h e r e e x i s t s  onto V ( G ) .  Assuming  2  an i s o m o r p h i s m ,  be i n t e r p r e t e d as  As  a consequence  Gi  G  one-  have t h e  2  and t h e v e r t i c e s a r e a p e r m u t a t i o n P^, o f  o f a LEMMA by Chao  a  [3,  labelled  the  p.  same  elements  489],  we  observe: l.T  LEMMA : G{- i s  isomorphic  a p e r m u t a t i o n m a t r i x P such  to G  =  T  G is  images  of G x a n  2  be i n t e r p r e t e d a s  all  of a l l  possible  o f the b i p a r t i t e m a t r i x o f G.  LEMMA : I f  and B  Gi(m,n) matrices  is  and B  l  2  isomorphic  p^  ^  m m  PROOF :  permutations  These  isomorphic  of the  considerations  1  rows  lead  2  are t h e i r r e s p e c t i v e b i p a r t i t e m a t r i c e s , to G (m,n)  and P ^  n x n  2  Gi(m,n)  i f and o n l y  2  ^  such  isomorphic  if  that PlBiP =  B ,  2  to G (m,n) 2  there e x i s t 2  P =  X 3 B1X1  X X X X X  2  3  4  then  X1X3  0  xx  Bi  x  that  P  *0  T  2  X^X^. X3BiX  2  +  X1^ B1X  0  X BiX3  ,  X^BiX  2  +  X^BIXLJ  B£O  1)  X ^ X j  +.  ( X ^ X ^  2)  X£B];X  +  (X£BJX )  3)  X3B1X;? +  Xij.B3}X1 +  X B X  T n t l  ,  +  1  1  2  /T, 2  2  2  XiBiXi  t  T  =  0,  =  0,  =  B  2  then  permutation  or P ? B I P = 2  B . 2  i m p l i e s by LEMMA 1.1  Bi  Hence  possible  G ( m , n ) and G ( m , n ) a r e c o n n e c t e d b i p a r t i t e  e x i s t e n c e o f a p e r m u t a t i o n m a t r i x P such  Let  exists  following:  1.2 graphs  i f there  A(G ).  b i p a r t i t e , then the b i p a r t i t e m a t r i c e s  and columns to-the  and o n l y  that  P A(Gi)P If  if  2  B " 2  Bi" 0 -  P =  "0  zl  the B" 2  0  5 Now s i n c e X  X ,  l s  X ,  2  X  3  and Bi,  4  every row and column o f B  B  has a t l e a s t  one n o n - z e r o e n t r y ,  are 0 and X  and/or Xi+ are 0.  1 and 2 imply X  :  and/or X  3 implies X  2  not both 0 , Xj,, X  and X or X X  4  2  , X  3  X  l s  not both 0.  4  and X  a r e 0.  3  3  are n o n - n e g a t i v e m a t r i c e s  2  2  not both 0, X  3  2  , X  Hence we have the s o l u t i o n s  Since P is  and  equations  However not both 0  4  X\ and Xi+ are 0  a permutation m a t r i x ,  X  , X  x  , X  2  3  ,  must be permutation m a t r i c e s  x  since  P  =  Co)  i  x  0  0 or  X  Hence X ^ X , ,  =  B  2  and X  or  2  such t h a t P A ( G ! ) P = T  isomorphic  to  = B  =  3  A(G )  0  B . 2  implies  2  3  must t h e r e f o r e be square and hence m=n.  3  X£BJX  Conversely P i B ^  2  , and  4  i n the l a t t e r case X  X  P  the e x i s t e n c e o f a permutation P  and hence again by LEMMA 1.1,  2  G  ,  is  J^  2  m x n  o f G(m,n) i s An obvious 1.3 Gi(m,n)  ^,  a matrix with a l l  LEMMA : G ^ m . n )  From LEMMA 1.2 P  if  =  is:  i s m o r p h i c to G ( m , n ) i f  and o n l y  2  2  is  r  l s  P  2  G  x  is  such t h a t P i B ! P  Pi(J-Bi)  P  2  = J - B  isomorphic to  if  COROLLARY,:  same c o l o u r PROOF :  2  2  isomorphic = B . 2  to G  But P i B ! P  , and P l ( J - B i )  P  and o n l y  2  = B  2  = J-B  2  if 2  if  and o n l y if  and  2  is  A graph and i t s  the COROLLARY b i p a r t i t e complement have the  group. From LEMMA 1.3  if  2  G .  As a consequence o f LEMMA 1.3 1.4  G(m,n).  2  there e x i s t  only i f G  the b i p a r t i t e m a t r i x o f  i s o m o r p h i c to G ( m , n ) .  PROOF :  J~PlBiP  is  graph,  e n t r i e s o n e , the b i p a r t i t e m a t r i x  g i v e n by J - B where B i s  but important r e s u l t  is  is  G .  S i n c e the b i p a r t i t e m a t r i x o f the complete b i p a r t i t e n  x  and l e t t i n g  B  1  =  B , 2  Pi  Pl<ep =  0 =  2  -0 and o n l y  P  •  corresponds  A  t o an a u t o m o r p h i s m ^fe  '  if  PJ 2  if  j » e p ( G ) w h e r e P(G)  b i p a r t i t e graph G.  But  is  the automorphism  | P^ = • P i « P }  is  2  group o f  just  the  the c o l o u r  group  A bipartite  graph  o f the graph G. The c o n c e p t o f r e d u c i b i l i t y i s G(m,n) i s  said  graph.with bipartite  t o be r e d u c i b l e  K components,  if  K > 1.  are disconnected  its It  g r a p h s whose complements  complement)  now d e f i n e d .  b i p a r t i t e complement is  be a g i v e n If  G is  bipartite  a  immediately obvious that  (not  t o be c o n f u s e d  constitute  reducible  The c o n c e p t o f c o m p l e t e r e d u c i b i l i t y i s LetG  is  with  all  bipartite  graphs.  defined  inductively.  graph.  complete b i p a r t i t e , then.G  is  s a i d t o be  completely  reduced. T h e . f i r s t stage;of taking  reduction. ,is  t h e b i p a r t i t e complement  reduced.  G is  The K - t h  said  stage:of  K-1  of  components  not  of  completely  reducible.  of determining  the  not completely reduced at  the  reduction.  A b i p a r t i t e graph G i s stage  K-reducible  of reduction are  A b i p a r t i t e graph G i s components  i t is  reduction consists  complement o f a l l  at the K-th  o f G, p r o v i d e d G i s  t o be 1 - r e d u c i b l e i f  bipartite stage  d e f i n e d t o be t h e o p e r a t i o n  obtained at the  serve  Kth s t a g e  G : =  of reduction  reduced.  to i l l u s t r a t e the  a  obtained  reducible.  completely reducible  b i p a r t i t e and h e n c e c o m p l e t e l y Some e x a m p l e s  i f t h e components  «r 2.  idea.  i f f o r some K a l l are  complete  7  fig. Hence 1^  each  component  of G i s completely reducible since  f o r some m,n , n a m e l y m=n=2 o r m=0, n = l .  n  isolated  vertex  1.1  v o f G~ w i l l  each  is  For completeness,  an  be d e f i n e d t o be Ki a i f v e V , a n d x  >  K  i i f Ve V  e.g.  2  .  ;:• 7  1  6  S  G : =  2. 8  3  f  G : = fig.  Although  G i s reducible, i t i s not completely  c o n n e c t e d component bipartite  complement  of £ with eight being  given  vertices  1.2  reducible since the  i s not r e d u c i b l e , i t s  by :  H : =  fig.  1.3  1.3  THE COLOUR GROUP OF A B I P A R T I T E GRAPH As  indicated  inthe  introduction, the colour  b i p a r t i t e graph i s t h e maximal  s e t o f automorphisms  group, f * ( ) » G  of a  with the property  8 t h a t ij{f ( v ) ) graph.  = j{v)  where  We show t h a t r * ( G )  Obviously  I  er*(G),  is is  a c o l o u r i n g of the v e r t i c e s of  in fact a  s i n c e j (v)  for  any  group.  = j (Iv).  = j i f  Now s i n c e f ( v ) = j ( ^ ( v ) )  1  ^ ) )  i t follows  Let^.j^z  Finally,  e  r*(G).  Then f C n ?  (v))  2  there is  permutation group  Let  of the graph,  concerning  such  follows  operation in  a corresponding  d e f i n e d on t h e v e r t i c e s o f G , we s h a l l  the  some d e f i n i t i o n s  from  groups.  A and B be two p e r m u t a t i o n g r o u p s " a c t i n g on s e t s  X and  T h e i r s u m , A + B , i s .a g r o u p  a c t i n g on t h e d i s j o i n t u n i o n XUY a n d  elements are ordered p a i r s  of permutations  w h e r e z e XUY  («+/?)  is  (2)  permuted a c c o r d i n g  =  oi. H  if  HEX  /3 z  if  HeY '  Their composition A [ B ] is and s e q u e n c e  (/^i,/^,.../^)  permutation denoted  (<x  XxY  =  (d;/3i,.../3 ) d  We s h a l l Harary  [12,  «EA,/3EB,  a group  [12,  .../3 ) i n d  p.  A[B]  the group  denotes  163]  such t h a t f o r [12,  f  one.component, where n.G.  w r i t t e n <*+/?,  in B there is  ( « x . /3..Y..).  concerning  whose  a c t i n g on XxY w h e r e f o r <k eA  of d permutations  ,  Y.  to:  make u s e o f t h e f o l l o w i n g t h e o r e m ( s e e  p. 1 6 6 ] )  T(G).  permutation P  henceforth consider  and u t i l i z e  so  2  the a s s o c i a t i v i t y o f composition i n r * ( G )  for each^eP(G),  [12]  1  = f C / ( v ) ) = f (v)  i m m e d i a t e l y f r o m . t h e the a s s o c i a t i v i t y of the group  Harary  ^ ef*(G)  that  r*(G).  je  Since  the  for  a  (x^ ,y.)'e p.  164]  example,  o f a g r a p h w i t h more  n. c o p i e s  unique  o f t h e graph G.  :  than  1.5. n G r  is  r  THEOREM  given  where S  : The g r o u p  by  r ( G . ) = S!  - denotes  o f t h e g r a p h .6 w h e r e  [rCGj] + S  h  the symmetric group  [r(G )]  n  For the complete b i p a r t i t e graph,  1^  n  ,  1  1  + ...+  2  o f degree  G=n G Un G U...u 2  2  S ,.[r(G )]. n  r  n^.  the automorphism  group  isi e a s i l y c a l c u l a t e d . Since  = "R^ + "K~  n  ,  n  and s i n c e  1^ + Y  where  = K^UK^"  =  V(\fiK  is  the n u l l  [ 1 2 , p . 1 6 6 ] we h a v e :  n )  sincer(G)=  r(^)  +  ,  m  ,  m =  r(K ) n  r(2K ) m  1  m  n  Denote b y C * ( G ) since T(G) and G  ,  m  the c o l o u r group  = r(ff),  and  subgroup  of V { & i )  c o l o u r group  2  + r(G ) 2  of  is  n  =  ]  since r(K I f m=n, n  ,  | n  )  = r*(K ) m  s  vertices in  which i s  m =  n  Then  (i) T * ( G )  = P*(Gi)  since r * ( G i )  =p*(Ia)  +r*(G ) 2  +T*(G ) 2  is  where G  x  t h e maximal  colour preserving.  Hence t h e  +r*(K ) n  w h e r e a l l v e r t i c e s o f 1^ a r e o f t h e same holds  colour.  since for a particular colouring  are of colour opposite to those o f  G r a p h s whose a u t o m o r p h i s m s vertices  n  ~ + s.-.  the r e s u l t s t i l l  all  n  w  = r *(\ )  =  165]  T O  (  *  • r  f  p.  e a s i l y determined.  *  r  o f G.  ( i i ) p*(GiUG )  are non-isomorphic,  2  [12,  '  > S [S ] 2  graph w i t h m p o i n t s ,  r e s u l t only  K^.  i n an i n t e r c h a n g e  o f t h e same c o l o u r h a v e c o l o u r g r o u p  identical  with  of  of auto-  10 morphism group.  Such g r a p h s where m f  n  as  t h e f o l l o w i n g have t h i s  property:  n  fig. while  t h e f o l l o w i n g do  1.4  not:  ^m,m  i Clearly  i  the c o l o u r group  fig.  o f a n y b i p a r t i t e g r a p h G c a n be  w r i t t e n as t h e d i r e c t sum o f two s u b g r o u p s  ofr(G),  consisting of.all  automorphisms  all  of v e r t i c e s o f the o p p o s i t e  automorphisms  1.6  THEOREM  as g i v e n  :  +  ...  1  + S  2  2  r  r  is  given  r (G) 1  andr (G), 2  colour. analogous  to t h a t  for  1.5.  of the  byr*(G)  = S  graph n  C r * ^ ) ]  + S .  LP*(G )]  n  2  - ir*(G )]. r  The p r o o f i s Noting  THEOREM  The c o l o u r g r o u p  G = n G Un G U...Un G 1  in  namely  of vertices of onecolour,  We now s t a t e a r e s u l t f o r c o l o u r g r o u p s automorphism groups  1.5  r  a d i r e c t consequence  the f a c t t h a t p *(G.)  d e f i n e d a b o v e , we o b t a i n :  =T  (G.)  of the previous  +T (G.) 2  discussion.  w h e r e T5 and T  2  are  as  11 1.7 COROLLARY : If G EE mdU... Un G thenT*(G ) = S R  FA^)  R  n  + ^ ( G . ) ] +...+ s , [ r i ( G ) + r ( G ) ] 2  n  r  2  R  r We now establish the following lemma concerning the existence of a bipartite graph with given group: 1.8 LEMMA : Let p* be the group defined as follows: ~=  \ % \ ?J h £ \ r. . ] m^, n^ denotes the degrees of the groups +  +  T , ] where m^ and n^. Then there  +  n  n  +  n  «*  exists a bipartite graph with Z k.(m.+n.)  vertices and at most  1=1  r  ?j ^ i ! i 0 1  n  PROOF :  edges with colour group p*. Let S  act on the set .C..=  k  {1 2 9  s  K | , i  letP  m  act on the set V , and P on the set V • of m* and n. elements m. n nj r  respectively. s  =< ^  }  Thenp* acts on the set:  c  i  i  . « - < V  Clearly, this set contains  (V""»•}}  r  r  r  2 k. (m-.+n.) ordered pairs of elements  of the form <i., v-> where i^ec., v.e{V UV,,.:} . J J J J J * m^- n,^.' m  Let these elements denote the vertices of a graph with v(G) = S. We now define the edge set E ( G ) to be any subset of the set |(<i .,V| ;> i.e C for some j and v. , e\, v eVi, or V . E V L . J  <  t  and-v E\/|/., |. The maximal number of edges is thus Z k^m.n. and i f g  G has this number of edges then G E  U k-rC  i-i  1  V i -  A further lemma concerning the nature of the graphs at each stage.of reduction is required before relating the concepts of isomorphism and colour groups in THEOREM 1.10. 1.9 LEMMA : Let G ^  denote the union of all complete  bipartite graphs obtained at stage i of the reduction of a completely reducible bipartite graph H. Then T*(H) =r*(G^') +...„T*(G^), where H is completely reduced after t stages.  12 PROOF :  For each stage  of  reduction  ff<i>.G< >UH< >,H<°>.H 1+i  where H ^  1+1  denotes  obtained at stage  the union of a l l graphs not complete b i p a r t i t e i .  Now s i n c e H i s  c o m p l e t e l y reduced a f t e r  t  stages ff-(t-l)  s  ( t )  G  Further  r*(H)=r*(H)  and  P *(H)  by COROLLARY  W *) 1  = r*(G^  = P*(G^^+r*(H^ p *(H( ))  =f*(G  1  and  r*(H  (  '  t  r  hence T * ( H ) 1.10  i  f  * (  r  THEOREM :  V(H  i  )|,  ( l )  i  of the f i n a l  ( l )  If  f  0  r  e  a  say G ^  S.  + S  c  i  +  1  )  ),  +.. . + r  2  * ( G ^ ) .  Then G i s  isomorphic  ( l )  )|  for all  isomorphic  ( r  X  edges,  V  U  V  s  n  c  e  i  permutationally isomorphic  -J  the union o f complete b i p a r t i t e  s  S  l  l  i s g i v e n by S> , [ S r  + SA ].  Applying  LEMMA 1.8  £ k-(m.+n.) v e r t i c e s , r * ( G ^ ' ) i~l { ( X  m  L  fV^UV^}  C l  U  (  and  c  x  {  '  o  w  f  and h e n c e E ( H ^ )  |E(G^)|,  hence  G ^  r  o  m  c  E  M  M  A  1  ,  8  E ( G ^ ) .  and H ^  G  to  a  s  t  n  e  m  a  x  v  i  y  m  +  construct  consequently v  2 h  to  + S• . ]  tn^  .  [S  K  the  is  a c t on v e r t e x s e t  ^}  index  decomposition.  = U k.Km.n., P*(G)  N  the  G and H h a v e  (') C  only  |V(G^^)| =|  t being  to H then o b v i o u s l y  a n d t h e same  ] +...+  i=l,2,...t,  obtained  t o H i f and and  and  reduction.  -j. i  n  a vertex set with )  (  +r*(G^ ^)  suppose p * ( G ^ )  graphs,  h  *(H  )  )  )|=|E(H  G is  Conversely  ( i )  +P  the union o f a l l complete b i p a r t i t e graphs  same number o f e d g e s  P*(H  )  )  L e t G,H be two c o m p l e t e l y r e d u c i b l e g r a p h s ,  stage of  PROOF :  [S'  t  1  h,  permutationally isomorphic t o r * ( H ^ )  s  |E(G  P*(u(i))  (  +  of the r e d u c t i o n .  ( 0 )  G  i  = r * ( G ^ )  d e n o t e by G ^ , H ^ at stage  (  )=r*(G  )  1.4  a  1  B u t by h y p o t h e s i s  ,  )  n  n  2  number  of  |E(H^)| =  h a v e t h e same v e r t e x and e d g e s  sets  13 and a r e h e n c e  isomorphic. .It)  Now G c a n be c o n s t r u c t e d f r o m G L e t Gj. = G  v  '  v  (2)  , G  (+)  G  v  v  '  as f o l l o w s :  a n d d e f i n e G.._.| t o be t h e b i p a r t i t e c o m p l e m e n t o f  G^ '""'^UG..  T h e n by c o n s t r u c t i o n G i s g i v e n  corresponds  t o t h e union o f a l l graphs not complete b i p a r t i t e p r i o r  1  to  by G-j s i n c e e a c h G^  reduction a t stage i . Utilizing  groups  a well  known r e s u l t c o n c e r n i n g  ( s e e f o r example [ 1 ] p. 1 4 6 ) , namely,  t h e sum o f i f  and T. a r e  isomorphic groups f o r i = l , 2 , . . . n then T i s isomorphic $ = 5 ^ 2 + . . . +S  n  and T=T +T +...+T 1  2  c o n s t r u c t . t h e c o l o u r group all  isomorphic  t o S where  , we c a n a p p l y THEOREM 1.10 t o  o f any c o m p l e t e l y r e d u c i b l e g r a p h ,  since  t h a t i s r e q u i r e d i s t h e c a l c u l a t i o n o f the c o l o u r groups o f  complete b i p a r t i t e graphs a t each stage  of the reduction.  14 CHAPTER 2 Reducible Trees  and  Graphs  REDUCIBLE TREES The i m p o r t a n c e o f t h e c o m p l e t e l y r e d u c i b l e g r a p h s was i n THEOREM 1 . 1 0 .  Necessary  and/or s u f f i c i e n t c o n d i t i o n s  d e t e r m i n e d f o r g r a p h s t o be r e d u c i b l e . notation shall  be a d o p t e d .  If  In  V^. = | v - j , . . . v ^  c o l o u r e d v e r t i c e s , t h e n f o r any WeV-j, w i s Since  is  said  are  the  now  following  a set of m i d e n t i c a l l y t o h a v e c o l o u r m.  any b i p a r t i t e g r a p h G ( m , n ) c a n be p a r t i t i o n e d i n t o m v e r t i c e s  o f one c o l o u r , colour m or 2.1  n vertices  LEMMA :  PROOF : is 0 since  of another, every  v e r t e x i n G(m,n)  has  n. If  there exists  and c o l o u r n , t h e n G i s  its  the sequel  established  its  a v e r t e x i n G(m,n) o f degree m  reducible.  L e t v be s u c h a v e r t e x . adjacency to a l l  non-adjacency  to a l l  G(m,n) = H(m,n-1) U K  ,,  Then t h e d e g r e e o f  vertices  vertices  of opposite colour in G implies  of opposite  and G i s  v i n G(m,n)  c o l o u r i n G.  Hence  reducible.  o, I  A second reducibility 2.2 degree  s i m p l e LEMMA p r o v i d i n g  for  is:  LEMMA :  n^l  a sufficient condition  If  there e x i s t non-adjacent  a n d c o l o u r n , d e g r e e m-1  vertices  of colour  r e s p e c t i v e l y , then G(m,n)  m,  is  reducible. PROOF :  L e t v be a v e r t e x o f d e g r e e m - 1 ,  v e r t e x o f degree  n-1,  c o l o u r m i n G(m,n).  o f w =1  i n G ( m , n ) and s i n c e  Further  (v,u)  {. E ( G )  G(m,n) = H ( m - l , n - l )  and  (v,w)  (u,w)  t  i  The d e g r e e o f v =  E ( G ) we have  E((3)  U K-j -| and G i s  c o l o u r n and w be a  (v,w)e  E(G).  f o r any o t h e r u e V ( G ) .  reducible.  Although  degree  the  Hence previous  15 two lemmas  provide rather elementary s u f f i c i e n t conditions  r e d u c i b i l i t y of a graph, G(m,n) i s requires  a tree.  This  LEMMA :  bipartite  If  in  T(m,n) i s  c o m p l e m e n t T ( m , n ) has  PROOF :  S i n c e T(m,n)  n-n-|) w h e r e G  is  2  Assume m-j +n-j CASE 1 :  >  (m-rt^) +  (m-n^) +  the  and s u f f i c i e n t  e m b o d i e d i n THEOREM 2 . 4  if which  proof.  a r e d u c i b l e ( b i p a r t i t e ) t r e e , then a component  K-j -j o r  K  its  -|.  Q  r e d u c i b l e , T ( m , n ) = G^(m^,n-|) U Go^m-m-i, c o n n e c t e d , and G-| i s  the  smallest  T.  3. (n-r^)  Then T ( 3 , 3 ) = K-| CASE 2 :  is  is  its  not n e c e s s a r i l y  c o n n e c t e d component o f  =  3.  U K-|  2  (n-n-,) >  Then G-j c o n t a i n s  In  observation  the f o l l o w i n g r e s u l t  2.3  vertices  they are both necessary  for  a n c 2  '  by i n s p e c t i o n T i s  disconnected.  3.  two v e r t i c e s o f o n e c o l o u r , G  o f t h e o p p o s i t e c o l o u r and h e n c e T has  2  contains  a four  cycle.  e i t h e r c a s e m-j+n-j » 3 i m p l i e s T c a n n o t be a t r e e .  < 3 f o r w h i c h e i t h e r m-j =n-j  two  Hence m-j+n-j  = 1 i n w h i c h c a s e G-j = K-j - j , o r m-|=o, n-| = 1  and t h e r e f o r e G, = K I , o, l As a d i r e c t c o n s e q u e n c e 2.4  THEOREM :  of the previous  A t r e e T(m,n)  is  lemmas we now  have:  r e d u c i b l e i f and o n l y  if  v e r t e x of degree m or n or non-adjacent v e r t i c e s of opposite m,n and d e g r e e s PROOF :  If  a n d m-1  i f T is  o r 2.)  T is  as  in  of opposite colours I f T i s as i n  r e d u c i b l e t h e n by LEMMA 2 . 3  2.2. 1.)  T = K-j -| U  T = K , U G(m,n-1). o, I 2.),  there exists  a pair of non-adjacent  vertices  o f degrees m-1, and n - 1 . 2 . ) , t h e r e e x i s t s a v e r t e x o f d e g r e e m.  By i n s p e c t i o n o f a l l trees through  colours  respectively.  C l e a r l y s u f f i c i e n c y f o l l o w s f r o m LEMMA  Conversely G(m-l,n-l)  n-1  i t has  10 p o i n t s ,  t r e e s w i t h up t o s i x see f o r example Harary  vertices [12])  (in a l i s t  we h a v e  the  of  a  16 following 2.5  corollary  :  COROLLARY  :  All  trees with less  than seven  vertices  are  reducible. As  examples  w i t h seven T]  of  vertices  =:  i r r e d u c i b l e t r e e s , we g i v e a l l  irreducible  trees  :  . , . . . . .  We c a n use THEOREM 2 . 4 reducible  trees  TYPE 1 :  non-adjacent  to construct  the general  fig.  2.1  form o f  all  : vertices  of colours  m,n a n d d e g r e e s  n-1,  m-1  m*3  m-l  w-2  TYRE 2  :  v e r t e x o f d e g r e e m and c o l o u r  That these diagrams particular  properties  2.2  fig.  2.3  n  do i n f a c t c h a r a c t e r i z e a l l  specified  fig.  trees with  the  as TYPE1 o r TYPE 2 c a n be e x h i b i t e d  17 by e x a m i n i n g  the minimal  allowable extensions  the minimal  namely tree  properties those  together with  preseving  the  the  property.  is:  1  1  (n) (m) ( n ) the a l l o w a b l e extension to vertices  2 or  t r e e , w h i l e any characteristic  is" t h e  of  vertices  vertex  i n t r o d u c t i o n o f new v e r t i c e s  F o r TYPE 2 t r e e s , allowable extensions from V b e i n g  adjacent  to 1 o r 4 r e s u l t s  n o t a d j a c e n t t o any  property  colour.opposite  (m) adjacent  3.  Introduction  vertex  with these  of the graph,  F o r TYPE 1 t r e e s , T  trees  o f TYPE 1 the minimal  o f 1,2,3  or 4 destroys  a single  vertex  tree is  than o r equal  to V are adjacent to  in the distance  t o 2.  Thus a l l  V and  the  of the  new  vertices  diagram  are i n . f a c t completely 2.6:  THEOREM :,  completely  of  V.  U s i n g t h e b i p a r t i t e m a t r i x o f t h e TYPE 1 and TYPE 2 t r e e s in the previous  the  trees.  a r e any w h i c h r e s u l t less  i n a TYPE 2  i t c a n now be shown t h a t t h e r e d u c i b l e  given trees  reducible.  If  T(m,n) i s  a r e d u c i b l e t r e e then T(m,n)  is  reducible.  PROOF :  The b i p a r t i t e m a t r i x m+1  m+2  0 0  m-1 m  0 .  0 1  and f o r a TYPE 2 t r e e i s  given  by  f o r a TYPE 1 t r e e i s  given  by  :  18 m+1,m+2  m" m'+l m '+2 :  m  m+i-j ,m+i^ +1  0 ..  0  0  0 .. 1 .. 0 ..  . 1 0  0 1  0 ..  .  since T is  t h a n one c o m p o n e n t . are  2  ...  2  0  0  m+i _^ ,m+i K  0  -j+1  K  m+n  0  0  ••••• 1  where the l a b e l l i n g c o r r e s p o n d s definition  m+i ,m+i +l  0  to figures  reducible, its  2.2  and 2 . 3 .  Now by  b i p a r t i t e c o m p l e m e n t has  The b i p a r t i t e m a t r i c e s  for T i f T is  more  o f TYPE 1  : 1  ^  = [1]  and B  2  1  = 1 0 1  Now T i s  c o m p l e t e l y r e d u c i b l e i f and o n l y  r e d u c i b l e w h e r e T = G-|UG G  2  is  B .  B u t B-j i s  2  reducible.  2  i f G-j and G  2  are completely  and t h e b i p a r t i t e m a t r i x o f G^ i s  the b i p a r t i t e m a t r i x of  The b i p a r t i t e c o m p l e m e n t o f G  2  B-j,  K-j -j h e n c e G-| i s  of  completely  is  0 1 0 hence G  2  =  -| U (m-1)  Q  U (n-1)  K  Q  -| a n d t h e r e f o r e G  2  is  completely  reducible. If of G  2  is  T is  o f TYPE 2 t h e n T* = K  given  by  :  Q  1  U G  2  where t h e b i p a r t i t e m a t r i x  19 1 • • • 1 1 • 0 . . . 0 1 . . •. 1 1 . . . 1 1 . . . 1 0 . . . 0 1 . . . 1  1  . . .  0 . . 0  and t h e b i p a r t i t e m a t r i x o f G  "0 . . . •  is  2  0 0 . . .  hence  0 0 . . .  0"  1 . . . 1 0 . . . 0 0 . . . 0 0 . . . 0 1 . . . 1 0 . . . 0  • _6  i  and t h e r e f o r e G~ = K,. d. np  UK,. n  U...K-.. 1 1  2  K  .  - 7  i and i s  completely reducible.  The p a r t i c u l a r n a t u r e o f t h e b i p a r t i t e m a t r i c e s trees  t o g e t h e r w i t h t h e r e s u l t o f THEOREM 2 . 4  o f an a l g o r i t h m f o r i s o m o r p h i s m The a l g o r i t h m re-orders t r e e as g i v e n  by i t s  o f f i g u r e 2.2  or 2.3.  the l a b e l s  d e g r e e , and t h e c o l u m n s  Two r e d u c i b l e t r e e s  are then isomorphic  i f and o n l y  and hence  We now s t a t e t h e a l g o r i t h m . then the a l g o r i t h m stops  least  at step  i f an i s o m o r p h i s m  one o f them i s  re-arranged  re-arranged  on p a g e s .1,7 a n d if  they  18.  have  identical bipartite matrices. Note t h a t i f a t r e e i s 3.  exists  reducible.  trees.  to the l a b e l l i n g  are then  as g i v e n  determining  construction  The r o w s o f t h e b i p a r t i t e m a t r i x a r e  i n one o f t h e f o r m s  label!ings,  the  of the v e r t i c e s o f a r e d u c i b l e  the matrix i s  identical  reducible  d e t e r m i n a t i o n between r e d u c i b l e  b i p a r t i t e matrix to correspond  in order of increasing until  allows  for  The a l g o r i t h m i s b e t w e e n two t r e e s  not  reducible  effective for provided  at  20 2.7  ALGORITHM : 1)  matrix  B^  m x n  Calculate  ^.  a l l row and column  Assume m < n . n  else  sums o f t h e b i p a r t i t e  tn  2)  If  I  3)  If  Z b . . = n - 1 , b.„ = 0 and  b.. = n o r  Z b . . = m go t o 4 . Z b.., = m - l „ g o t o 4 ,  STOP B n o t r e d u c i b l e . 4)  Re-order  rows o f B s o t h a t  5)  s e t I=J=1  6)  scan row I u n t i l  Z b.  . $  Z\b..  • where  v  K > 1.  J.  c  a ^ =1.  I n t e r c h a n g e columns j and  S e t J=J+1.  (mxn)  Q  f  t  h  e  7)  I f J « n go t o 6 , e l s e  8)  I f I ^ m go t o 6.  9)  Repeat  s  e  c  o  10)  n  d  g  r  a  steps p  s e t 1=1+1  1 through 8 f o r t h e b i p a r t i t e  matrix  h .  I f t h e two r e s u l t i n g  matrices  are identical  then  t h e two g r a p h s a r e i s o m o r p h i c .  REDUCIBLE GRAPHS Unfortunately, easily that  characterized  the conditions  example  illustrates  reducible  b i p a r t i t e graphs i n general  as i n the case o f t r e e s .  Later  o f THEOREM 2 . 4 a r e s u f f i c i e n t that they  a r e not so  results  although  will  show  the following  are not necessary.  Let G :  f i g . 2.4  21 The b i p a r t i t e c o m p l e m e n t i s  given  by  :  fig. .Now s i n c e  the components  of G.are  both.trees with less  v e r t i c e s we c a n a p p l y COROLLARY 2 . 5 However G s a t i s f i e s reducible 2.8 is  and h e n c e G i s  than  2.5  seven  completely reducible.  none o f t h e c o n d i t i o n s w h i c h c h a r a c t e r i z e d  trees. LEMMA :  If  G(m,n)  has  a r e d u c i b l e spanning  t r e e then  G(ni,n)  reducible. PROOF :  vertices  If  G is  n-1  illustrated  and m-1  r e s p e c t i v e l y a n d h e n c e by LEMMA 2.1  r e d u c i b l e g r a p h s have  by e x a m p l e .  Necessary  e x i s t e n c e of a r e d u c i b l e spanning THEOREM  :  r e d u c i b l e spanning  t r e e i n G are given  2.8 G 'has  If  tree if.and only  G(m,n)  has  or  trees  was  for  the  : has  a  i f there e x i s t non-adjacent  vertices  n-1  there  and m-1  respectively or  n.  a r e d u c i b l e spanning  t r e e t h e n f r o m LEMMA  v e r t i c e s which are of degree m or n or are n o n - a d j a c e n t ,  o p p o s i t e c o l o u r and d e g r e e m-1 Conversely n - 1 , m-1  by  A c o n n e c t e d b i p a r t i t e g r a p h G(m,n)  a v e r t e x of degree m or  PROOF :  r e d u c i b l e spanning  and s u f f i c i e n t c o n d i t i o n s  o f o p p o s i t e c o l o u r s m,n a n d d e g r e e s exists  colours  reducible.  That n o t - a l l  2.9  t r e e then G c o n t a i n s  of degree m or n or non-adjacent v e r t i c e s of opposite  m,n and d e g r e e s LEMMA 2 . 2  G has a r e d u c i b l e s p a n n i n g  suppose  and c o l o u r m , n .  colour n except v  ,,  v  and  n-1.  G.has n o n - a d j a c e n t v e r t i c e s Then is  of  is  adjacent to  adjacent to a l l  all  v  ]»  v m +  ]  of  vertices  vertices  degree of  of colour m  22 except  "v-j.. S i n c e  f r o m V-| t o V  6 is  assumed t o be c o n n e c t e d  whose l e n g t h  m + 1  vertex, of opposite  colour  and hence d e g r e e  is  3.  Otherwise  there exists there would  Hence G has  (u,w)  where If  the  u is  G has  adjacent to  and w i s  m + 1  m +  -|  tree  of  eE(G) a n d an e d g e  )  adjacent to  a v e r t e x v o f d e g r e e m, t h e s p a n n i n g  a  thanv  a r e d u c i b l e spanning  TYPE 1 c o n s i s t i n g o f a l l ( u . v ^ ) eE(G), a l l ( w , v  path  exist  t o v-j n o t a d j a c e n t t o v - j , o t h e r  < n-1.  a  v"  m +  i.  tree is  given  by  following: 1)  set  o f .edges  2)  set  of a l l  adjacent to  (v,u.j)  together  e E(G)  edges such t h a t  e x a c t l y one v e r t e x  u.  (u.,w.)  with eE(T)  i m p l i e s w.  is  e V(T).  3) By c o n s t r u c t i o n  T is  a r e d u c i b l e g r a p h o f TYPE 2 s p a n n i n g  The s p a n n i n g t r e e o f a r e d u c i b l e g r a p h i s nor are a l l following  spanning  examples  trees  V(G).  not n e c e s s a r i l y  o f a r e d u c i b l e g r a p h r e d u c i b l e as  reducible  graph:  fig.  2.0  has  since  the  show.  L e t G be t h e f o l l o w i n g  By LEMMA 2 . 1 ,  unique,  degree  (3)  = m = 4, G is  a r e d u c i b l e s p a n n i n g t r e e T-,  :  3  2.6  r e d u c i b l e and by THEOREM  23  T-| i s  a r e d u c i b l e spanning  reducible  spanning  t r e e o f TYPE 2 .  However 1^ i s  also  a  t r e e o f TYPE 2 n o t i s o m o r p h i c t o T - j :  vF i n a l l y Tg i s and hence i s  a l s o a spanning  as  n o t s a t i s f y THEOREM  2.4  nonreducible :  Two n o n - i s o m o r p h i c g r a p h s trees  t r e e b u t does  may h a v e i s o m o r p h i c r e d u c i b l e s p a n n i n g  the f o l l o w i n g example i l l u s t r a t e s :  In a d d i t i o n t o i s o m o r p h i c s p a n n i n g  t r e e s , G-j and G  2  v e r t i c e s w i t h t h e same d e g r e e s , and same number o f e d g e s .  fig.  2.7  also  have  A  24  previous  example, f i g . 1.2,  isomorphic  gives  r e d u c i b l e spanning  two n o n - i s o m o r p h i c  t r e e s , v e r t i c e s w i t h t h e same  and e c c e n t r i c i t i e s , t h e e c c e n t r i c i t y b e i n g vertex  from any o t h e r i n t h e  graph.  The r a d i u s  diameter d(G),  is  the radius  is  a  introduced in  order  and d i a m e t e r o f a r e d u c i b l e  d e f i n e d t o be t h e minimum e c c e n t r i c i t y , t h e  t h e maximum e c c e n t r i c i t y o f t h e  2.1.0 THEOREM : . A l l  degrees  graph.  concerning  r(G)  with  t h e maximum d i s t a n c e o f  The e c c e n t r i c i t y o f .the v e r t e x o f a g r a p h t o r e l a t e some r e s u l t s  graphs,  vertices.  b i p a r t i t e graphs of radius  less  than 3 are  reducible. PROOF :  L e t v be a p o i n t o f minimum e c c e n t r i c i t y i n a b i p a r t i t e  graph G(m,n)  where r ( G )  < 3.  Then a l l  v e r t i c e s are a d i s t a n c e  most 2 from v and hence a l l v e r t i c e s o f c o l o u r o p p o s i t e a d j a c e n t t o v. reducible As  Hence G c o n t a i n s  by LEMMA  a p o i n t o f d e g r e e m, and i s  COROLLARY :  the diameter of G i s PROOF :  r(G)  2.2  and 2 . 3  If  G is  a graph  less  than  5.  < 2 implies G is  all  of radius  LEMMA :  less  r e d u c i b l e and has t r e e T.  r e d u c i b l e spanning  4 and s i n c e d ( G ) < d ( T ) .2.12  therefore  following  d e g r e e m and hence a r e d u c i b l e s p a n n i n g figures  are  2.1.  a c o n s e q u e n c e , we h a v e t h e  2.11  to v  at  f o r any g r a p h ,  <  Every c i r c u i t of length.2p  a vertex  then  of  Now by i n s p e c t i o n  trees  d(G)  than 3,  have d i a m e t e r  of  d(T)  4. is  irreducible for  p ^ 4. PROOF : K  2  2  i f p=2,  and c o n s e q u e n t l y  then the c i r c u i t i s  of  reducible.  t h e b i p a r t i t e complement  the c i r c u i t of length 6 i s For p ^ 4 . t h e  proof  is  If  isomorphic  a consequence  L e t G have p » 3 p o i n t s .  If  p=3,  length  4,  isomorphic  to  t o 3K-j ^ a n d h e n c e r e d u c i b l e . o f a t h e o r e m by P o s a  f o r every n,  [20]  1 £ n;< ( p - l ) / 2 ,  : the  of  25  number o f p o i n t s f o r odd p ,  o f degree n o t - e x c e e d i n g  t h e number o f p o i n t s  n is  o f degree  less  (p -  t h a n n and  1)  does not  if,  exceed  2 (p-l)/2  then 6 i s  .The  Hamiltonian.  b i p a r t i t e complement o f a c i r c u i t o f  vertices  each o f degree  p-^2.  .We  use  2p  condition, is  Hamiltonian  the  and  connected. ' this  a-reducible  has  Hence t h e b i p a r t i t e c o m p l e m e n t o f  c i r c u i t with p ^ 4 satisfies.Posa's consequently  length'2p  r e s u l t t o e s t a b l i s h an u p p e r b o u n d on t h e r a d i u s  of  graph.  2.1.3 THEOREM :  All  b i p a r t i t e graphs o f radius  g r e a t e r than  3  are i r r e d u c i b l e . PROOF : If figures If  L e t G ( m , n ) be a b i p a r t i t e g r a p h w i t h  G is 2.1  a t r e e then G i s and 2 . 2 ,  G has  e(v)>8.  n o t r e d u c i b l e s i n c e by i n s p e c t i o n  the radius  them o f l e n g t h n o t l e s s  t h a n 8.  the graph  If  forms  is  vertex w is  length  If  the path  be a v e r t e x on t h e p a t h a d j a c e n t t o w a n d  2(p-l)  a n d by LEMMA 2 . 1 2  b i p a r t i t e complement o f the  This is  graph  length  consider  contains  irreducible. in  a  The the  n o t r e d u c i b l e s i n c e any v e r t e x n o t on t h e p a t h P  a single  LEMMA 2 . 1 2 . C i s  odd  circuit.  a d j a c e n t t o a t l e a s t one v e r t e x i n G has  3.  a vertex v with  adjacent to every vertex of opposite colour  Hence G i s  s  a c i r c u i t o f l e n g t h > 2p  irreducible.  P t o g e t h e r w i t h the e d g e . ( v , w ' j .  c i r c u i t of  If  t h e n G has  is  the length of the path 1 i s  (v,w)  w h e r e 1 = 2 p - l a n d by LEMMA 2 . 1 2 e v e n , l e t w'  ^8  reducible trees  of  two v e r t i c e s v,w w i t h a p a t h P b e t w e e n  t h e n P t o g e t h e r w i t h t h e edge  1 is  of a l l  no c i r c u i t s o f l e n g t h  Hence.there e x i s t s  r(G)>3.  is  G.  c i r c u i t C of length > 8,  i r r e d u c i b l e , and a l l  then again  v e r t i c e s n o t on C m u s t  a d j a c e n t t o a t l e a s t one v e r t e x i n C , and h e n c e G i s  applying be  not r e d u c i b l e .  26 If.G  has more t h a n one c i r c u i t . o f l e n g t h > 8,  a n y two s u c h such  that  C| a n d C  circuits.  (v,w)  is  Then t h e r e e x i s t  n o t ah edge o f G .  a n d C2 be  v e r t i c e s v e C| a n d w e C  Hence  (v,w)  a r e c o n n e c t e d s u b g r a p h s by.LEMMA 2 . 1 2 ,  2  let  E E(G) G is  and  again  2  since connected  and hence i r r e d u c i b l e . L e t A=A(G) be t h e a d j a c e n c y m a t r i x o f t h e b i p a r t i t e g r a p h G. well  known p r o p e r t y o f t h e a d j a c e n c y m a t r i x i s 2.1.4 THEOREM [ 2 ,  walks  of  length  From.this is  n from v. result  the smallest  which i s  it  :  to  Using corollary  The i , j e n t r y o f A  is  e a s i l y e s t a b l i s h e d t h a t the radius  v a l u e o f n such  that A + A  COROLLARY : less  that A + A  +...+  A  is  there exists  than If  G is  contains  n  the  a row  smallest  a s t r i c t l y positive matrix. the  following  r e d u c i b l e t h e n by THEOREM 2 . 1 0  r(G)  <c 3 .  Hence  3  a row o f X = A + A  + A  which  is  Now s i n c e A i s  s t r i c t l y p o s i t i v e , where s y m m e t r i c and no  row  z e r o s , X i s s y m m e t r i c and no row c o n t a i n s a l l z e r o s , and T ' 2 9 ? XX = X is a s t r i c t l y positive matrix. B u t X = [A + A  2  + A  > 0 and h e n c e d ( G )  = A  2  + 2A  Summarizing  3  + 3A  4  + 2A ^  5  + A  6  > 0 implies A + A  has  shown t h a t a l l Two e x a m p l e s  t h r e e and d i a m e t e r l e s s  reducible.  + A  the r e d u c i b l e graphs are  o f connected graphs w i t h radius THEOREM 2 . 1 0  2  3  + A  4  +  A  5  6.  these r e s u l t s ,  than three are r e d u c i b l e . radius  A  seven.  + A ]  to s i x .  +...+  of G  all  therefore  the s e t  of  The d i a m e t e r o f a n y c o n n e c t e d r e d u c i b l e b i p a r t i t e  t h e a d j a c e n c y m a t r i x o f G.  6  2  and THEOREM 2 . 1 0 y i e l d s  2  contains  t h e number  v..  is  these r e s u l t s  PROOF :  3  is  n  :  2.15  A.is  :  s t r i c t l y p o s i t i v e , w h i l e the d i a m e t e r . o f G i s  value o f n such  graph  p.110]  A  included  in  up t o t h r e e a n d d i a m e t e r  up  the graphs w i t h radius  less  a r e now g i v e n  o f graphs  t h a n s i x w h i c h a r e and a r e  not  of  27  G: =  G: =  fig. G  is  a reducible.graph  The f o l l o w i n g is  not  reducible  :  w i t h d i a m e t e r 5 and r a d i u s  g r a p h G has  d i a m e t e r and r a d i u s  equal  2.8  :  3. to 3,  yet  28  The b i p a r t i t e c o m p l e m e n t o f G i s s u b g r a p h s b e l o w as  Hence G i s  given  by t h e u n i o n o f t h e  labelled.  c o n n e c t e d and c o n s e q u e n t l y G i s  The e x a m p l e s  two  in figures  2.8 and 2.9  serve  irreducible. to i l l u s t r a t e that reducible  g r a p h s a r e n o t c o m p l e t e l y c h a r a c t e r i z e d by t h e i r r a d i u s  and d i a m e t e r .  29 CHAPTER 3 An I s o m o r p h i s m T e s t i h g  3.1  Algorithm  f o r Completely  Reducibie  Graphs  COMPLETELY REDUCIBLE GRAPHS THEOREM 1.10  gives  necessary  and s u f f i c i e n t c o n d i t i o n s  completely reducible  b i p a r t i t e g r a p h s t o be i s o m o r p h i c .  THEOREM 2 . 6  a characterization of completely  Before  provides  implementing"THEOREM  (section  3.2),  bipartite  we s h a l l  i n an i s o m o r p h i s m  discuss  other classes  Moreover,  reducible  testing  of  THEOREM :  PROOF : partitioned  Since  The g r a p h . K  i n t o two s e t s  X  m  the v e r t i c e s o f m+n  a s u b g r a p h on e a c h . s e t ,  where J i s its  an m x n . m a t r i x  -| i s  completely  completely  of the graph G = vertices  reducible  is  reducible.  X K-j ^ c a n  n  such t h a t  the b i p a r t i t e m a t r i x  of cartesian  correspondence  n  , is  given  i n one s u b g r a p h  exactly  2  is  have  given  vertices is  n  Consequently, entry  by  if  of  b i p a r t i t e matrices  E nK-j -j a n d t h u s G i s  (v-,,v ) 2  e E(G)  by  Hence G i s  ^  0  X  0  x  one-one  .  Hence  X^ and X  completely  2  have  their  bipartite  reducible.  •), v  1 1  the  and t h e r e f o r e G^ = mK-| -|  subgraphs K^,^  f o r v-, e V d ^ ,  2  in  each  I n t e r p r e t i n g 3C-| 2  and X  2  the  a n  two g r a p h s G.|, G , X^  x  T  2J  o f each subgraph  the m a t r i c e s  J  1  reducible  Now by  i n e a c h row a n d c o l u m n .  L e t G be a g r a p h w i t h d i s j o i n t that  one.  be  defined  a d j a c e n t t o e x a c t l y one v e r t e x  the b i p a r t i t e matrices  complements a n d G"  .  one n o n - z e r o as  2  n  entries  product of graphs, there e x i s t s  between the  o t h e r subgraph  and X  with a l l  b i p a r t i t e complement  definition  vertex  trees.  algorithm  J  since  two  graphs.•  3.1  as  1.10  for  2  and K^,^,  e V(K , m  v, then  n  *  such (vpV^  30  and ( v . , v ) i E ( G ) f o r j j * 1, i f 2 . 2  Assume m^ ^ n ^ , m  <j n  2  a n d m-| * m .  2  o f t h e g r a p h G so c o n s t r u c t e d  (m xn ) 1  has  the form  J  1 |(m xn ) 2  1  xn  The b i p a r t i t e c o m p l e m e n t G = G ^ U G 2  has  bipartite  o f X^ and X G  2  are  matrix X .  2  w h e r e G-j has  none o r e x a c t l y one n o n - z e r o  c o m p l e t e l y r e d u c i b l e and t h e r e f o r e  These r e s u l t s 3.2  are generalized  THEOREM ;  partitioned  sets  of points PROOF :  previously  is  Then G i s  of G consisting  completely  Since  all  such g r a p h s have  •  and  i n the  following  THEOREM:  has  a complete  can  be  bipartite  reducible  edges between the  if  and  two  a b i p a r t i t e matrix  as  :  J  (m xn )  particular cut-set  Hence G-j  (m-ixn-,)  9  1  column  reducible.  (m-,xn ) ]  2  row a n d  Xp  G.  completely  of a l l  d e f i n e d t o be o f t h e f o r m  X  is  such t h a t each s e t  s u b g r a p h o f G d e f i n e d on i t . i f the c u t - s e t  element.  so  further  each  L e t G be a b i p a r t i t e g r a p h whose v e r t i c e s  i n t o two s e t s  only  b i p a r t i t e matrix  Now by c o n s t r u c t i o n  2  has  2  1  x| 2 l> m  G  :  (mixn,)  2  2  Then t h e b i p a r t i t e m a t r i x  2  ,  (m xn-|)  2  2  r e f e r r e d to corresponds  the  to the b i p a r t i t e  matrix  0 X, a n d by d e f i n i t i o n G i s  completely reducible  is  >  completely  But G j U G  2  r e d u c i b l e i f and o n l y  corresponds  t o the c u t - s e t  i f G-|UG of  G.  i f and o n l y 2  is  i f G =G^UG  completely  2  reducible,  31  The e x i s t e n c e is  of completely  i l l u s t r a t e d by a p r e v i o u s  b i p a r t i t e complement  reducible  example,  graphs not y e t c l a s s i f i e d  t h e graph G  i n f i g . 2 . 7 , whose  2  i s g i v e n by :  G:.=  G contains isolated  3.2  a TYPE 1 t r e e a s a c o m p o n e n t  vertex.  Hence G i s c o m p l e t e l y  t o g e t h e r w i t h an  reducible.  GRAPH R E D U C I B I L I T Y ALGORITHM L e t G ( m , n ) be a b i p a r t i t e g r a p h w i t h m+n v e r t i c e s . of the algorithm  i s t o determine whether G i s completely  and i f s o , t o c o n s t r u c t array  a px3 a r r a y ,  Assume G i s c o n n e c t e d ,  ."  a  r  e  t  n  e  m a  each component  ^  r i  '  x  blocks  corresponding  stage  ©  B ^  and B j  Initially  <&...©  B ^  array  parameter. , B  2  to the b i p a r t i t e matrix  t o be t r e a t e d a t s t a g e s . 1  direct  o f C, and s b e . t h e  B.is. i t s b i p a r t i t e matrix  and B = B | ° ) , £ = B J )  3.3  p ^ m+n, c a l l e d t h e c h a r a c t e r i s t i c  n...) be t h e i t h r o w v e c t o r o f t h e c h a r a c t e r i s t i c  L e t p be t h e r o w . p o i n t e r  ^ks  reducible,  o f the graph.  . L e t . ( i - , .'m., C.  The p u r p o s e  of  set s to 1 j to 1  where © d e v o t e s t h e  sum o f m a t r i c e s - . ;  ALGORITHM 1) there  Calculate  B  (  s  -  1  )  = B^  s  )  + B ^ 2  a r e no r o w s o r c o l u m n s c o n t a i n i n g  s )  +...+  only  B  R  ^ .  J  If  zero e n t r i e s ,  K =l and g  STOP, B n o t  reducible. 2)  If B^ "^ s  has a column w i t h e n t r i e s  i n t h e p t h r o w o f C, i n c r e m e n t  a l l zeros  ^(s-l) p by o n e a n d l e t B v  save  (s,l,o)  be t h e m a t r i x  32  obtained a f t e r deletion of that 3)  If  B  "  v  'has  t h e p t h row o f C ,  a row w i t h e n t r i e s  Repeat  columns  having  5)  If  6)  = J ^  to  Each.row  j  x  n  j ^  d e l e t e B.  Increment  left  m  save s  by 1 a n d i f j  B  procedure  involves  ^ K  sub-blocks  is  terminated i t  successfully  as  not y e t  L e t G be t h e g r a p h  matrix  given 1  1  by 1  : 1  1  1  1 0  °li 0 I 1 0 !  1 0  0  given  by  lji  " 0  0  0  1*1;  0  0  0  1 j  0  1 0  0  C,  unless  5. there are  corresponds  no  stage  is  to a complete  of reduction.  o b t a i n e d by t a k i n g  a graph which Each  stage  is  either  possible  If  to construct  f o r the  1  1 1 0  G  2  given  The the  complete  of reduction  a  the  corresponds algorithm  unique  graph.  i l l u s t r a t e the o p e r a t i o n of the algorithm  example.  = B is  or  i n t h e p t h row o f  completely reduced.  b i p a r t i t e m a t r i x and t h e c o l o u r . g r o u p  '  1,  the sth  o r must b e . f u r t h e r r e d u c e d .  to t r e a t i n g a l l  x  no rows  go t o s t e p  s  t r e a t i n g each component  b i p a r t i t e .complement o f t h e g r a p h  B  contains  (s,m.,h.)  o f the c h a r a c t e r i s t i c a r r a y  We f i r s t  matrix  treat.  subgraph obtained during  is  '  v  s by 1 a n d go t o s t e p  bipartite  bipartite  be t h e  in  '*  J  j  (s,o,l)  entries.  :  7) • I n c r e m e n t blocks  save  row.  2 and 3 u n t i l  only zero  i n c r e m e n t p by 1 ,  zeros s  steps  B , ^  all  i n c r e m e n t p by one and l e t J 3 ^ ~ ^  obtained a f t e r deletion of that 4)  column.  in figure  2.7.  in  Its  an bipartite  33 and c o n t a i n s  a column o f a l l  characteristic given  by  array  :  zeros.  is  (1,0,1).  0  0  1  0  0  1  1  0  1  1  1  0  This matrix s a t i s f i e s  Hence t h e f i r s t e n t r y i n t o  The m o d i f i e d m a t r i x  none o f t h e c o n d i t i o n s  p r o c e e d i n g w i t h s t e p 5,  t h e new m a t r i x  is  in steps  1  1  is  1,2, with  the then  hence blocks  1 . 1  (2)  _  1  1  1  1  0  1  and  Hence t h e s e c o n d e n t r y corresponding bipartite,  so a g a i n  f o l l o w e d by s t e p s and  block [1] of  (2)  by Bg  applying _  _ =  0  0  0  1  [1]  step  (2)  .  F i n a l l y B^  1 we h a v e  0  0  1  0.  to which B ^ ^  is  2  1  1  3  0  1  3  1  0  3  1  0  3  1  1  is  (3,0,1), .  (3,1,1) corresponding  r e d u c e d a f t e r d e l e t i n g rows  Hence t h e c h a r a c t e r i s t i c a r r a y l'  not complete  :  zeros.  0  (?) ' is  (2,1,1)  i n the three e n t r i e s  and f i n a l l y t h e e n t r y  1  v  is  = 0 0  2 and 3 w h i c h r e s u l t  (3,1,0)  1  i n t o the c h a r a c t e r i s t i c array  t o K-j ^ g i v e n  (2) 'BV'-'  (3,1,0)  B.  0  given  by:  and  to  columns  the  34 The o r i g i n a l array  as  follows.  graph  c a n be c o n s t r u c t e d  L e t G-j be t h e g r a p h  from i t s  consisting  f o u r complete b i p a r t i t e graphs obtained at stage  .Let G  2  be t h e u n i o n o f G-| a n d a l l  obtained at stage  Let G  3  Comparison isomorphic given.by  o f Gg w i t h G  the e n t r i e s (s^  rows  Thus  :  complete b i p a r t i t e graphs  and a l l c o m p l e t e b i p a r t i t e graphs  2  in  figure  graph.  1^,;  n  zero i n which  2.7  shows t h a t Gg i s  i n t h e f o l l o w i n g manner as  S-j.  K If  m n  _  corresponds  S ,  + S  m  is  :  indicated previously  whose c o l o u r g r o u p i s case  indeed  The c o l o u r g r o u p o f t h e g r a p h  ,r\^) c o r r e s p o n d s ,  v e r t e x whose c o l o u r g r o u p i s identical  2  i n the array  complete b i p a r t i t e graph o n e o f m.j,n.j i s  3.  the  1 :  to the o r i g i n a l  Each row  o f the union of  2 :  be t h e u n i o n o f G  obtained at stage  characteristic  t o an  to a -  unless  isolated  the c h a r a c t e r i s t i c a r r a y - c o n t a i n s  then the c o l o u r group f o r those  entries  is  given  by  K  35 S [S ; K  + S ,].  m  group  The c o l o u r g r o u p  n  sumof  previous = S .  the groups  example r * ( 6 ^ )  o f t h e graph  i s then given  r e p r e s e n t e d . b y each row. is  S  + [S  ]  +  1  + S  2  by t h e  Thus i n t h e  [S^] + S  1  + [S  1  +  E x a m i n a t i o n o f f i g u r e 2 . 7 shows t h a t an i n t e r c h a n g e o f v e r t i c e s  2  1 and 2 i s t h e o n l y automorphism o f G. .  Since  the c h a r a c t e r i s t i c array  i s independent o f the l a b e l l i n g  o f t h e v e r t i c e s o f G , t h e r e d u c t i o n o f any c o m p l e t e l y r e d u c i b l e bipartite.graph array  isomorphic  t o G must  r e s u l t i n t h e same c h a r a c t e r i s t i c  up t o a r e - o r d e r i n g o f rows d e t e r m i n e d d u r i n g  p r o v i d e d m^n.  this  to those  s^,  I f m=n, a n d two g r a p h s G^(m,m) a n d G ( n , n ) a r e 2  i s o m o r p h i c , and t h e r e e x i s t s 1.2),  t h e same s t a g e  P p P , , such  t h a t P{BJP  2  = B  2  ( s e e LEMMA  i s e q u i v a l e n t t o t h e v e r t i c e s i n G^ b e i n g c o l o u r e d  in G . 2  Hence-an  characteristic array.of G  i n t e r c h a n g e d f columns 2  again y i e l d s  oppositely  2 and 3 o f t h e  a c h a r a c t e r i s t i c array  identical  t o t h a t o f G-j u p . t o a r e - o r d e r i n g o f t h e rows d e t e r m i n e d d u r i n g  each  stage. In array  o r d e r t o u s e ALGORITHM 3 . 3 . t o  c o n s t r u c t a unique c h a r a c t e r i s t i c  f o r each c o m p l e t e l y r e d u c i b l e b i p a r t i t e g r a p h , t h e o r d e r o f  treatment of the blocks  B^ i m  x  n  i^  a t each stage  i s to treat the block  w i t h minimum n^ among a l l " b l o c k s w i t h minimum m. among a l l b l o c k s n o t yet treated.  The rows o f t h e c h a r a c t e r i s t i c a r r a y a r e t h e n i n  o r d e r by n . , m^ a n d f i n a l l y  ascending  s^.  The d e t e r m i n a t i o n o f i s o m o r p h i s m  between c o m p l e t e l y r e d u c i b l e  g r a p h s i s now j u s t a t e s t o f w h e t h e r t h e r e s p e c t i v e c h a r a c t e r i s t i c arrays  a r e i d e n t i c a l . . . The o n l y r e m a i n i n g c a s e t b be c o n s i d e r e d  t h e p o s s i b i l i t y t h a t w i t h m=n, t h e e q u i v a l e n t v e r t e x s e t s graphs under c o n s i d e r a t i o n a r e o f o p p o s i t e c o l o u r . case  f o r tWo. i s o m o r p h i c g r a p h s t h e n P|B|P  ( s e e LEMMA 1 . 2 ) .  2  = B  2  o f two  I f such  f o r some  is  i s the  P-j,P  2  Rather than repeat t h e r e d u c t i o n procedure w i t h  36 B| as  b i p a r t i t e m a t r i x r a t h e r t h a n B^,  second  and t h i r d c o l u m n s  we n e e d o n l y  interchange  of the c h a r a c t e r i s t i c array  g r a p h s , and r e - o r d e r a l l  rows  is  ascending  o r d e r as  o f one o f  the the  previously  described. As an e x a m p l e , we c o n s i d e r a r e - l a b e l l i n g o f t h e g r a p h figure  2.7  G  2  of  :  G :=  Applying  a l g o r i t h m 3.3  (3,0,1),  (3,1,0).  final  entry  is  Comparing labelling  as  before y i e l d s  F i n a l l y the modified matrix is  (3,1,1).  this  The c h a r a c t e r i s t i c a r r a y  m=n,  an i n t e r c h a n g e o f t h e l a s t  rows  in ascending  o r d e r as  0 '  I  hence  i s [1  not i d e n t i c a l .  two columns  previously  the  1  0"  2  1  1  3  0  1  3  0  1  3  1  0  3  1  1  However  original since  and a r e - o r d e r i n g o f  described gives  the  :  -  2  1  1  3  0  1  3  1  0  3  1  0  3  1  1.  which i s  to the c h a r a c t e r i s t i c array F i n a l l y we o b s e r v e results  [1]  c h a r a c t e r i s t i c array with that of the  o f G , we n o t e t h a t i t i s  U  (1,1,0),(2,1,1),(3,0,1),  for determining  identical  f o r the o r i g i n a l  labelling.  t h a t the a l g o r i t h m y i e l d s isomorphism  only  partial  b e t w e e n two a r b i t r a r y b i p a r t i t e  37 graphs.  The a l g o r i t h m behaves thus  1)  I f both G-j and G  :  are c o m p l e t e l y r e d u c i b l e , then they are  2  isomorphic i f and o n l y i f they produce i d e n t i c a l  characteristic  arrays. 2)  I f o n l y one o f G-j and G  are o b v i o u s l y 3)  If.  2  i s c o m p l e t e l y r e d u c i b l e , then they  not i s o m o r p h i c . n e i t h e r G-j nor G  isomorphism problem remains  2  i s c o m p l e t e l y r e d u c i b l e then the  unsolved.  TIMING CONSIDERATIONS The number o f o p e r a t i o n s is  r e q u i r e d . a t each stage o f the a l g o r i t h m  examined i n an e f f o r t to p r o v i d e some e s t i m a t e o f i t s e f f i c i e n c y  f o r comparison with o t h e r m e t h o d s . f o r d e t e r m i n i n g graph  isomorphism.  L e t G(m,n) be the b i p a r t i t e graph under c o n s i d e r a t i o n .  The nature  and number o f e x e c u t i o n s o f each o p e r a t i o n i s : STEP 1 :  s b i p a r t i t e complementations where s i s the stage parameter.  .STEP 2 :  m summations  o f n numbers f o r comparison w i t h  zero.  STEP 3 :  n summations  o f m numbers f o r comparison with  zero.  STEP 4 :  K  s  tests  f o r a complete b i p a r t i t e subgraph,  m.n. comparisons 1  with o n e , where  STEP 5 :  K  STEP 6 :  s incrementations  g  w I  consequently function p-|P  2  £ n. 4 n.  w  1  I f m= £ Pi f o r Pi > 1 ( l < i < k) then ( m - k + T r + y  M  PI.'  2 PROOF :  ^ m,  1  incrementations  LEMMA :  3.4  k-1  z: m.  Ui  1  involving  F o r k=2, m= p^ + p  2 p.]  + p  2  2 is  2 >  2  Then m = p^  maximized by maximizing  f ( x ) = x (m-x) i s m o n o t o n i c a l l y  2 + p  2  = 2p^p and  2 m -2p^p .  increasing  2  2  Now the  f o r o«xsm .  Hence  2  = p-|(m-p^) i s minimized f o r p o s i t i v e i n t e g e r values o f p-j a t p^ = 1  and as a r e s u l t  2  2  m =2p-jp < (m-1) 2  + 1.  38  For > P  k  k > 2 assume w i t h o u t  loss  k £pj  w h e r e t h e p^ m a x i m i z e  of generality '.  ;  If  k 2"^ 2 Then by t h e a b o v e a r g u m e n t z f p.. + taking  P ^ l .  P^y  ' l increases  n  t i m e s we o b t a i n P ^ P ^ - j . =...= This total  lemma a l l o w s  number  3.5  (N-1 ) + 1 »  a  n  P-]  d  occurs  as  :  hence  The number  k-2  required. on  the  graph.  there  where the  i , w i t h the r e s u l t  and K b l o c k s  ...  p^.  and  o f the r e d u c t i o n of a graph  a t each stage  o f s i z e m^ x . m . THEOREM  2  Iterating  n  m-R+1  =  Pi  p -2  t o be t r e a t e d a n d we assume m^ ~ n .  case  one b l o c k  = 1  k £  r e q u i r e d i n STEP 5 t o r e d u c e a  We assume t h a t a t e a c h . s t a g e  possible  > 1 l e t N = p^_-j +  k  the value o f  P2  *  2  f o r t h e c a l c u l a t i o n o f an u p p e r : b o u n d  of comparisons  k=K+l b l o c k s  p  t h a t p-j > p  are  worst  that there  is  of size l x l .  of comparisons  required in  r e d u c t i o n o f a c o m p l e t e b i p a r t i t e m a t r i x by ALGORITHM 3 . 3  the is  at  most  3 of order p  where p i s  PROOF :  Under  (m.. ^ = K) X consists  t h e number o f  the assumption  (m^_.-| -  t h a t a t each stage  of comparisons  matrix with K blocks  required is  Now i f s  stages  elements  t o be t e s t e d , t h e n t h e t o t a l  are required u n t i l  s  is  i  there  less  t h e n by LEMMA  than or equal  there exists  to  3.4  (n^.-K)  number o f c o m p a r i s o n s  p 1  6  £ (m 1"1 - 2K(m) s ( s + l ) + 2 •< K i m p l i e s m < (s+1) K, h e n c e 2  =  iK)  2  1  Ks or  s  Therefore  1  =  m + 3T 3  (2s+l)  IC  6  K  < m < (s+1) < m < K (m.-K)  2  s(s+l)  s+1 2  < m K  3  0(m ). 2  - m  2  (m+1) K  +mK 6  o  .  required  T (m. - K) . I f m.-.l i s p a r t i t i o n e d i n t o p a r t s m . , a n d K i=l ' t h e n m^._-| = m = i K w i t h m=m .. I (m.-K) i=l = nTs  Now-m  an  a block w i t h fewer K  1  ones'  is  K) m a t r i x t o be t r e a t e d whose b i p a r t i t e c o m p l e m e n t  of a block diagonal  t h e number  vertices.  (m+1) K  (2m+l) K  2  39 For non-square blocks of m  i  and n^.  Then  are true f o r m f  a t each s t a g e ,  redefine  (m^.-K)(n^-K) < ( m ^ K )  it  and t h e p r e v i o u s  maximum results  n.  Determination o f the expected value o f since  t o be t h e  involves  K is  extremely  computations w i t h unordered p a r t i t i o n s  e x p e c t e d v a l u e o f K,  E(K),  is  given  difficult  [9].  The  by:  m E(K). =  Z i  Pi(m) PlmT  vl m  =1  Z  i  p.(m)  pW) i=l  w h e r e p(m) d e n o t e s  t h e number o f u n o r d e r e d p a r t i t i o n s o f m; p ^ m ) ,  number o f  unordered p a r t i t i o n s of m i n t o i  E(K)with  m £10  are given  in table  I.  elements.  The v a l u e s  the for  TABLE  I  E(K)  m  p(m)  1  1  1  2  2  1.5  3  3  2  4  5  2.4  5  7  2.86  6  11  3.18  7  15  3.60  8  22  3.72  9  30  3.67  10  42  4.62  The Number and E x p e c t e d V a l u e o f t h e U n o r d e r e d P a r t i t i o n s t h e Numbers  one t o t e n .  of  41 Since there e x i s t s t h a t m-j = m-K, m  2  =...=  o n l y one p a r t i t i o n o f m i n t o K p a r t s m  K  = 1 the p r o b a b i l i t y o f a c h i e v i n g the  upper bound g i v e n i n THEOREM 3.5 i s by  TT p ( m . )  - 1  if  it  is  such  e x c e e d i n g l y s m a l l , being  assumed t h a t any p a r t i t i o n i s  given  equally  1ikely. Under an a l t e r n a t i v e assumption,  t h a t a t stage i the tn^xn. b l o c k  has a b i p a r t i t e complement with b l o c k diagonal equal b l o c k s  form c o n s i s t i n g  of K  o f s i z e m . , . t h e n . t h e number o f blocks t o be d e a l t with i than o r equal to K . K  at stage i i s  less  Hence a f t e r s s t a g e s , s <  l o g ( m ) , the number o f comparisons r e q u i r e d at STEP 5 o f the K  is  < K(m) K = m  2  2  + K (m ) K2 2  2  +...  K (m ) K s  algorithm  2  5  (1 + 1 + . . . + 1 )  and hence i s  o f order m .  These; r e s u l t s  compare f a v o r a b l y with the more general  algorithm  2 o f C o r n e i l who showed t h a t . i t s 5  t i m i n g was u s u a l l y  of order p  3 to p  with an upper bound o f p , p being the number o f v e r t i c e s o f the graph [4].  42 SUMMARY  The value o f any s o l u t i o n  to the isomorphism problem i s  upon the c o n s t r u c t i o n o f a unique r e p r e s e n t a t i o n o f a g r a p h , of v e r t e x or edge l a b e l l i n g , thesis  dependent  independent  i n a r e a s o n a b l y e f f i c i e n t manner.  This  has p r o v i d e d such a r e p r e s e n t a t i o n f o r the c o m p l e t e l y r e d u c i b l e  b i p a r t i t e graphs,.with being 0(n  ), where n i s  the time r e q u i r e d f o r computing such a r e p r e s e n t a t i o n the o r d e r of the graph.  In a d d i t i o n t h i s  represent-  a t i o n has been shown to have the p r o p e r t y t h a t the c o l o u r group o f the graph may be e a s i l y  c o n s t r u c t e d from i t .  C r i t e r i a f o r the e x i s t e n c e o f r e d u c i b l e b i p a r t i t e graphs have a l s o been e s t a b l i s h e d . radius  l e s s than  In p a r t i c u l a r i s  the f a c t t h a t a l l  r e d u c i b l e graphs have  four.  Although  the method i s . a . u s e f u l  o f two graphs i n q u e s t i o n . i s  procedure only when a t l e a s t  c o m p l e t e l y r e d u c i b l e , the importance o f  decomposition procedures f o r use as a t e c h n i q u e i n the c o n s t r u c t i o n solutions  to the isomorphism.problem  is  c l e a r l y emphasized.  one  finding of  BIBLIOGRAPHY  B.,  43  1.  Baumslag,  2.  B e r g e , C , The T h e o r y o f G r a p h s London, Methnen,~T962.  3.  Busacker, R.G., J . L . Saaty, M c G r a w - H i l l , 1964.  4.  C o r n e i l , D.G., 1968.  5.  C o r n e i l , D.G., C C . G o t l i e b , "An E f f i c i e n t A l g o r i t h m f o r Graph I s o m o r p h i s m " , J . ACM 1 7 ( 1 9 7 0 ) , p p . 5 1 - 6 4 .  6.  Chao, C , pp.  7.  Erdtts, P., J.W. Moon,."On Subgraphs o f the Complete B i p a r t i t e SIAM J . A p p l . M a t h . , 1 6 ( 1 9 6 8 ) p p * 4 0 8 - 4 1 6 ,  8.  F r u c h t , R., " H e r s t e l l u n g von G r a p h e n m i t v o r g e g e b e n e r G r u p p e " , C o m p o s i t i o M a t h . , (1938) pp. 239-250.  9.  G u p t a , R.,  Hall  11.  Harary,  and i t s A p p l i c a t i o n s , A .  F i n i t e Graphs  Graph Isomorphism,  "On G r o u p s 488-497.  Symp. 10.  B. C h a n d l e r , G r o u p T h e o r y , New Y o r k , M c G r a w - H i l l , 1 9 6 8 .  University of  Am. M a t h . S o c . ,  (1966) pp.  E.  Proc.  135-136. 1967.  P a l m e r , " T h e S m a l l e s t G r a p h whose G r o u p i s  Czech. Math. J r . , 16(91)(1966) pp.  Cyclic",  70-71.  12.  Harary,  13.  H a r a r y , F.,  14.  H a r a r y , F . , . ( e d . ) , P r o o f T e c h n i q u e s i n G r a p h T h e o r y , New Y o r k , Academic P r e s s , 1969. H a r a r y , F . , E. P a l m e r , R.C. R e a d , " T h e Number o f Ways t o L a b e l a G r a p h " , P s y c h o m e t r i k a , 32(1967) pp. 155-156.  15.  F.  Graph",  abstrakter  J r . , M . , C o m b i n a t o r i a l T h e o r y , New Y o r k , B l a i s d e l l , F.,  Toronto,  118(1965)  "A D e c o m p o s i t i o n Theorem f o r B i p a r t i t e G r a p h s " , Rome,  (trans.),  a n d N e t w o r k s , New Y o r k ,  Ph.D. T h e s i s ,  and G r a p h s " , T r a n s .  Doig  ( e d . ) , S e m i h a r on G r a p h T h e o r y , New Y o r k , H o l t , Graph Theory,  New Y o r k , A d d i s o n - W e s l e y ,  1967.  1969.  16.  I z b i c k i , H., " U n e n d l i c h e Graphen e n d l i c h e n Grades m i t vorgegebenen E i g e n s h a f t e n " , M o n a t s h . M a t h . , 6 3 ( 1 9 5 9 ) p p . 298-301 .  17.  J o h n s o n D., A . D u l m a g e , N. M e n d e l s o h n , " C o n n e c t i v i t y and R e d u c i b i l i t y of Graphs", Canad. J . M a t h . , 14(1962) pp. 529-539.  18.  Kagno, I . N . , " L i n e a r Graphs o f Degree < 6 and t h e i r G r o u p s " , Amer. J . M a t h . , 6 8 ( 1 9 4 6 ) p p . 5 0 5 - 5 2 0 , 6 9 ( 1 9 4 7 ) p. 8 7 2 , 7 7 ( 1 9 5 5 ) p. 3 9 2 .  19.  Ledemann.W., I n t r o d u c t i o n t o .the T h e o r y o f F i n i t e G r o u p s , O l i v e r and Boyd, 1949.  20.  Mowshowitz, A . ,  London,  E n t r o p y a n d t h e C o m p l e x i t y o f G r a p h s , C0NC0MP T e c h n i c a l  Report, University of Michigan,  1967.  21.  P d s a , L., "A Theorem C o n c e r n i n g H a m i l t o n L i n e s " , Magyar Kutato I n t . K d z U , 7(19620, pp. 225-226.  Tud. A l a d .  Mat.  22.  S a b i d u s s i , G . , " G r a p h s w i t h G i v e n G r o u p and G i v e n G r a p h T h e o r e t i c a l P r o p e r t i e s " , . C a n a d . J . M a t h . , 9(1957) pp. 515-525.  23.  S a b i d u s s i , G . , "On t h e Minimum O r d e r o f G r a p h s w i t h G r o u p " , Monatsh. M a t h . , 63(1959) pp. 124-127.  24.  S h i r a k a w a I., H; T a k a h a s k i , "On t h e P l a n a r D e c o m p o s i t i o n o f a C o m p l e t e B i p a r t i t e G r a p h " , SIAM J . A p p l . M a t h . , 1 6 ( 1 9 6 8 ) p p . 4 0 8 - 4 1 6 .  Given.Automorphism  

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-0051347/manifest

Comment

Related Items