Having the same spectrum for the adjacency matrix is a Necessary but not sufficient condition for Graph Isomorphism, our recent algorithmic result states a conjecture that every graph is characterized by its Family of Spectra, rather than Spectrum itself.
I have been doing some work on efficient algorithms for generating PINGS (Pair of Isospectral and Non-Isomorphic Graphs), I wrote a program which can search for PINGS in a very efficient manner, I found some interesting results there are no PINGS for n=2,3,4 for n=5 we have one PING (see the picture) it happens that its the only PING for n=5 it has a symmetric spectrum of {-2,0,0,2}. Also I found a very interesting result that there cannot be more than two INGS(Iso-Spectral and non-isomorphic graphs) which share the same spectrum so if INGS exists they exist as PINGS, I was curious if they exist something like XINGS X=P or T or ... but it happens its just P (only a pair). There are 5 PINGS for n=6 for n=7 there are 55 PINGS see the list at http://trinity.engr.uconn.edu/~vamsik/n.7.
No comments:
Post a Comment