Path extremal conjecture for zero forcing sets of fixed size

Let GG be an nn-vertex graph, and let z(G;k)z(G;k) denote the number of zero forcing sets of GG having size kk. Let PnP_n be the path on nn vertices. Fixed-size zero forcing conjecture. If GG is an nn-vertex graph, then for all kk,

z(G;k)z(Pn;k)=(nk)(nk1k).z(G;k)\le z(P_n;k)=\binom{n}{k}-\binom{n-k-1}{k}.

This conjecture would imply the path extremal conjecture for the probability that a random vertex set is zero forcing, via the expansion of that probability in terms of the numbers z(G;k)z(G;k). The paper presents it as a stronger conjecture and does not establish it.

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).

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.