The conjecture characterizing graphs with fixed PSD propagation time one
Let be a connected graph. A PSD fast join is a graph of order such that or
for and positive integers with . Here denotes the maximum positive semidefinite propagation time over minimum positive semidefinite forcing sets. PSD fixed-propagation-time conjecture. If is a connected graph and
then 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
- 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.