کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6415992 | 1631086 | 2016 | 24 صفحه PDF | دانلود رایگان |
Given a graph G and an initial designation of each vertex in 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). In this paper, we introduce and investigate a new parameter, the failed skew zero forcing number 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) is undefined for certain graphs: we classify such graphs. We provide an algorithm that determines if Fâ(G) is undefined, and also finds the unique perfect matching guaranteed in the case Fâ(G) is undefined. We provide classifications of graphs with high and low values of Fâ(G), compare the parameter to other zero forcing parameters, and finally, establish 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) and these minimum rank problems. We also classify all graphs such that any set of vertices of order Zâ(G) is a skew zero forcing set.
Journal: Linear Algebra and its Applications - Volume 509, 15 November 2016, Pages 40-63