Motivated by a discrete-time process intended to measure the speed of the spread of contagion in a graph,the burning number b(G)of a graph G,is defined as the smallest integer k for which there are vertices x1,…xk su...Motivated by a discrete-time process intended to measure the speed of the spread of contagion in a graph,the burning number b(G)of a graph G,is defined as the smallest integer k for which there are vertices x1,…xk such that for every vertex u of G,there exists i∈{1,…k}with dG(u,xi)≤k−i,and dG(xi,xj)≥j−i for any 1≤i<j≤k.The graph burning problem has been shown to be NP-complete even for some acyclic graphs with maximum degree three.In this paper,we determine the burning numbers of all short barbells and long barbells,respectively.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11971158,12371345,11971196).
文摘Motivated by a discrete-time process intended to measure the speed of the spread of contagion in a graph,the burning number b(G)of a graph G,is defined as the smallest integer k for which there are vertices x1,…xk such that for every vertex u of G,there exists i∈{1,…k}with dG(u,xi)≤k−i,and dG(xi,xj)≥j−i for any 1≤i<j≤k.The graph burning problem has been shown to be NP-complete even for some acyclic graphs with maximum degree three.In this paper,we determine the burning numbers of all short barbells and long barbells,respectively.
