On the complexity of failed zero forcing
On the complexity of failed zero forcing
复制标题
论失败的迫零的复杂性
DOI：
10.1016/j.tcs.2016.11.032
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Y. Shitov
中科院分区：
文献类型：
--
作者：
Y. Shitov
设 G 是一个简单图，其顶点被划分为两个子集，称为“填充”顶点和“空”顶点。据说一个顶点被填充的顶点 uifvis 的唯一空邻居 ofu 所强制。如果我们可以通过重复填充强制顶点来填充 G 的所有顶点，那么我们将一组初始的填充顶点称为强制集。我们讨论图的所谓失败强迫数，它是不强迫的集合的最大基数。回答 Ansill、Jacob、Penzellna、Saavedra 最近提出的问题，我们证明这个量是 NP 难计算的。我们的证明也适用于相关的图不变量，称为倾斜失败强迫数。
LetGbe a simple graph whose vertices are partitioned into two subsets, called ‘filled’ vertices and ‘empty’ vertices. A vertexvis said to be forced by a filled vertexuifvis a unique empty neighbor ofu. If we can fill all the vertices ofGby repeatedly filling the forced ones, then we call an initial set of filled vertices a forcing set. We discuss the so-called failed forcing number of a graph, which is the largest cardinality of a set which is not forcing. Answering the recent question of Ansill, Jacob, Penzellna, Saavedra, we prove that this quantity is NP-hard to compute. Our proof also works for a related graph invariant which is called the skew failed forcing number.