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.

  • $\begingroup$ Roberson I have a confusion here.In this product we should have $mn$ eigenvalues with multiplicity. But with your computation we'll have $m+nm=m(n+1)$. What is the reason? Can you clear that for me? Vahid $\endgroup$ – user91523 Sep 10 '16 at 15:37
  • $\begingroup$ I have edited my answer to fix this mistake. $\endgroup$ – David Roberson Sep 12 '16 at 1:33

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.