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.
$\begingroup$
$\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 HuynhCommented Dec 19, 2015 at 8:54
-
$\begingroup$ @TonyHuynh is there matlab code? $\endgroup$– TurboCommented Dec 19, 2015 at 8:56
-
$\begingroup$ Sorry, I don't use Matlab, so I don't know. $\endgroup$– Tony HuynhCommented Dec 19, 2015 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$– joroCommented Dec 19, 2015 at 9:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
answered Dec 19, 2015 at 10:05
-
$\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$– TurboCommented Dec 19, 2015 at 10:45
-
$\begingroup$ Ted Spence's lists are of pairwise non-isomorphic graphs. $\endgroup$ Commented Dec 19, 2015 at 12:31
-
$\begingroup$ every strongly regular graph of same size is cospectral? $\endgroup$– TurboCommented Dec 19, 2015 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$ Commented Dec 20, 2015 at 0:28
-
$\begingroup$ are these the hardest examples to test for isomorphism and non-isomorphism? $\endgroup$– TurboCommented Dec 20, 2015 at 1:02
$\begingroup$
$\endgroup$
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:
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.
