Graph Burning: Bounds and Hardness
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915865997344768 |
|---|---|
| author | Antony, Dhanyamol Chandran, L. Sunil Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka |
| author_facet | Antony, Dhanyamol Chandran, L. Sunil Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka |
| contents | Graph burning is a discrete-time process that models the propagation of information in a network. Initially, we have an undirected graph of unburned vertices. At each time step, an unburned vertex is chosen to burn; additionally, unburned vertices with at least one burned neighbor from the previous step also become burned. Once a vertex is burned, it remains burned for all future steps. The burning number of a graph is the minimum number of steps to burn all the vertices of the graph. The BURNING NUMBER PROBLEM asks whether the burning number of an input graph $G$ is at most $k$ or not. In this paper, we study the BURNING NUMBER PROBLEM both from an algorithmic and a structural viewpoint. The BURNING NUMBER PROBLEM is known to be NP-complete for interval graphs. Here, we prove that this problem is NP-complete even when restricted to connected proper interval graphs. The well-known burning number conjecture asserts that the burning number of a connected graph of order $n$ is at most $\lceil \sqrt{n}~\rceil$. In line with this conjecture, the upper and lower bounds of the burning number are well-studied for various graph classes. Here, we provide an improved upper bound for the burning number of connected $P_k$-free graphs and show that the bound is tight up to an additive constant of $1$. Finally, we study two variants of the problem: edge burning and total burning. We establish their relationship with the classical burning and evaluate the algorithmic complexity of these variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18984 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph Burning: Bounds and Hardness Antony, Dhanyamol Chandran, L. Sunil Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka Combinatorics Discrete Mathematics 05C38, 05C05, 05C85 Graph burning is a discrete-time process that models the propagation of information in a network. Initially, we have an undirected graph of unburned vertices. At each time step, an unburned vertex is chosen to burn; additionally, unburned vertices with at least one burned neighbor from the previous step also become burned. Once a vertex is burned, it remains burned for all future steps. The burning number of a graph is the minimum number of steps to burn all the vertices of the graph. The BURNING NUMBER PROBLEM asks whether the burning number of an input graph $G$ is at most $k$ or not. In this paper, we study the BURNING NUMBER PROBLEM both from an algorithmic and a structural viewpoint. The BURNING NUMBER PROBLEM is known to be NP-complete for interval graphs. Here, we prove that this problem is NP-complete even when restricted to connected proper interval graphs. The well-known burning number conjecture asserts that the burning number of a connected graph of order $n$ is at most $\lceil \sqrt{n}~\rceil$. In line with this conjecture, the upper and lower bounds of the burning number are well-studied for various graph classes. Here, we provide an improved upper bound for the burning number of connected $P_k$-free graphs and show that the bound is tight up to an additive constant of $1$. Finally, we study two variants of the problem: edge burning and total burning. We establish their relationship with the classical burning and evaluate the algorithmic complexity of these variants. |
| title | Graph Burning: Bounds and Hardness |
| topic | Combinatorics Discrete Mathematics 05C38, 05C05, 05C85 |
| url | https://arxiv.org/abs/2402.18984 |