Burning numbers of t-unicyclic graphs

DOI10.1007/S40840-021-01194-9MaRDI QIDQ2064928zbMATHOpenAlexFDO

Authors Ruiting Zhang, Yingying Yu, Huiqing Liu

Publication date 6 January 2022

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

unicyclic graphlinear forestburning number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Other game-theoretic models (91A40)

Abstract: Given a graph $G$, the burning number of $G$ is the smallest integer $k$ for which there are vertices $x_1,x_2,ldots,x_k$ such that $(x_1,x_2,ldots,x_k)$ is a burning sequence of $G$. It has been shown that the graph burning problem is NP-complete, even for trees with maximum degree three, or linear forests. A $t$-unicyclic graph is a unicycle graph with exactly one vertex of degree greater than $2$. In this paper, we first present the bounds for the burning number of $t$-unicyclic graphs, and then use the burning numbers of linear forests with at most three components to determine the burning number of all $t$-unicyclic graphs for $tle2$.

Recommendations

• Bounds on the burning number
• Burning numbers of path forests and spiders
• Burning number of theta graphs
• An upper bound on the burning number of graphs
• On the burning number of \(p\)-caterpillars

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A note on competitive diffusion through social networks
• A survey of graph burning
• APX-hardness and approximation for the \(k\)-burning number problem
• An upper bound on the burning number of graphs
• Bounds on the burning number
• Bounds on the burning numbers of spiders and path-forests
• Burning a graph as a model of social contagion
• Burning a graph is hard
• Burning graphs: a probabilistic perspective
• Burning number of caterpillars
• Burning number of graph products
• Burning numbers of path forests and spiders
• Graph bootstrap percolation
• Graph burning: tight bounds on the burning numbers of path forests and spiders
• Graph searching games and probabilistic methods
• How to Burn a Graph
• On the burning number of \(p\)-caterpillars
• On the burning number of generalized Petersen graphs
• Simplified weak Galerkin and new finite difference schemes for the Stokes equation
• The Firefighter problem: a survey of results, directions and questions
• The burning number of directed graphs: bounds and computational complexity

Cited in

(4)

• The generalized burning number of graphs
• Burning Numbers of Barbells
• Burning number of theta graphs
• On the burning number of \(p\)-caterpillars

This page was built for publication: Burning numbers of \(t\)-unicyclic graphs

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