The conjecture characterizing graphs with fixed PSD propagation time one

About 1 year old · traced to

Let GG be a connected graph. A PSD fast join is a graph of order n≥2n\geq 2 such that G≅KnG\cong K_n or

G≅(Kn1 ∪˙ Km1)∨…∨(Knt ∪˙ Kmt),G\cong (K_{n_1}\mathbin{\,\dot{\cup}\,} K_{m_1})\vee \ldots \vee (K_{n_t}\mathbin{\,\dot{\cup}\,} K_{m_t}),

for t≥2t\geq 2 and positive integers ni,min_i,m_i with n=∑i=1tni+min=\sum_{i=1}^t n_i+m_i. Here pt⁡+‾(G)\overline{\operatorname{pt}_+}(G) denotes the maximum positive semidefinite propagation time over minimum positive semidefinite forcing sets. PSD fixed-propagation-time conjecture. If GG is a connected graph and

pt⁡+‾(G)=1,\overline{\operatorname{pt}_+}(G)=1,

then GG is a PSD fast join. The theorem establishing the converse shows that PSD fast joins have fixed PSD propagation time equal to one; the conjecture is proved for graphs that are joins or have sufficiently large forcing numbers, while the general case remains open.

References

Primary source

Daniela Ferrero, H. Tracy Hall, Leslie Hogben, Mark Hunnell and Ben Small, “Zero forcing propagation time intervals and graphs with fixed propagation time”, arXiv:2511.16335 (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.