论文标题
守望者在定向图上的步行问题
The watchman's walk problem on directed graphs
论文作者
论文摘要
在图中，守望者的步行是最小封闭的统治步行。给定图表$ g $和一个守望者，$ w（g）$表示守望者步行的长度（守望者号码），而守望者步行问题的典型目标是确定$ w（g）$并在$ g $中找到守望者的步行。在本文中，我们将守望者的步行问题扩展到了定向图。在有向图中，我们说守望者只能移动并看到与他相对于外向弧相邻的顶点。也就是说，一个守望者的步行是定向的，统治是朝向弧线的方向。该论文的定向图是锦标赛的家族和完整多部分图的方向。我们给予守望者编号的界限，并讨论其与支配数字变体的关系。
In a graph, a watchman's walk is a minimum closed dominating walk. Given a graph $G$ and a single watchman, the length of a watchman's walk in $G$ (the watchman number) is denoted by $w(G)$ and the typical goals of the watchman's walk problem is to determine $w(G)$ and find a watchman's walk in $G$. In this paper, we extend the watchman's walk problem to directed graphs. In a directed graph, we say that the watchman can only move to and see the vertices that are adjacent to him relative to outgoing arcs. That is, a watchman's walk is oriented and domination occurs in the direction of the arcs. The directed graphs this paper focuses on are families of tournaments and orientations of complete multipartite graphs. We give bounds on the watchman number and discuss its relationship to variants of the domination number.
