MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
The composition $G=G_1[G_2]$ of graphs $G_1$ and $G_2$ with disjoint point sets $V_1$ and $V_2$ and edge sets $X_1$ and $X_2$ is the graph with point vertex $V_1×V_2$ and $u=(u_1,u_2)$ adjacent with $v=(v_1,v_2)$ whenever $u_1$ is adjacent to $ v_1$ or $[u_1=v_1]$ and $u_2$ is adjacent to $v_2$.
Does anyone know what the spectrum of this graph is related to eigenvalues of $G_1$ and $G_2$?
The adjacency matrix of the product is $A_1 \otimes J + I \otimes A_2$, where $J$ is the all ones matrix of size $n = |V(G_2)|$ and $I$ is the identity matrix of size $m = |V(G_1)|$. The two matrices in the sum commute if and only if $G_2$ is regular, and in this case you can compute the eigenvalues of $G_1[G_2]$ easily. In particular, if $\lambda_1 \ge \ldots \ge \lambda_m$ and $\mu_1 \ge \ldots \ge \mu_n$ are the eigenvalues of $G_1$ and $G_2$ respectively, then whenever $G_2$ is regular the eigenvalues of $G_1[G_2]$ are $\lambda_in + \mu_1$ for all $i \in [m]$ and $\mu_j$ with multiplicity $m$ for all $j \in [n]\setminus \{1\}$. Note that some of the $\mu_j$'s may be repeated so their actual multiplicity will be some multiple of $m$.
If $G_2$ is not regular then you are probably going to have harder time writing the eigenvalues of the product in terms of the eigenvalues of the factors.
