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

burning numbercaterpillar graphscomputational complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) 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

(24)

• Bounds on the burning number
• Burning numbers of \(t\)-unicyclic graphs
• Burnability of double spiders and path forests
• Parameterized complexity of graph burning
• Bounds on the burning numbers of spiders and path-forests
• Caterpillars in Erdős-Hajnal
• APX-hardness and approximation for the \(k\)-burning number problem
• Parameterized Complexity of Graph Burning
• Burning and \(w\)-burning of geometric graphs
• Burn and win
• Improved pyrotechnics: closer to the burning number conjecture
• The burning number conjecture holds asymptotically
• The burning number conjecture is true for trees without degree-2 vertices
• Spanning caterpillar in biconvex bipartite graphs
• Burning number of Jahangir graphs
• Upper bounds and approximation results for the \(k\)-slow burning problem
• The burning game on graphs
• Burning sufficiently large p-caterpillars for a fixed p
• Burning disjoint union of spider and path
• Burning path-like and clique-like graphs
• From burning extremal balanced spiders into properties for generalization to all trees
• Burn and win
• Information dissemination and confusion in signed networks
• Burning number of caterpillars

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)