4
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2016 at 15:37
  • $\begingroup$ I have edited my answer to fix this mistake. $\endgroup$ Sep 12, 2016 at 1:33

Your Answer

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

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