Efficient Algorithm for Graph Isomorphism Problem

EasyChair Preprint 798, version history

VersionDatePagesVersion notes
1
March 1, 2019
4
2
November 16, 2019
6
  1. The  results are formalized with statement of 4 other lemmas.
  2. Minor corrections are incorporated
3
January 15, 2020
8

(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

4
January 31, 2020
10

(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

5
March 2, 2020
13

(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

6
May 29, 2022
7

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

7
September 9, 2022
7

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

8
October 6, 2023
10

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

9
October 23, 2023
11

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

10
November 19, 2023
11

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: Eigenvectors, Permutation Matrices, eigenvalues, isomorphic graphs, 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 798},
  year      = {EasyChair, 2023}}