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$
1
  • $\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$ Apr 30, 2013 at 0:54

1 Answer 1

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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