The decomposed-spider conjecture for graph burning

Let TT be a tree containing a decomposed spider formed by paths Qii=1t\\{Q_i\\}_{i=1}^t, where t3t\geq 3, and let viv_i be the non-terminal endpoint of QiQ_i for 1it1\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 1i,jt1\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.

Sources & referencesView supporting material

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.