Reconfiguration graphs of zero forcing sets

DOI10.1016/J.DAM.2023.01.027arXiv2009.00220MaRDI QIDQ6348133FDOQ6348133

Authors: Jesse Geneson, Ruth Haas, Leslie Hogben 

Publication date: 1 September 2020

Abstract: 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, $mathscrZ(G)$, is the graph whose vertices are the minimum zero forcing sets of $G$ with an edge between vertices $B$ and $B^{\prime }$ of $mathscrZ(G)$ if and only if $B$ can be obtained from $B^{\prime }$ 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 $mathscrZ(G)$ takes $2^{Theta(n)}$ operations in the worst case for a graph $G$ of order $n$.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

This page was built for publication: Reconfiguration graphs of zero forcing sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348133)