Graph Isomorphism Problem: Diophantine Algebraic Matrix Riccati, Sylvester Equations

EasyChair Preprint 15278

Abstract

 Graph  isomorphism  problem  has  been  attempted  by  various  researchers.  One of the earlier  researchers  related  the  problem  to  solution  of  structured  Diophantine  matrix  Riccati  equation  as  well  as  structured  Sylvester equation  [17].  He  provided  several  necessary  conditions  for  isomorphism  of  graphs  and  also  a  necessary  and  sufficient condition. We  progress  those  promising  approaches  and  provide  a  polynomial  time  algorithm  to  verify  one  of  the  strong  necessary  conditions.  Thus,  the  algorithms  provide correct  decision  when  the  input  graphs  are  non-isomorphic. The  hope  is  that  connections  to  algebraic  matrix  Riccati  equations ( and  their  well  known  solution  methods )  could  provide  new  approaches  to  solve  the  associated  matrix  Diophantine  equations ( including  the  { 0, 1 }  matrix  solutions ). Also,  results  related  to  Sylvester  equation and  matrix  Non-Symmetric  Algebraic  Riccati  equation,NARE ( including  the  case  where  the  unknown  matrix  is  orthogonal ) are  derived.

Keyphrases: Algebraic Matrix Riccati Equation, Cosprectral Graphs, Sylvester equation, isomorphic graphs

@booklet{EasyChair:15278,
  author    = {Rama Murthy Garimella},
  title     = {Graph Isomorphism Problem: Diophantine Algebraic  Matrix  Riccati, Sylvester  Equations},
  howpublished = {EasyChair Preprint 15278},
  year      = {EasyChair, 2024}}