| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
07 February 2025 |
|
| | | |
|
Article overview
| |
|
On the complexity of failed zero forcing | Yaroslav Shitov
; | Date: |
1 Sep 2016 | Abstract: | Let $G$ be a simple graph whose vertices are partitioned into two subsets,
called filled vertices and empty vertices. A vertex $v$ is said to be forced by
a filled vertex $u$ if $v$ is a unique empty neighbor of $u$. If we can fill
all the vertices of $G$ by 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. | Source: | arXiv, 1609.0211 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|