{"id":"arxiv/2605.14730","url":"https://arxiv.org/abs/2605.14730","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Hardness of Burning Number Problem on Regular Graphs","domain":"cs.DS","source":"arxiv","authors":["Dhanyamol Antony","L. Sunil Chandran","Anita Das","Shirish Gosavi","Dalu Jacob","Shashanka Kulamarva"],"reviews":0,"subject":"cs.DS","summary":"The Burning Number Problem (BNP) models the spread of information or contagion in a network through a discrete-time process on a graph. At each step, one new vertex is selected as a burning source, while fire simultaneously spreads from previously burned vertices to their neighbors. The burning number of a graph is the minimum number of steps required to burn all vertices. The decision version asks whether the burning number is at most a given integer $k$. BNP is known to be NP-complete even on restricted graph classes such as path forests. We study BNP on connected regular graphs, a natural…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-14","reactions":{}}