MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – 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$.

share|cite|improve this answer
I'm sorry...what do you mean with the notation V(B)? – Rob Apr 30 '13 at 10:33
Thanks a lot for your help anyway. – Rob Apr 30 '13 at 10:33
@Roberto: I meant $V(Y)$, it's fixed now. – Chris Godsil Apr 30 '13 at 11:47 I thought. Now it makes sence. – Rob May 1 '13 at 12:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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