论文标题
图形的路径偏心率
Path eccentricity of graphs
论文作者
论文摘要
令$ g $为连接的图。 ECC $ _G（P）$表示的路径$ P $的偏心率是从$ p $到$ g $的任何顶点的最大距离。在\ textsc {central路径}（CP）问题中，我们的目的是找到一条最小偏心率的路径。 1981年，Cockayne等人在研究图上的不同中心度度量的研究中引入了这个问题。他们表明，CP可以在树上的线性时间内解决，但众所周知，在许多类别的图中，众所周知，cp是NP-HARD，例如弦式二分组图，平面3连接的图，拆分图等。 我们将连接图〜$ g $的路径偏心率作为参数。令PE $（g）$表示中央路径$ p $ $ g $的ECC $ _G（P）$的值。我们在某些图形类中获得了PE $（g）$的紧密上限。我们证明了Biconvex图上的PE $（g）\ leq 1 $，而两部分凸形图上的pe $（g）\ leq 2 $。此外，我们设计了在线性时间中找到这样的路径的算法。另一方面，通过研究图的最长路径，我们在一般图和$ k $连接的图上获得了PE $（g）$的紧密上限。 最后，我们研究了图中心路径和最长路径之间的关系。我们表明，在树木和二分置换图上，最长的路径也是一条核心路径。此外，对于这些图形的超类，我们为此特性展示了反例。
Let $G$ be a connected graph. The eccentricity of a path $P$, denoted by ecc$_G(P)$, is the maximum distance from $P$ to any vertex in $G$. In the \textsc{Central path} (CP) problem our aim is to find a path of minimum eccentricity. This problem was introduced by Cockayne et al., in 1981, in the study of different centrality measures on graphs. They showed that CP can be solved in linear time in trees, but it is known to be NP-hard in many classes of graphs such as chordal bipartite graphs, planar 3-connected graphs, split graphs, etc. We investigate the path eccentricity of a connected graph~$G$ as a parameter. Let pe$(G)$ denote the value of ecc$_G(P)$ for a central path $P$ of $G$. We obtain tight upper bounds for pe$(G)$ in some graph classes. We show that pe$(G) \leq 1$ on biconvex graphs and that pe$(G) \leq 2$ on bipartite convex graphs. Moreover, we design algorithms that find such a path in linear time. On the other hand, by investigating the longest paths of a graph, we obtain tight upper bounds for pe$(G)$ on general graphs and $k$-connected graphs. Finally, we study the relation between a central path and a longest path in a graph. We show that on trees, and bipartite permutation graphs, a longest path is also a central path. Furthermore, for superclasses of these graphs, we exhibit counterexamples for this property.
