Five properties an equivalence relation $\equiv$ on finite simple graphs may have.

It is preserved under disjoint unions if $G \equiv G'$ and $H \equiv H'$ imply $G + H \equiv G' + H'$, and preserved under categorical products if $G \equiv H$ implies $G \times K \equiv H \times K$ for every graph $K$. It is preserved under taking complements if $G \equiv H$ implies $\overline{G} \equiv \overline{H}$; since complementation is an involution and $\equiv$ is symmetric, this one implication already gives the biconditional of the paper.

It is preserved under left lexicographic products if $H \equiv H'$ implies $G \cdot H \equiv G \cdot H'$ for every graph $G$, and preserved under right lexicographic products if $G \equiv G'$ implies $G \cdot H \equiv G' \cdot H$ for every graph $H$.