Question on bilinear form of Laplacian matrix for graphs

Question

I'm going through the paper Spectrally robust graph isomorphism by Kolla, Koutis, Madan and Sinop, and am a bit puzzled by the very last paragraph of the second page.

Recall that the Laplacian of a graph $G$ is the matrix $L_G=D-A_G$ where $A_G$ is the adjacency matrix of $G$ and $D$ is the diagonal matrix whose entries are the degrees of the vertices. Suppose $G$ and $H$ have the same vertex set $V$. We say that $G$ dominates $H$ if for all vectors $x\in \mathbb{R}^V$ it holds that $x^tL_Gx\leq x^tL_Hx$.

If I understand correctly, at the end of the second page, the authors claim that it should not be hard to show that if $G$ and $H$ are cospectral and $G$ dominates $H$, then $G$ and $H$ must be isomorphic. How does one show this?

Answer 1

We can identify the eigenvalues and eigenvectors of $L_G$ by the rule:

• $\lambda_1$ is the maximum of $\mathbf x^{\mathsf T}L_G \mathbf x$ over all $\mathbf x$ such that $\|\mathbf x\| = 1$, and the associated eigenvector $\mathbf v_1$ is the vector that achieves that maximum.
• $\lambda_2$ is the maximum of $\mathbf x^{\mathsf T}L_G \mathbf x$ over all $\mathbf x$ such that $\|\mathbf x\| = 1$ and $\mathbf x^{\mathsf T} \mathbf v_1 = 0$, and the associated eigenvector $\mathbf v_2$ is the vector that achieves that maximum.
• $\lambda_3$ is the maximum of $\mathbf x^{\mathsf T}L_G \mathbf x$ over all $\mathbf x$ such that $\|\mathbf x\| = 1$ and $\mathbf x^{\mathsf T} \mathbf v_1 = \mathbf x^{\mathsf T} \mathbf v_2 = 0$, and the associated eigenvector $\mathbf v_3$ is the vector that achieves that maximum.
• And so forth...

Of course, the same also holds for $H$. So we can prove that $L_H$ has the same eigenvectors, one at a time:

• We have $\lambda_1 = (\mathbf v_1)^{\mathsf T} L_G \mathbf v_1 \le (\mathbf v_1)^{\mathsf T} L_H \mathbf v_1 \le \lambda_1$: the $=$ is because $\mathbf v_1$ is an eigenvector of $L_G$, the first $\le$ is because $G$ dominates $H$, and the second $\le$ is because $\lambda_1$ is also the maximum of $\mathbf x^{\mathsf T}L_H \mathbf x$ over all $\mathbf x$ such that $\|\mathbf x\| = 1$. Therefore both $\le$'s are $=$'s, and $\mathbf v_1$ must be the eigenvector of $L_H$ associated to $\lambda_1$.
• By the same argument, we have $\lambda_2 = (\mathbf v_2)^{\mathsf T} L_G \mathbf v_2 \le (\mathbf v_2)^{\mathsf T} L_H \mathbf v_2 \le \lambda_2$. (Crucially, at this point we already know that $\mathbf v_1$ is an eigenvector of $L_H$, and that $(\mathbf v_2)^{\mathsf T} \mathbf v_1 = 0$.) Therefore both $\le$'s are $=$'s, and $\mathbf v_2$ must be the eigenvector of $L_H$ associated to $\lambda_2$.
• And so forth...

Once we know that $L_G$ and $L_H$ have the same eigenvectors, we have $L_G \mathbf x = L_H \mathbf x$ for all $\mathbf x$, because we can just write $\mathbf x$ in the basis of eigenvectors. Therefore $L_G = L_H$, and so $G=H$.

This is stronger than just saying $G$ and $H$ are isomorphic; we do not need to permute the vertex set. If we are given that $G,H$ have the same eigenvalues and $G$ dominates $\pi(H)$ for some permutation $\pi$, as in the paper, then we conclude $G = \pi(H)$, so $G$ is isomorphic to $H$.