Zero forcing set of graph $G$ is a subset $Z$ of vertices for which the following holds: if initially the vertices from $Z$ are coloured black and we apply the colour change rule repeatedly, then at the end of the process all vertices of $G$ should be black. Here the colour change rule is defined as: a black vertex $u$ forces the change of colour in a white negihbour $v$, if $v$ is the only white neighbour of $u$. The zero forcing number of a graph is the size of the smallest zero forcing set. In this work, we list and prove results for some well known families of graphs, lower and upper bounds of the zero forcing number and characterise the graphs for which these bounds are tight. Some upper bounds for various products of graphs and connections to other graph parameters, such as domination and independence number, are also given.
We implement algorithms for checking whether a set is zero forcing and for calculating the zero forcing number of a general graph in C++. The latter algorithms are exponential, however due to NP-hardness of the problem, polynomial time complexity (most likely) cannot be obtained. Some additional complexity results for closely related problems are also listed.
|
