The decomposed-spider conjecture for graph burning

About 11 years old · traced to

Let TT be a tree containing a decomposed spider formed by paths Qii=1t\\{Q_i\\}_{i=1}^t, where t≥3t\geq 3, and let viv_i be the non-terminal endpoint of QiQ_i for 1≤i≤t1\leq i\leq t. Write b(G)b(G) for the burning number of a graph GG.

Decomposed-spider conjecture. If

b(⋃i=1tQi)≥kb\left(\bigcup_{i=1}^t Q_i\right)\geq k

and

d(vi,vj)≥2kd(v_i,v_j)\geq 2k

for all 1≤i,j≤t1\leq i,j\leq t, then b(T)≥k+1b(T)\geq k+1.

This conjecture proposes that a sufficiently separated decomposed spider forces the ambient tree to require at least one more burning step than the spider itself. The supplied text gives no resolution evidence, so its status is left open.

References

Primary source

Anthony Bonato, Jeannette Janssen and Elham Roshanbin, “Burning a Graph is Hard”, arXiv:1511.06774 (2015).

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.