Cospectral graphs are graphs having same eigenvalues. Constructions of cospectral graph is an interesting question in graph theory. Now a days we use graph theory in different brunches of Sciences and Technology. I am looking for some applications of the idea of cospectral graph. Please provide some examples with references.
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ I very much enjoy brunches of all types, but perhaps if you indicate what aspects of cospectrality you have already investigated, your question might be easier to answer. $\endgroup$– Gordon RoyleSep 17, 2015 at 11:43
-
$\begingroup$ I have a taken a brief literature survey on the construction of adjacency, Laplacian and signless Laplacian cospectral graphs. $\endgroup$– SupriyoSep 17, 2015 at 16:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
I'll add some thoughts partially in response to Igor's answer, in that while I agree that cospectral graphs are intrinsically interesting, I think there is a bit more to it than that.
Many authors (including mathematicians, chemists, physicists) over many years have tried to develop complete graph invariants that can be computed in polynomial time, but a good fraction of these turn out to be spectral invariants in disguise (with respect to some matrix or other). So then cospectral graphs are useful counterexamples.
(These papers often proceed along the lines: here's an invariant obtained by counting walks or something similar in some complicated way. I tried it on lots of small graphs and it works, so I conjecture it always works. A few non-isomorphic strongly regular graphs with the same parameters will often usefully stress test these algorithms.)
More generally, there is the question of how much, and what, information about a graph can be deduced from its spectrum. Cospectral graphs tell you what can't - for example, number of edges can be deduced, but degree sequence can't.
answered Sep 18, 2015 at 13:54
-
1$\begingroup$ I was going to say something similar, but it somehow did not seem like an "application". As you say, the obvious application is to give yet another indication for why graph isomorphism is hard... $\endgroup$ Sep 18, 2015 at 16:34
-
1$\begingroup$ I don't know if this qualifies as an application, but there is a nice connection between Kelly-Ulam reconstruction conjecture and cospectral graphs. This is mentioned in Brouwer and Haemers book. The Kelly-Ulam conjecture states that a graph can be reconstructed from the deck of vertex-deleted subgraphs and it is open. Tutte proved that the characteristic polynomial can be reconstructed from the characteristic polynomials of the vertex-deleted subgraphs. Thus, if Kelly-Ulam conjecture is false, the counterexamples would be have to be cospectral. $\endgroup$ Sep 29, 2015 at 23:03
$\begingroup$
$\endgroup$
Well, this paper: ISOSPECTRAL GRAPHS AND MOLECULES W. C. HERNDON* and M. L. ELLZEY, JR. (in Tetrahedron) describes some applications of isospectrality in chemistry; this seems to be the main application area (google application of isospectral graphs).
That said, I think mostly isospectral graphs are interesting for their own sake.
answered Sep 18, 2015 at 11:13