Burning numbers of t-unicyclic graphs

DOI10.1007/S40840-021-01194-9zbMATH Open1479.05228arXiv2103.07840OpenAlexW3204818430MaRDI QIDQ2064928FDOQ2064928

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)

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$.

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

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

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)

Cites Work

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

Cited In (4)

• Burning number of theta graphs
• The generalized burning number of graphs
• Burning Numbers of Barbells
• 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)