6
$\begingroup$

Two graphs are said to be cospectral if they have same eigenvalues wrt adjacency matrix, Normalised or Signless laplacian matrix. How many graphs has cospectral mates for a given number of nodes? We know answer to this question when number of nodes is less than $12$. I did not see any research paper till now where author has shown any algorithmic approach to compute those statistics. Either it is too simple to say or they do not wish to disclose it.

For a given number of nodes I like to compute number of graphs with at least one cospectral mate. Is there any algorithmic way to do so? If available please give me some references.

Thank you for your help.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

This appears an open problem according to a paper.

In connection with the graph isomorphism problem, it is of interest what fraction of all graphs is uniquely determined by its spectrum. Haemers onjectures that the fraction of graphs on n vertices with a cospectral mate tends to zero as n tends to infinity. Numerical data for n ≤ 9 was given in [2], and for n = 10, 11 in [3]. Here we do n = 12, and also take the opportunity to correct a few earlier values.

OEIS A082104 Number of distinct characteristic polynomials among all simple undirected graphs on n nodes. has some more references.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ It is interesting to note that there are 165 billion graphs on 12 vertices, so the computation is non-trivial. $\endgroup$
    – Gordon Royle
    Commented Jan 13, 2015 at 1:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .