Greedy optimality conjecture for tooth-dominant comb graphs

Let Cn,mC_{n,m} be the comb graph with spine parameter nn and tooth parameter mm, let b(Cn,m)b(C_{n,m}) be its burning number, and let Tgreedy(S)T_{\mathrm{greedy}}^{(S)} be the number of fires used by the greedy algorithm when its initial placement is specified by SS. Define

Tgreedy=min{Tgreedy(S):S=1,2,,n}.T_{\mathrm{greedy}}=\min\left\{T_{\mathrm{greedy}}^{(S)}:S=1,2,\ldots,n\right\}.

Greedy optimality conjecture for comb graphs. If nmn\leq m, then

b(Cn,m)=min{Tgreedy(S):S=1,2,,n}.b(C_{n,m})=\min\left\{T_{\mathrm{greedy}}^{(S)}:S=1,2,\ldots,n\right\}.

The greedy algorithm is proved optimal in the spine-dominant regime nmn\geq m, while in the tooth-dominant regime it is known to give an approximation and has been confirmed through m=n+4m=n+4. Its optimality for all nmn\leq m remains open.

Sources & referencesView supporting material

Primary source

John Peca-Medlin, “Burning rooted graph products”, arXiv:2603.00304 (2026).

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.