I was wondering how to relate the spectra of the composition of two graphs in term of the factors...someone can help me?

$\begingroup$ This paper contains some partial results in this area, and could give some sense of what's known and not known: Romain Boulet. "Spectral behavior of some graph and digraph compositions." 2011. upcommons.upc.edu/handle/2099/10370 $\endgroup$– Joseph O'RourkeCommented Apr 30, 2013 at 0:54
1 Answer
If graphs $X$ and $Y$ have adjacency matrices $A$ and $B$ respectively, then the composition of $X$ around $Y$ has adjacency matrix $$ A\otimes J + I\otimes B $$
Assume $B$ is $k$regular. Then the allones vector $\textbf{1}$ is an eigenvector for $B$ with eigenvalue $k$ and if $x$ is an eigenvector for $A$ with eigenvalue $\lambda$, then $x\otimes\textbf{1}$ is an eigenvector for the composition with eigenvalue $\lambdaV(Y) +k$. If $y$ is an eigenvector for $B$ orthogonal to $\textbf{1}$ with eigenvalue $\mu$, then $x\otimes y$ is an eigenvector for the composition with eigenvalue $\mu$.
If $B$ is not regular then there is no simple expression for the spectrum; it can be shown that it is determined by the spectrum of $X$, $Y$ and the complement of $Y$.

$\begingroup$ I'm sorry...what do you mean with the notation V(B)? $\endgroup$– RobCommented Apr 30, 2013 at 10:33

$\begingroup$ @Roberto: I meant $V(Y)$, it's fixed now. $\endgroup$ Commented Apr 30, 2013 at 11:47

$\begingroup$ exactly...how I thought. Now it makes sence. $\endgroup$– RobCommented May 1, 2013 at 12:16