From the 1 of 5 linked papers with an AI index.
5 papers
Graph Burning: Bounds and Hardness
Dhanyamol Antony, L. Sunil Chandran, Anita Das +3
The paper studies the graph burning process, proving NP‑completeness for proper interval graphs, giving tight upper bounds for connected P_k‑free graphs, and analyzing edge and tot…
Burning Graph Powers and Branching Trees
Jesper Jansson, Shashanka Kulamarva, Yukihiro Murakami +1
Graph burning is a discrete-time process that models the spread of social contagion. Initially, all vertices are unburned. In each round, one unburned vertex is selected and burned…
Hardness of Burning Number Problem on Regular Graphs
Dhanyamol Antony, L. Sunil Chandran, Anita Das +3
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 Graph-Theoretic Model for a Generic Three-Jug Puzzle
Suresh Manjanath Hegde, Shashanka Kulamarva
A classic three-jug puzzle asks, given three jugs , , and with fixed maximum capacities, with jug filled with wine to its maximum capacity, whether is it possible to…
Acyclic Edge Coloring of 3-sparse Graphs
Nevil Anto, Manu Basavaraju, Shashanka Kulamarva
A proper edge coloring of a graph without any bichromatic cycles is said to be an acyclic edge coloring of the graph. The acyclic chromatic index of a graph denoted by ,…