Notes on the Zero Forcing Algorithm

by ayushkhaitan3437

In this post I will try and understand the gist of the paper Zero Forcing Sets and the Minimum Rank of Graphs by Brualdi.

Let F be a field. The set of symmetric matrices of order n\times n containing entries from F is called S_n(F). The matrix corresponding to a graph is defined in the following way: if there is an edge between edges i and j, then a_{ij}=a_{ji} are non-zero. Clearly, multiple symmetric matrices can correspond to a single graph.

Let \mathfrak{S}(G) be the set of all symmetric matrices in S_n(F) corresponding to a graph G. Then the minimum rank of G, or mr(G), is defined to be \min(\text{rank}(A):A\in\mathfrak{S}(G)). Also, the corank of a matrix is the dimension of its nullity, and its maximum corank is M(G)=\max(\text{corank}(A):A\in\mathfrak{S}(G)). There’s a theorem which states that for a graph G, mr(G)+M(G)=|G|. All this is for the field F.

Here we talk about Zero-forcing sets, and discuss whether this is similar to the game that Pete and I developed. The colour change rule is the following: Let all vertices of a graph G be either white or black. If a white vertex is attached to a black vertex such that it is the only white neighbour of the black vertex, then it too is coloured black. The zero forcing set of G is a minimal set of vertices (may not be unique) such that colouring them black ensures that the whole graph will eventually be coloured black. Is this related to the game that Pete and I developed?

If we can build a graph which becomes all black by one algorithm but not by another, then we can know that they’re not the same.

1. Assume that 3-vertex: white vertex, and 2-vertex: black vertex.

The three squares is a graph that turns black by the zero forcing algorithm, but not our game.

20161020_200707

The diagram given below is an example of a graph which is forces to have zero sections by our game, but not the zero forcing algorithm.

20161020_195730

2. Assume that 3-vertex: black vertex, and 2-vertex: white vertex.

The three squares graph again is an example of a graph that is forced to have zero sections by the zero forcing algorithm, but not our game.

The graph given above is again an example of a graph which is forced to have zero sections by our game, but not the zero forcing algorithm.

Hence, the zero-forcing algorithm does not have much to do with the game that we’ve developed.

Advertisements