The conjecture characterizing graphs with fixed PSD propagation time one

From papers

Let GG be a connected graph. A PSD fast join is a graph of order n2n\geq 2 such that GKnG\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 t2t\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.

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

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).

Solutions 0

No solutions have been posted yet.