5
$\begingroup$

Is there a repository of cospectral non-isomorphic graphs available somewhere?

I am looking for list of $0/1$ adjacency matrix pairs that can be input data in tools such as MATLAB.

$\endgroup$
4
  • $\begingroup$ Sage can generate all graphs on a given set of vertices which are cospectral with a given adjacency matrix. See mvngu.googlecode.com/hg/onepage/sage/graphs/graph_generators/… $\endgroup$ – Tony Huynh Dec 19 '15 at 8:54
  • $\begingroup$ @TonyHuynh is there matlab code? $\endgroup$ – 1.. Dec 19 '15 at 8:56
  • $\begingroup$ Sorry, I don't use Matlab, so I don't know. $\endgroup$ – Tony Huynh Dec 19 '15 at 9:07
  • $\begingroup$ @TonyHuynh Cospectral to given graph looks interesting. From the documentation it is not clear to me how to do this. Would you please give example? Is it efficient or just enumerates graphs?. $\endgroup$ – joro Dec 19 '15 at 9:32
6
$\begingroup$

The simplest source of cospectral graphs is lists of strongly regular graphs, lots of which are easily available from Ted Spence's web page at http://www.maths.gla.ac.uk/~es/srgraphs.php.

Otherwise you can use Sage to generate small graphs (up to 10 or so vertices) and then filter out cospectral pairs or groups. I expect the built in Sage function for cospectral pairs just wraps this up.

I don't know what you are doing with them, but I'd probably recommend choosing the computational tool based on what you need, rather than specifying Matlab in advance. If you're working with 64 vertex graphs you'll need full symbolic computation with arbitrary length integers and you'll want to avoid, or be very very careful, in finding eigenvalues numerically.

$\endgroup$
6
  • $\begingroup$ I cant make out from page whether cospectral lists are non-isomorphic (I am assuming they are) can i take them to be non-isomorphic cospectral sets? $\endgroup$ – 1.. Dec 19 '15 at 10:45
  • $\begingroup$ Ted Spence's lists are of pairwise non-isomorphic graphs. $\endgroup$ – Gordon Royle Dec 19 '15 at 12:31
  • $\begingroup$ every strongly regular graph of same size is cospectral? $\endgroup$ – 1.. Dec 19 '15 at 22:28
  • 1
    $\begingroup$ @Turbo - every strongly regular graph with the same parameters is cospectral. See en.m.wikipedia.org/wiki/Strongly_regular_graph for precise definition of parameters. $\endgroup$ – Gordon Royle Dec 20 '15 at 0:28
  • $\begingroup$ are these the hardest examples to test for isomorphism and non-isomorphism? $\endgroup$ – 1.. Dec 20 '15 at 1:02
2
$\begingroup$

You can do this in sage for small order and then export the adjacency matrices to say text file friendly to Matlab and then parse in Matlab.

Tony Huynh suggests one approach. Another approach is to enumerate with McKay's nauty in sage in keep track of cospectral.

Such database will be large:

https://oeis.org/A082104

A082104 Number of distinct characteristic polynomials among all simple undirected graphs on n nodes. 1, 2, 4, 11, 33, 151, 988, 11453, 247357, 10608128, 901029366, 148187993520

Check the references in OIES.

From Brouwer's reference:

https://www.win.tue.nl/~aeb/graphs/cospectral/cospectralA.html Numbers of characteristic polynomials and cospectral graphs

Consider contacting Brouwer, though the full database will take a lot of space AFAICT.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.