Download PDFOpen PDF in browserGraph Isomorphism Problem: Diophantine Algebraic Matrix Riccati, Sylvester EquationsEasyChair Preprint 152787 pages•Date: October 21, 2024AbstractGraph 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
|