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

详细信息    查看全文

• 作者：Jephian C.-H. Lin ^{chlin@iastate.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C50 ; 05C57 ; 05C83 ; 15A03 ; 15A18 ; 15A29
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 October 2016
• 年：2016
• 卷：507
• 期：Complete
• 页码：229-250
• 全文大小：482 K

文摘

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