1. Problem List
-
Problem 1.02.
[Wayne Barret] If $G$ is a graph with $n$ vertices, $m$ edges and diameter $d$ are there functions $f(n,m,d)$ and $g(n,m,d)$ that can serve as lower and upper bounds, respectively, for $Z(G)$? -
Problem 1.04.
Can we find asymptotic results based on density, $\delta = \dfrac{|E|}{ {{n}\choose{2}} }$? See Butler and Young paper (https://ajc.maths.uq.edu.au/pdf/57/ajc_v57_p065.pdf). Note: $Z(G) = n - 0(n)$ for random graph $G(n,p)$. -
Problem 1.06.
[Steve Butler] Does $Z_q$ have a ‘better’ combinatorial version, maybe based on inertia? C.C.R. for $Z_q$: This is a two player game and player $1$ is trying to minimize how much money is spent and player two is trying to maximize how much money is spent.- Normal zero forcing is free for player one.
- It costs player one $1$ dollar to fill a single vertex.
- The graph $G$- (filled vertices) has connected components $F_1,F_2,\dots, F_k$. Player one hands player two $q+1$ components to player two and player two hands at least one connected component back to player one. Now player one can force on the returned components (for free).
-
Problem 1.08.
For $Z_{\infty}(G) = Z(G)$ we know path cover is an bound, for $Z_0(G) = Z_+(G)$ we know tree cover number is a bound for PSD zero forcing, are there related bounds for $Z_1(G)$, $Z_2(G)$, etc.? -
Problem 1.1.
Can we characterize graphs for which $Z_1(G) = 0,1,2$ and/or $Z_1(G) = |G|, |G| -1, |G| - 2$. -
DEFINE $\mu(G)$.
Problem 1.12.
[Jephian C.-H. Lin] Can we design a zero forcing number/color change rule for colin de Verdiere type parameter $\mu(G)$, i.e. can we design $Z_{\mu}(G) \ge \mu(G)$. -
Problem 1.14.
Is there a practical reduction of zero forcing to some known, well studied, NP-problem? -
Problem 1.16.
Is there a good way to compute $Z(G)$ for $G$ planar or outer planar? (See related results for power domination: Jiong Guo, Rolf Biedermeier, 2007, Improved Algorithms and complexity results for power domination in graphs: http://ai2-s2-pdfs.s3.amazonaws.com/978e/7fcaf5d701de467675ac8b9ba83ed6462732.pdf). This might be known if $\Delta(G) \le 3$ since it is NP hard to find the fast-mix number. -
Problem 1.18.
Is the minor-monotone floor version of zero forcing easy (polynomial time) to compute for planar graphs? Probably NP-hard by tree-width relationship. -
Problem 1.2.
Given $\text{Aut}(G)$, what are the number of non-isomorphic zero forcing sets. In particular, what about circulates? This can have implications for propagation time because it is probably true that ‘isomorphic’ zero forcing sets have the same propagation time. -
This is true if $\text{deg}(v) = 1$, $\text{deg}(v) = 2$.
Problem 1.22.
[Michael Young] If $G$ is bipartite, $V = X \cup Y$, $|X| \ge |Y|$ and for all $v\in X$ $\text{deg}(v) = 3$ is $\text{M}(G) = \text{Z}(G)$?
It is important that we have $|X| \ge |Y|$, there is a counterexample on $20$ vertices where the parameters are not equal. -
Problem 1.24.
What about approximate zero forcing? This is a question about quantum mechanical systems where typically neighboring quantum particles interact strongly with each other and quantum particles that are distance two from each other interact weakly with each other and distance three and greater do not interact. More formally, if $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ and $G_1 \subseteq G_2$ . Can we relate $\text{Z}(G_1)$ and $\text{Z}(G_2)$? -
Problem 1.26.
What can we say about probabalistic zero forcing, i.e. edges have weights and if standard zero forcing says we can force we do so with probability of the edge weight. -
Problem 1.28.
[org.aimpl.user:nwarnberg@uwlax.edu] For positive semidefinite (PSD) zero forcing consider the minimum PSD propagation time $\text{pt}_+(G) := \min\{\text{propagation times given a minimum PSD zero forcing set}\}$ and the maximum PSD propagation time $\text{PT}_+(G) := \max\{\text{propagation times given a minimum PSD zero forcing set}\}$. If $\text{pt}_+ (G) \le k \le \text{PT}_+(G)$ is there a minimum PSD zero forcing set with propagation time $k$? This is not true for standard zero forcing, skew zero forcing, directed zero forcing, loop zero forcing or power domination propagation time.-
Remark. [Steve Butler] Maybe the definition of maximum propagation time is wrong, maybe we look at all possible zero forcing sets or maybe we use minimal zero forcing sets. Can we fill the propagation time interval if we increase the set of possible zero forcing sets?
-
-
Problem 1.3.
Investigate the convexity of zero forcing sets by creating a simplicial complex based on the complements of minimal zero forcing sets. Can the geometry of the complex tell us anything about propagation time or finding more minimal zero forcing sets? -
Problem 1.32.
Can we find $G_1, G_2, G_3,\dots $ where $\displaystyle\lim_{i\to \infty} \dfrac{|Z(G_1)|}{|G_i|} = 0$ and $Z(G_i) \ge \dfrac{n}{\log(n)}$. -
Problem 1.34.
[Chassidy Bozeman] Throttling is concerned about the sum of the size of a zero forcing set and the associated propagation time, i.e. we are willing to not use the minimum zero forcing number if it decreases the propagation time, in other words if $B$ is a zero forcing set and $\text{pt}(G,B)$ is the corresponding propagation time then the throttling number is $\min\{|B| + \text{pt}(G,B) \}$. -
Problem 1.36.
What about variations of throttling, like the product of $|B|$ and $\text{pt}(G,B)$? Note that $\ell$-round power domination seems like it is similar to throttling. -
Problem 1.38.
[Illya Hicks] Can we beat the wavefront algorithm for computing $\text{Z}(G)$, power domination is around $(1.8)^n$, which is better than brute force. -
Problem 1.4.
[Illya Hicks] Can we use forts/havens, hyper graphs and clutters to improve wavefront? A fort is a subgraph such that every vertex outside of the fort connects to at least two vertices inside the fort. -
Problem 1.42.
[Bryan Shader] Develop theory of partial zero forcing/unique paths that Bryan Shader talked about. -
Problem 1.44.
[Daniela Ferrero] Given a set $S$, what is the smallest zero forcing set that contains $S$ (restrained zero forcing). Similarly, given a set $S$ what is the smallest zero forcing set that is contained in $S$? -
Problem 1.46.
Given a set of zero forcing sets can we transform one set into another using basic operations (vertex swaps, adding/deleting, token sliding and jumping, etc.) and stay within the set? In particular, if the given set is the set of all minimum zero forcing sets, how high above $\text{Z}(G)$ do we have to go (how many extra vertices would we have to add) to move between all sets. -
Problem 1.48.
[Boris Brimkov] Find all graphs where all minimal zero forcing sets are also minimum zero forcing sets. (Greedoids?) -
Problem 1.5.
Can we use the geometry of the simplicial complex generated by complements of zero forcing sets to answer questions about zero forcing or propagation time? -
Problem 1.54.
[Boris Brimkov] Establish relationship between zero forcing sets and Hodge theory. -
Problem 1.56.
[Michael Young] If $G$ is a connected, $r$-uniform hypergraph, with $n\ge k+r$ vertices, then the $k$-power domination number is less than or equal to $\dfrac{n}{k+r}$. True if $r =2$. -
Problem 1.58.
[Daniela Ferrero] What is the generalization to zero forcing with multiple colors? Maybe the colors are linearly ordered, i.e. red can force purple, purple can force blue, etc. Maybe the graph has an underlying coloring and filled vertices force according to the zero forcing rule if they are on their preferred color and don’t otherwise. This was an application of an ecosystem where colors represent animals (or bacteria etc.) and the underlying coloring corresponds to an animals suitable habitat. -
Problem 1.6.
Vertex weighted forcing, let $w$ be the weight function, i.e. $w(v)$ is the weight of vertex $v$. Then we want to minimize the cost where the cost is the sum of the weights of a zero forcing set under the standard C.C.R. -
Problem 1.62.
$k$-forcing edge weighted: let $w(u,v)$ be the weight of edge $uv$. let $u$ be filled, if $\displaystyle \sum_{v \text{unfilled neighbor of u}} w(u,v) \le k$ then $u$ forces all unfilled neighbors. Minimize number of vertices needed to force the graph. -
Problem 1.64.
[Ellen Gethner] Can we use art gallery problem results/techniques to help answer zero forcing questions and power domination questions. In particular, what about near triangulation graphs. -
Problem 1.68.
[Leonardo Banchi] Can Daniel Burgarth’s ideas relating the zero forcing number and controllability be extended to PSD matrices?-
Remark. No, he has a small counterexample.
-
-
Problem 1.72.
[Simone Severini] We can use zero forcing to create ‘and’ and ‘or’ gates, can we extend this to model cellular automata evolution? -
Problem 1.74.
[Steve Butler] Does $\text{Z}_q$ equal $\text{M}_q$ for caterpillar graphs? -
Problem 1.76.
[Steve Butler] If $a_0 ,a_1,a_2,\dots$ is a sequence of integers and $a_0 = 1 \le a_1 \le a_2 \le \dots$ can we find a caterpillar graph $C$ such that $Z_0(C) = a_0$, $Z_1(C) = a_1$, ...?
Cite this as: AimPL: Zero forcing and its applications, available at http://aimpl.org/zeroforcing.