论文标题
图中的单声位置集
On monophonic position sets in graphs
论文作者
论文摘要
图理论中的一般位置问题要求最大的图$ g $顶点$ s $，因此$ g $的最短路径不包含两个以上的顶点$ s $。在本文中，我们考虑了一种称为\ emph {单声位位置问题}的一般位置问题的变体，该变体是通过``诱导路径''替换“最短路径”而获得的。我们证明了图形的单声位置数字的一些基本属性和边界，并确定某些图系列的单声位位数，包括独立图，两部分图和拆分图。我们表明，无三角形图的单声位置数量在上面的独立性数字上。我们提出了一般位置数，单声位置数和单声音船体数的实现结果。最后，我们讨论了单声道位置问题的复杂性。
The general position problem in graph theory asks for the largest set $S$ of vertices of a graph $G$ such that no shortest path of $G$ contains more than two vertices of $S$. In this paper we consider a variant of the general position problem called the \emph{monophonic position problem}, obtained by replacing `shortest path' by `induced path'. We prove some basic properties and bounds for the monophonic position number of a graph and determine the monophonic position number of some graph families, including unicyclic graphs, complements of bipartite graphs and split graphs. We show that the monophonic position number of triangle-free graphs is bounded above by the independence number. We present realisation results for the general position number, monophonic position number and monophonic hull number. Finally we discuss the complexity of the monophonic position problem.
