Path extremal conjecture for random set zero forcing
Path extremal conjecture for random set zero forcing
Let be an -vertex graph, let denote the path on vertices, and let be the random subset of vertices obtained by including each vertex independently with probability , where . Write for the family of zero forcing sets of . Path extremal conjecture. If is an -vertex graph and , then
with equality holding if and only if either or . This is the random-set analogue of the classical fact that the path has the smallest zero forcing number among -vertex graphs. The paper proves the inequality, with the stated equality conditions, for trees when 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
Sign in to submit a solution.
No solutions have been posted yet.