论文标题
在有向图上的标准零强迫限制
Throttling for standard zero forcing on directed graphs
论文作者
论文摘要
零强迫是图表上的一个过程，其中使用颜色变化规则迫使顶点变为蓝色。图表中所有顶点所花费的时间为蓝色是传播时间。节流最小化初始蓝色顶点的总和和传播时间的总和。在本文中，我们研究了定向图（Digraphs）的环境中的节流。我们表征了所有简单的挖掘物，最多只能使用节流数字$ t $，并在翻转弧和删除顶点后检查节流数的变化。我们还介绍了无向图的方向节流间隔（OTI），这是图形方向实现的节流数字的范围。尽管显示OTI在不同的图家族之间有所不同，但获得了一些一般界限。另外，通过路径的方向的方向来实现路径的OTI的最大值，该路径的方向交替。此方向的节流数是根据顶点数量确切确定的。
Zero forcing is a process on graphs in which a color change rule is used to force vertices to become blue. The amount of time taken for all vertices in the graph to become blue is the propagation time. Throttling minimizes the sum of the number of initial blue vertices and the propagation time. In this paper, we study throttling in the context of directed graphs (digraphs). We characterize all simple digraphs with throttling number at most $t$ and examine the change in the throttling number after flipping arcs and deleting vertices. We also introduce the orientation throttling interval (OTI) of an undirected graph, which is the range of throttling numbers achieved by the orientations of the graph. While the OTI is shown to vary among different graph families, some general bounds are obtained. Additionally, the maximum value of the OTI of a path is conjectured to be achieved by the orientation of a path whose arcs alternate in direction. The throttling number of this orientation is exactly determined in terms of the number of vertices.
