On the burning number of p-caterpillars

DOI10.1007/978-3-030-63072-0_12zbMATH Open1479.05339arXiv1912.10897OpenAlexW2996203613MaRDI QIDQ2056898FDOQ2056898

Authors: Michaela Hiller, Arie M. C. A. Koster, Eberhard Triesch 

Publication date: 8 December 2021

Abstract: The burning number is a recently introduced graph parameter indicating the spreading speed of content in a graph through its edges. While the conjectured upper bound on the necessary numbers of time steps until all vertices are reached is proven for some specific graph classes it remains open for trees in general. We present two different proofs for ordinary caterpillars and prove the conjecture for a generalised version of caterpillars and for trees with a sufficient amount of leaves. Furthermore, determining the burning number for spider graphs, trees with maximum degree three and path-forests is known to be $mathcalNP$-complete, however, we show that the complexity is already inherent in caterpillars with maximum degree three.

Full work available at URL: https://arxiv.org/abs/1912.10897

Recommendations

• On the burning number of generalized Petersen graphs
• On strict-double-bound numbers of caterpillars
• Bounds on the burning numbers of spiders and path-forests
• Burning numbers of \(t\)-unicyclic graphs
• The burning numbers of generalized Peterson graphs \(P(n, 1)\) and \(P(n, 2)\)
• The generalized burning number of graphs
• An upper bound on the burning number of graphs
• Caterpillars in Erdős-Hajnal
• Burning number of graph products
• On the counting of caterpillar continua

zbMATH Keywords

computational complexitycaterpillar graphsburning number

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• The number of caterpillars
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• Burning a graph is hard
• How to Burn a Graph
• Bounds on the burning numbers of spiders and path-forests

Cited In (17)

• Bounds on the burning numbers of spiders and path-forests
• Burning and \(w\)-burning of geometric graphs
• The burning number conjecture holds asymptotically
• Spanning caterpillar in biconvex bipartite graphs
• The burning number conjecture is true for trees without degree-2 vertices
• Caterpillars in Erdős-Hajnal
• Bounds on the burning number
• Parameterized Complexity of Graph Burning
• Parameterized complexity of graph burning
• Improved pyrotechnics: closer to the burning number conjecture
• APX-hardness and approximation for the \(k\)-burning number problem
• Burning numbers of \(t\)-unicyclic graphs
• Burning number of caterpillars
• Burning number of Jahangir graphs
• Burn and win
• Upper bounds and approximation results for the \(k\)-slow burning problem
• Burnability of double spiders and path forests

This page was built for publication: On the burning number of \(p\)-caterpillars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056898)