论文标题
在顶点位置的图表数
On the Vertex Position Number of Graphs
论文作者
论文摘要
在本文中，我们将可见性的概念从整数晶格中的一个点到图理论的设置。对于连接图$ g $的顶点$ x $，我们说$ s \ subseteq v（g）$是\ emph {$ x $ - position set}，如果对于任何$ y \ in s $ in s $ in n n y yin s $是$ x，y $ g $中的任何$ y \，$ x，y $ paths in $ g $ in $ g $不包含$ s $ s \ s \ setminus \ setMinus \ y \ y \ y \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \} $。我们研究了图中最大和最小的$ x $位置集的最大和最小订单，确定了图形类别的这些数字，并根据腰围，顶点度，直径和半径给出界限。最后，我们讨论了在图中找到最大顶点位置集的复杂性。
In this paper we generalise the notion of visibility from a point in an integer lattice to the setting of graph theory. For a vertex $x$ of a connected graph $G$, we say that a set $S \subseteq V(G)$ is an \emph{$x$-position set} if for any $y \in S$ the shortest $x,y$-paths in $G$ contain no point of $S\setminus \{ y\}$. We investigate the largest and smallest orders of maximum $x$-position sets in graphs, determining these numbers for common classes of graphs and giving bounds in terms of the girth, vertex degrees, diameter and radius. Finally we discuss the complexity of finding maximum vertex position sets in graphs.
