Greedy optimality conjecture for tooth-dominant comb graphs
Greedy optimality conjecture for tooth-dominant comb graphs
Let be the comb graph with spine parameter and tooth parameter , let be its burning number, and let be the number of fires used by the greedy algorithm when its initial placement is specified by . Define
Greedy optimality conjecture for comb graphs. If , then
The greedy algorithm is proved optimal in the spine-dominant regime , while in the tooth-dominant regime it is known to give an approximation and has been confirmed through . Its optimality for all remains open.
Sources & referencesView supporting material
Primary source
John Peca-Medlin, “Burning rooted graph products”, arXiv:2603.00304 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.