Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|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. upcommons.upc.edu/handle/2099/10370 –  Joseph O'Rourke Apr 30 '13 at 0:54
add comment

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 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|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
    
exactly...how I thought. Now it makes sence. –  Rob May 1 '13 at 12:16
add comment

Your Answer

 
discard

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.