7
$\begingroup$

The simple connected graph $G$ has $n$ vertices and we have:

1) $|E(G)|‎\geq‎ \frac{n(n-1)}{3}$

2) we have the spectrum and degree sequence of $G$

3) $Spectrum(G)=Spectrum(H)$

Is $G \cong ‎H$?

$\endgroup$
1
  • $\begingroup$ due to 1), it's not what you want, but it's stronger than 3), so maybe is of some interest to you: mathoverflow.net/questions/52169/adjacency-matrices-of-graphs (You could maybe try to modify this example by adding additional edges in one of the graphs and see whether "they are mapped to edges" in the other graph by the provided matrix...) $\endgroup$ Dec 15, 2011 at 0:26

2 Answers 2

4
$\begingroup$

No. $H$ is isomorphic to $G$ if and only if the same is true of their complements. The complements of $G$ and $H$ are required to be mildly sparse graphs (certainly $k$-regular for any $k$ is fine, as long as $n$ is reasonably large), and one can certainly find $k$ regular isospectral non-isomorphic graphs.

EDIT To find such families, google "isospectral cubic graphs". Some of the things which come up are NOT cubic (e.g., the paper Isospectral Cayley graphs of some finite simple groups by Lubotzky, Samuels, Vishne gets examples for almost all degrees.)

$\endgroup$
3
  • $\begingroup$ Dear Rivin Do you have an example or an algorithm for constructing such graphs? Thanks $\endgroup$
    – Shahrooz
    Dec 14, 2011 at 19:49
  • $\begingroup$ @shahrooz: see the edit. $\endgroup$
    – Igor Rivin
    Dec 14, 2011 at 20:50
  • $\begingroup$ The Google search just returns your question to me... $\endgroup$
    – draks ...
    Apr 30, 2015 at 22:26
2
$\begingroup$

Connected strongly regular graphs with parameters $(v,k,\lambda)$ have eigenvalue $k$ appearing once and two other eigenvalues with prescribed multiplicity. In general there are many non-isomorphic graphs for a fixed parameter. There are two graphs with parameters $(16,6,2)$ and 15 with parameters $(25,12,5)$. The number of non isomorphic graphs can grow dramatically....

All strongly regular graphs with parameter $(v,k,\lambda)$ are regular (so the degree sequence is obvious) and are cospectral. Either the graph or its complement meets your bound on the number of edges.

Andries Brouwer maintains a nice webpage on strongly regular graphs here. (Check out the number of $(36,15,6)$ strongly regular graphs!)

$\endgroup$
1
  • $\begingroup$ Thank you very much dear Smith. Your guidance was very helpful. $\endgroup$
    – Shahrooz
    Dec 16, 2011 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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