Path extremal conjecture for random set zero forcing

From papers

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 0p10\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 0p10\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 p0,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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.