Eigenvalues of the join of two graphs? We define the join of two graphs $G = (V(G),E(G))$, $H=(V(H),E(H))$ as the graph:
$$G \wedge H : = (V(G) \cup V(H), E(G) \cup E(V) \cup \{gh: g \in V(G), h \in V(H))$$
If I know the spectrum of the adjacency matrices of $G$ and $H$, what can I tell about the spectrum of the adjacency matrix of $G \wedge H$?
Any references are appreciated.
 A: There is no simple formula in general.
The join of $G$ and $H$ is the complement of the disjoint union of the
complements of $G$ and $H$. So we are faced with determining the spectrum of the complement of a graph. This is straightforward for regular graphs,
but not otherwise.
I treat the case when $G$ and $H$ are both regular, with degrees $k$ and $\ell$ respectively. Any eigenvector for $G$ (or $H$) that is orthogonal to $\mathbb1$ (the all-ones vector) extends to an eigenvector of the join, with the same eigenvalue. So the characteristic polynomial of the join is divisible by
\[
\frac{\phi(G,t)\phi(H,t)}{(t-k)(t-\ell)}
\]
The two eigenvalues missing have eigenvectors orthogonal to those already found, and therefore these eigenvectors are constant on $V(G)$ and on $V(H)$. Let $m=|V(G)|$ and $n=|V(H)|$.
Assume $u$ is the vector equal to 1 on $V(G)$ and 0 on $V(H)$, and let $v$ be 1 on $V(H)$ and zero on $V(G)$. The span of $u$ and $v$ is invariant under the action of the adjacency matrix of the join and, relative to the basis formed by $u$ and $v$, it is represented by the matrix
\[
\begin{pmatrix}k&n\\ \ell&m\end{pmatrix}
\]
and our two missing eigenvalues are the zeroes of $t^2-(k+\ell)t-mn$.
If $G$ and $H$ are not both regular, there is a formula in terms of the characteristic polynomials of $G$ and $H$, and of their complements. It's possible that this formula is in Cvetkovic, Doob, Sachs ``Spectra of Graphs''.
A: Suppose $A(G)$ and $A(H)$ are the adjacency matrices of orders $m$ and $n$ of the graphs $G$ and $H$ respectivelty Let $J_{m,n}$ be an $m\times n$ all one matrix.
Then the adjacency matrix of the join is given by
$$A(G\wedge H)=\begin{bmatrix} A(G)&J_{m,n}\\J_{n,m}&A(H) \end{bmatrix}$$.
