On the burning number of p-caterpillars

DOI10.1007/978-3-030-63072-0_12MaRDI QIDQ2056898zbMATH OpenOpenAlexFDO

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

Publication date 8 December 2021

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

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)

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.

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

Cites work

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

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
• Burning numbers of \(t\)-unicyclic graphs
• APX-hardness and approximation for the \(k\)-burning number problem
• 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)