论文标题
零强迫集的重新配置图
Reconfiguration graphs of zero forcing sets
论文作者
论文摘要
本文开始研究强迫集的重新配置，更具体地说是零强迫图。给定的基本图$ g $，其零强迫图，$ \ mathscr {z}（g）$是该图，其顶点是$ g $的最小零强迫集，在顶点$ b $ b $ b $和$ b'$ of $ b $ b $ of $ \ nathscr {z}（z}（g）$ if $ b $ b $ b $ b $ b $ b $ b $ a $ b $ a $ b'a $ b'a $ b'a $ b'a $ b'a $ b'a $ b'a $ b'congects的范围a $ b'per。结果表明，森林的零强迫图是连接的，但是许多零强迫图被断开连接。我们表征其零强制图是路径或完整图的基本图，并表明恒星不能为零强迫图。我们表明，计算$ \ MATHSCR {z}（g）$在最坏情况下，$ 2^{θ（n）} $操作，对于$ n $的Gragr $ g $。
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, $\mathscr{Z}(G)$, is the graph whose vertices are the minimum zero forcing sets of $G$ with an edge between vertices $B$ and $B'$ of $\mathscr{Z}(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 $\mathscr{Z}(G)$ takes $2^{Θ(n)}$ operations in the worst case for a graph $G$ of order $n$.
