论文标题
燃烧的几何图
Burning Geometric Graphs
论文作者
论文摘要
引入了一种称为\ textit {图形燃烧}的程序，以促进警报，社会传播或对图形和网络的社会影响或情感的传播建模。 图形燃烧在离散的时间步长（或圆形）上运行。在每个步骤$ t $上，首先（a）从“外部”燃烧一个未燃烧的顶点（作为\ textit {fire source}），然后（b）（b）火蔓延到与顶点相邻的顶点，直到步骤$ t-1 $。 $ g $的所有顶点被烧毁后，此过程停止了。目的是将给定图中的所有顶点刻在最短的时步中。燃烧图所需的最少时间步长称为其\ textit {burning number}。燃烧数量越少，燃烧的速度就越快。 最佳燃烧一般图是NP完整问题。已经证明，最佳的路径森林，蜘蛛图和最高度的树木的最佳燃烧是NP完整的。我们在\ textit {几何图}的几个子类上研究\ textit {图形燃烧问题}。 我们表明，燃烧间隔图（第7.1节，定理7.1），排列图（第7.2节，定理7.2）和磁盘图（第7.3节，定理7.3节）最佳是NP完整的。此外，我们认为，一般图的最佳燃烧（第9.2节，猜想9.1）不能比3个附属因子近似。
A procedure called \textit{graph burning} was introduced to facilitate the modelling of spread of an alarm, a social contagion, or a social influence or emotion on graphs and networks. Graph burning runs on discrete time-steps (or rounds). At each step $t$, first (a) an unburned vertex is burned (as a \textit{fire source}) from "outside", and then (b) the fire spreads to vertices adjacent to the vertices which are burned till step $t-1$. This process stops after all the vertices of $G$ have been burned. The aim is to burn all the vertices in a given graph in minimum time-steps. The least number of time-steps required to burn a graph is called its \textit{burning number}. The less the burning number is, the faster a graph can be burned. Burning a general graph optimally is an NP-Complete problem. It has been proved that optimal burning of path forests, spider graphs, and trees with maximum degree three is NP-Complete. We study the \textit{graph burning problem} on several sub-classes of \textit{geometric graphs}. We show that burning interval graphs (Section 7.1, Theorem 7.1), permutation graphs (Section 7.2, Theorem 7.2) and disk graphs (Section 7.3, Theorem 7.3) optimally is NP-Complete. In addition, we opine that optimal burning of general graphs (Section 9.2, Conjecture 9.1) cannot be approximated better than 3-approximation factor.
