Eigenvalues of the join of two graphs?

Question

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.

Answer 1

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''.

Answer 2

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}$$.