5
$\begingroup$

Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that are obtained by applying a binary operation to $G$ and $H$? For example, to take one special case, is $G‎\otimes‎G$ (Kronecker product) isospectral? Which binary operations between $G$ and $H$ preserve the isospectrality?

$\endgroup$

3 Answers 3

5
$\begingroup$

If $G_i$ is cospectral to $H_i$ ($i=1,2$), then the direct products, with adjacency matrices $$ A(G_i)\otimes A(G_2),\quad A(H_i)\otimes A(H_2) $$ are cospectral, as are the Cartesian products with adjacency matrices $$ A(G_1)\otimes I + I\otimes A(G_2),\quad A(H_1)\otimes I + I\otimes A(H_2) $$ If $G$ and $H$ are cospectral and regular, their complements are cospectral. It follows that, for regular graphs, the lexicographic product preserves the spectrum. Cvetkovic and his colleagues has a theory of what they refer to as NEPS, which generalizes these observations.

If $G$ and $H$ are cospectral strongly regular graphs and $u\in V(G)$, $v\in V(H)$, then $G\setminus u$ and $H\setminus v$ are cospectral (as are their complements).

There is no hope of any exhaustive answer to this question.

$\endgroup$
3
$\begingroup$

Chris seems to have forgotten that he and I published a generalization of the NEPS in C. D. Godsil and B. D. McKay, Constructing cospectral graphs, Aequationes Mathematicae, 25 (1983) 257-268. This contains some general methods of using the tensor product, as well as some other techniques.

$\endgroup$
4
  • 1
    $\begingroup$ There are three signs of senility. The first sign is that a man forgets his theorems. The second sign is that he forgets to zip up. The third sign is that he forgets to zip down. (Erdos) $\endgroup$ Dec 18, 2011 at 23:31
  • $\begingroup$ Actually, I believe it was Stan Ulam, not Erdos, who said that. $\endgroup$
    – Igor Rivin
    Dec 18, 2011 at 23:44
  • $\begingroup$ See en.wikiquote.org/wiki/Stanislaw_Ulam $\endgroup$
    – Igor Rivin
    Dec 18, 2011 at 23:50
  • $\begingroup$ Perhaps this will remind Chris: homepages.cwi.nl/~mueller/haemers.pdf $\endgroup$
    – Igor Rivin
    Dec 18, 2011 at 23:53
0
$\begingroup$

Since the eigenvalues of the tensor products of two matrices are products of the eigenvalues, the answer to your question would seem to be "yes". More interestingly it would appear that $G\otimes H$ and $H\otimes G$ would be isospectral for any graphs $G, H.$ (where by $G\otimes H$ I mean the graph whose adjacency matrix is the tensor product of those of $G, H.$)

$\endgroup$
2
  • 2
    $\begingroup$ But $G\otimes H$ and $H\otimes G$ are isomorphic, and so their cospectrality is not a surprise. $\endgroup$ Dec 18, 2011 at 22:14
  • $\begingroup$ @Chris: umm, indeed... $\endgroup$
    – Igor Rivin
    Dec 18, 2011 at 22:24

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.