Reconfiguration graphs of zero forcing sets
share
This paper begins the study of reconfiguration of zero forcing sets, and more specifically, the zero forcing graph. Given a base graph G, its zero forcing graph, 𝒵(G), is the graph whose vertices are the minimum zero forcing sets of G with an edge between vertices B and B' of 𝒵(G) if and only if B can be obtained from B' by changing a single vertex of G. It is shown that the zero forcing graph of a forest is connected, but that many zero forcing graphs are disconnected. We characterize the base graphs whose zero forcing graphs are either a path or the complete graph, and show that the star cannot be a zero forcing graph. We show that computing 𝒵(G) takes 2^Θ(n) operations in the worst case for a graph G of order n.
READ FULL TEXT