论文标题
双蜘蛛和路径森林的可耐用性
Burnability of Double Spiders and Path Forests
论文作者
论文摘要
图的燃烧数量可用于测量网络中传播的传播速度。燃烧的数字猜想可以说是与此图参数相关的主要未解决的猜想，可以通过证明每订单$ m^2 $的每一树都有最多$ m $燃烧的数字来解决。众所周知，这可以容纳许多类别的树木，包括蜘蛛 - 恰好一个顶点的树木大于两个。实际上，已经证实，某些略大于$ m^2 $的订单的蜘蛛最多也具有$ m $的燃烧数字，然后将其猜想为所有树木是正确的。本文的第一个焦点是验证双蜘蛛的这种疑问稍强 - 树木具有两个至少三个的顶点，它们相邻。我们的另一个重点涉及路径森林的燃烧数量，这是一类图形，其中它们的燃烧数量与蜘蛛和双蜘蛛的燃烧数量自然相关。在这里，我们的主要结果表明，订单$ m^2 $的路径森林的最短路径足够长的燃烧数量$ m $，这是任何相同订单的路径森林最小的。
The burning number of a graph can be used to measure the spreading speed of contagion in a network. The burning number conjecture is arguably the main unresolved conjecture related to this graph parameter, which can be settled by showing that every tree of order $m^2$ has burning number at most $m$. This is known to hold for many classes of trees, including spiders - trees with exactly one vertex of degree greater than two. In fact, it has been verified that certain spiders of order slightly larger than $m^2$ also have burning numbers at most $m$, a result that has then been conjectured to be true for all trees. The first focus of this paper is to verify this slightly stronger conjecture for double spiders - trees with two vertices of degrees at least three and they are adjacent. Our other focus concerns the burning numbers of path forests, a class of graphs in which their burning numbers are naturally related to that of spiders and double spiders. Here, our main result shows that a path forest of order $m^2$ with a sufficiently long shortest path has burning number exactly $m$, the smallest possible for any path forest of the same order.
