← All problems

Equality of (3,3)- and (3,4)-spreading numbers on grid graphs

5 years old · traced to

Let PmP_m and PnP_n be paths on mm and nn vertices, respectively, and let Pm□PnP_m\square P_n denote their Cartesian product. For a graph GG, write σ(p,q)(G)\sigma_{(p,q)}(G) for its (p,q)(p,q)-spreading number. Spreading-number equality conjecture. If m,n≥3m,n\ge 3, then

σ(3,3)(Pm□Pn)=σ(3,4)(Pm□Pn).\sigma_{(3,3)}(P_m\square P_n)=\sigma_{(3,4)}(P_m\square P_n).

The conjecture concerns the unresolved (3,q)(3,q)-spreading numbers for rectangular grid graphs. Since every vertex of Pm□PnP_m\square P_n has degree at most 44, the (3,4)(3,4)- and (3,∞)(3,\infty)-spreading numbers coincide; the conjectured equality would therefore also identify the (3,3)(3,3)-spreading number with the corresponding bootstrap percolation number, whose exact values are not known in general.

References

2 papers in this index state this conjecture (2021–2023). The statement above is taken from the most recent of them; the others are arXiv:2109.07875.

Source: Boštjan Brešar, Tanja Dravec, Aysel Erey and Jaka Hedžet, “Spreading in graphs”, arXiv:2309.16852 (2023).

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.