I was wondering how to relate the spectra of the composition of two graphs in term of the factors...someone can help me?
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$– Joseph O'RourkeCommented Apr 30, 2013 at 0:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
answered Apr 30, 2013 at 1:41
-
$\begingroup$ I'm sorry...what do you mean with the notation V(B)? $\endgroup$– RobCommented Apr 30, 2013 at 10:33
-
$\begingroup$ @Roberto: I meant $V(Y)$, it's fixed now. $\endgroup$ Commented Apr 30, 2013 at 11:47
-
$\begingroup$ exactly...how I thought. Now it makes sence. $\endgroup$– RobCommented May 1, 2013 at 12:16