Using a new zero forcing process to guarantee the Strong Arnold Property

Abstract

The maximum nullity $M(G)$ and the Colin de Verdière type parameter $\xi (G)$ both consider the largest possible nullity over matrices in $\mathcal{S}(G)$, which is the family of real symmetric matrices whose $i,j$-entry, $i\ne j$, is nonzero if $i$ is adjacent to $j$, and zero otherwise; however, $\xi (G)$ restricts to those matrices $A$ in $\mathcal{S}(G)$ with the Strong Arnold Property, which means $X=O$ is the only symmetric matrix that satisfies $A\circ X=O$, $I\circ X=O$, and $AX=O$. This paper introduces zero forcing parameters $Z_{\mathrm{SAP}}(G)$ and $Z_{\mathrm{vc}}(G)$, and proves that $Z_{\mathrm{SAP}}(G)=0$ implies every matrix $A\in \mathcal{S}(G)$ has the Strong Arnold Property and that the inequality $M(G)-Z_{\mathrm{vc}}(G)\le \xi (G)$ holds for every graph $G$. Finally, the values of $\xi (G)$ are computed for all graphs up to $7$ vertices, establishing $\xi (G)=\lfloor Z\rfloor (G)$ for these graphs.