Efficient Algorithm for Graph Isomorphism Problem

1. The  results are formalized with statement of 4 other lemmas.
2. Minor corrections are incorporated

(1)  The  case  of  non-distinct  eigenvalues  of  adjacency  matrix  is  considered  and  new  ideas are  presented

(2)  Several  new  references  are  added

(3)  Computational  Complexity  of  the  algorithm  is  presented  clearly

(1)  Connections  of  the  isomorphism  problem  to  solution  of  Algebraic  Riccati  equation  is  discussed.  Solution  in  a  special  case  is  also  provided

(2)  Sub section  on  GRAPH  SPECTRA  is  also  included

(3)  Some  new  references  are  provided

(1)  A  new  lemma ( lemma 5 )  which  is  crucial  for  the   goodness  of   algorithm  is  proved  and  included

(2)  Some  minor  mistakes  are  corrected

(3)  Acknowledgements  are  updated

Some  results  which  are  not  correct  are  removed.

A  new  algorithm  for  testing  graph  isomorphism  is  provided.

Some  Lemmas  which  are  not  true  are  removed

The  abstract  is  modified  with  necessary  and  sufficient  conditions  for  graph  isomorphism.

Proof  of  Lemma  2  is  made  complete  formally

Lemma  3  is  changed  into  Theorem.  This  theorem  provides  a  proof  of  necessary  and  sufficient  conditions  for  graph  isomorphism

Polynomial  time  algorithm  to  test  isomorphism  of  arbitrary  graphs  (  with  out  any  conditions )  is  proposed.  Some  mistakes  in   the  earlier  versions  are  corrected.  Connections  to   algebraic  Ricatti  equation  are  discussed

1. It  is  proved  that  the  algorithm  meets  a  lower  bound  on  computational  complexity  for  the  graph  isomorphism  problems. New  LEMMA  3  is  added

2. Some  typos  are   corrected

3.  Section  4  is  improved

1.   A  new  lemma  i.e.  LEMMA 3  is  added   which  provides  necessary  and   sufficient  condition   for  graph  isomorphism

2. Using  the  new  Lemma  3,  a  polynomial  time  algorithm  to  check  the   necessary   condition   is  discussed

3. Some  mistakes  in   the  earlier  version  are   corrected