| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Variations of zero forcing and power domination

Given a simple, finite graph $G$ with vertex set $V(G)$, we define a zero forcing set of $G$ as follows. Choose $S \subseteq V(G)$ and color all vertices of $S$ blue and all vertices in $V(G)-S$ white. The color change rule is if $w$ is the only white neighbor of blue vertex $v$, then we change the color of $w$ from white to blue. If after applying the color change rule as many times as possible eventually every vertex of $G$ is blue, we call $S$ a zero forcing set of $G$.

Given a graph $G$ and a set $S \subseteq V(G)$, we define the set of vertices monitored by the set $S$ where all vertices in $S$ and all neighbors of vertices in $S$ are monitored and whenever a vertex $v$ is monitored and all but one of its neighbors, say $w$, are monitored, then vertex $w$ is also monitored. In this case we say that vertex $v$ propagates to vertex $w$. An initial set of vertices that eventually monitors the whole graph is called a power dominating set. The power domination number is the minimum order of a power dominating set.

    1. Power domination with zero forcing variants

          We begin the propagation process as power domination in the first time step, then continue the propagation process as zero forcing for all further time.

      Add remark

      Problem 2.1.

      [Adam Berliner] Determine the minimum number of elements in a set $S$ so that such a propagation process covers the vertices of $G$ after a time step $t \in \mathbb{N}$.
        1. Remark. [Mark Hunnell] Beginning the first $k$ time steps of the propagation process as power domination, then continuing as zero forcing could also be of interest.

            • Reversible zero forcing

                  We consider the zero forcing propagation process where after a certain time $t \in \mathbb{N}$, if an observed vertex does not propagate it is unobserved. Such a process is helpful in modeling disease spread. Notice that vertices can be observed more than once, relating to the possibility of getting reinfected.

              Add remark

              Problem 2.2.

              [Daniela Ferrero] For $t=3$ and a graph $G$, determine the minimum number of elements in a set $S \subseteq V(G)$ so that such a propagation process covers the vertices of $G$.

                • Zero forcing and planarity

                      We investigate the relationship between the existence of a zero forcing set and the planarity of the graph.

                  Add remark

                  Problem 2.3.

                  [Emily McMillon] Let $G$ be a planar graph. Determine conditions for which a zero forcing set $S$ exists. If such a set $S$ exists, determine bounds on the size of the zero forcing set $S$ of $G$.

                    • Power domination for $d$-regular random graphs

                          There is a known power domination result for $3$-regular random graphs.

                      Add remark

                      Problem 2.4.

                      [Daniela Ferrero] Determine if the power domination result for $3$-regular random graphs can be generalized to $d$-regular random graphs.

                        • Random forcing set


                          Add remark

                          Problem 2.5.

                          [Amanda Redlich] Given a graph $G$ with a minimum zero forcing set of size $s_0$, determine the probability that a randomly chosen set $S$ of size $s \ge s_0$ is a forcing set.

                            • Redefining as poset problems

                                  We can redefine forcing problems as poset problems. We want to explore a similar redefining for power domination and zero forcing.

                              Add remark

                              Problem 2.6.

                              [Ann Trenk] Determine conditions for a poset $(\mathcal{G}, \preceq)$ where $\mathcal{G}$ is the set of graphs with a minimum size power dominating (zero forcing) set.

                                • Proportional zero forcing

                                      We introduce a variation on zero forcing propagation, assigning a weight based on the step of forcing. At each step, a newly forced vertex inherits half of the forcing weight from each vertex that is forcing it.

                                  Add remark

                                  Problem 2.7.

                                  [Chassidy Bozeman] Determine the minimum number of vertices needed to guarantee a graph to be fully forced.

                                    • Upper bound on the maximum nullity of a graph

                                          The zero forcing number of a graph is the minimum size of a zero forcing set, which gives an upper bound to the maximum nullity.

                                      Add remark

                                      Problem 2.8.

                                      [Mark Hunnell] Determine if the enhanced (odd cycle) forcing number bounds the maximum nullity of any families of graphs.

                                        • Maximal zero forcing sets

                                              The zero forcing number of a graph is known to be bounded in terms of the order, maximum degree and minimum degree.

                                          Add remark

                                          Problem 2.9.

                                          Determine if the zero forcing number is equivalent to the maximal number of zero forcing sets.

                                              Cite this as: AimPL: Graph Theory: structural properties, labelings, and connections to applications, available at http://aimpl.org/graphstructureapp.