Failed skew zero forcing on a graph

详细信息    查看全文

• 作者：Thomas Ansill^a ; ^{tba6700@rit.edu" class="auth_mail" title="E-mail the corresponding author} ; Bonnie Jacob^b ; ^{bcjntm@rit.edu" class="auth_mail" title="E-mail the corresponding author} ; Jaime Penzellna^a ; ^{jnp5028@rit.edu" class="auth_mail" title="E-mail the corresponding author} ; Daniel Saavedra^a ; ^{dns6040@rit.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C50
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 November 2016
• 年：2016
• 卷：509
• 期：Complete
• 页码：40-63
• 全文大小：545 K

文摘

Given a graph G   and an initial designation of each vertex in V(G)$V(G)$ as “filled” or “empty,” we apply the skew color change rule, which states that a vertex v becomes filled if and only if it is the unique empty neighbor of some other vertex in the graph. If repeated application of the color change rule results in all vertices in the graph eventually being filled, then the initial set of filled vertices is a skew zero forcing set. The minimum cardinality of such a set is the skew zero forcing number of G  , Z⁻(G)${\mathrm{Z}}^{-}(G)$. In this paper, we introduce and investigate a new parameter, the failed skew zero forcing number  F⁻(G)${\mathrm{F}}^{-}(G)$, which is the maximum cardinality of a starting set that will not result in all vertices in the graph eventually being filled.

It turns out that F⁻(G)${\mathrm{F}}^{-}(G)$ is undefined for certain graphs: we classify such graphs. We provide an algorithm that determines if F⁻(G)${\mathrm{F}}^{-}(G)$ is undefined, and also finds the unique perfect matching guaranteed in the case F⁻(G)${\mathrm{F}}^{-}(G)$ is undefined. We provide classifications of graphs with high and low values of F⁻(G)${\mathrm{F}}^{-}(G)$, compare the parameter to other zero forcing parameters, and finally, establish F⁻(G)${\mathrm{F}}^{-}(G)$ for multiple graph families.

The skew zero forcing number was originally introduced for its application to the problem of finding the minimum rank among all skew-symmetric matrices associated with a graph, and it also applies to the problem among all symmetric matrices with zero diagonal. We establish connections between F⁻(G)${\mathrm{F}}^{-}(G)$ and these minimum rank problems. We also classify all graphs such that any set of vertices of order Z⁻(G)${\mathrm{Z}}^{-}(G)$ is a skew zero forcing set.