Brimkov's propagation time interval conjecture for hypercubes

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 d2d\geq 2,

pt(Qd)=1andPT(Qd)=2d2.\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.

Sources & referencesView supporting material

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.