# Spectrum of composition of graphs( lexicographic product)

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

• 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 – Joseph O'Rourke Apr 30 '13 at 0:54

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 all-ones 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 $\lambda|V(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$.
• @Roberto: I meant $V(Y)$, it's fixed now. – Chris Godsil Apr 30 '13 at 11:47