Skip to main content
1 of 2
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

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(B)| +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$.

Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61