Path extremal conjecture for random set zero forcing
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.