1
$\begingroup$

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

$\endgroup$
  • $\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'Rourke Apr 30 '13 at 0:54
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm sorry...what do you mean with the notation V(B)? $\endgroup$ – Rob Apr 30 '13 at 10:33
  • $\begingroup$ @Roberto: I meant $V(Y)$, it's fixed now. $\endgroup$ – Chris Godsil Apr 30 '13 at 11:47
  • $\begingroup$ exactly...how I thought. Now it makes sence. $\endgroup$ – Rob May 1 '13 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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