Path extremal conjecture for random set zero forcing

About 4 years old · traced to

Let GG be an nn-vertex graph, let PnP_n denote the path on nn vertices, and let Bp(G)B_p(G) be the random subset of vertices obtained by including each vertex independently with probability pp, where 0≤p≤10\le p\le 1. Write ZFS⁡(G)\operatorname{ZFS}(G) for the family of zero forcing sets of GG. Path extremal conjecture. If GG is an nn-vertex graph and 0≤p≤10\le p\le 1, then

Pr⁡[Bp(G)∈ZFS⁡(G)]≤Pr⁡[Bp(Pn)∈ZFS⁡(Pn)],\Pr[B_p(G) \in \operatorname{ZFS}(G)]\le \Pr[B_p(P_n) \in \operatorname{ZFS}(P_n)],

with equality holding if and only if either p∈0,1p\in \\{0,1\\} or G=PnG=P_n. This is the random-set analogue of the classical fact that the path has the smallest zero forcing number among nn-vertex graphs. The paper proves the inequality, with the stated equality conditions, for trees when nn is sufficiently large, and proves a constant-factor comparison for general graphs.

References

Primary source

Bryan Curtis, Luyining Gan, Jamie Haddock, Rachel Lawrence and Sam Spiro, “Zero Forcing with Random Sets”, arXiv:2208.12899 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.