Skip to main content
MathOverflow

Return to Answer

Added OEIS link
Source Link
joro
joro
  • 25.4k
  • 10
  • 66
  • 121

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.

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.

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.

Source Link
joro
joro
  • 25.4k
  • 10
  • 66
  • 121

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.