Efficient Algorithm for Graph Isomorphism Problem

EasyChair Preprint no. 798, version history

VersionDatePagesVersion notes
1March 1, 20194
2November 16, 20196
  1. The  results are formalized with statement of 4 other lemmas.
  2. Minor corrections are incorporated
3January 15, 20208

(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

4January 31, 202010

(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

5March 2, 202013

(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

6May 29, 20227

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

7September 9, 20227

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

8October 6, 202310

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

9October 23, 202311

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

10November 19, 202311

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

Keyphrases: eigenvalues, Eigenvectors, isomorphic graphs, Permutation Matrices, spectral representation

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@Booklet{EasyChair:798,
  author = {Rama Murthy Garimella},
  title = {Efficient  Algorithm  for  Graph  Isomorphism  Problem},
  howpublished = {EasyChair Preprint no. 798},

  year = {EasyChair, 2023}}