Brimkov's propagation time interval conjecture for hypercubes

About 1 year old · traced to

Let QdQ_d be the dd-dimensional hypercube graph, and let pt⁡(G)\operatorname{pt}(G) and PT⁡(G)\operatorname{PT}(G) denote the minimum and maximum propagation times over minimum zero forcing sets of a graph GG. The graph GG has a full propagation time interval when every integer in [pt⁡(G),PT⁡(G)][\operatorname{pt}(G),\operatorname{PT}(G)] is realized by some minimum zero forcing set.

Brimkov's conjecture. For every integer d≥2d\geq 2,

pt⁡(Qd)=1andPT⁡(Qd)=2d−2.\operatorname{pt}(Q_d)=1\quad\text{and}\quad \operatorname{PT}(Q_d)=2^{d-2}.

Moreover, QdQ_d has a full propagation time interval.

Only a few graph families are known to have full propagation time intervals, so the conjecture predicts both extremal propagation times and the realization of every intermediate time for hypercubes.

References

Primary source

Thomas R. Cameron and Jonad Pulaj, “IP Models for Minimum Zero Forcing Sets, Forts, and Related Graph Parameters”, arXiv:2508.07293 (2025).

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.