3
$\begingroup$
  • On n-vertices, how many isospectral graphs exist?

[..I saw this previous "historic" discussion between two of the stalwarts in this field - Operation on Isospectral graphs ]

  • Given a graph are these ways to generate other graphs from it which have the same spectrum as the first one but will necessarily be non-isomorphic? (...if one considers weighted graphs then are two graphs with different weights but same connectivity considered isomorphic?...)
Improve this question
$\endgroup$
1
  • $\begingroup$ The question is not clear to me. Suppose that, for some $n$, there are 737 graphs, including one set of 3 isospectral graphs, and one set of 4. Would you say there are 2 isospectral graphs? would you say 4? would you say 7? $\endgroup$
    – Gerry Myerson
    Commented Sep 27, 2014 at 6:21

1 Answer 1

Reset to default
5
$\begingroup$

The answer to the first question is unknown. It is even unknown if the fraction of graphs on $n$ vertices determined by their spectra converges to 0, or 1, or something between, or even converges at all.

About the second question, it is not well posed. You have to decide whether you want weighted graphs (in which case you just have symmetric matrices and nearly anything is possible), and you have to decide what is isomorphic for you. You might get some ideas from this paper: C. D. Godsil and B. D. McKay, Constructing cospectral graphs, Aequationes Mathematicae, 25 (1983) 257-268.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Brendon McKay Thanks! Any insights about the second question? I mean - an obvious thing to try is this - say I take the adjacency matrix "A" and then conjugate it by some matrix then I get another matrix which is isospectral to whatever I began with - if I choose the conjugating matrix to be orthogonal then I can possibly ensure that symmetricity of the original matrix is maintained - so it seems one can create another graph isospectral to the original - $\endgroup$
    – user6818
    Commented Sep 27, 2014 at 7:43
  • $\begingroup$ @BrendonMcKay the issue is can I (1) maintain d-regularity and (2) if I restrict to unweighted graphs then can I do something like this (as in always maintain that the adjacency matrices I produce are always 1.0 matrices.) $\endgroup$
    – user6818
    Commented Sep 27, 2014 at 7:44

You must log in to answer this question.

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