论文标题
在图形方向的维也纳索引上
On the Wiener Index of Orientations of Graphs
论文作者
论文摘要
强大的Digraph $ d $的Wiener索引定义为所有有序对顶点之间的距离之和。该定义已扩展到不一定要通过将顶点$ a $定义到顶点$ b $的距离为$ 0 $的挖掘图，如果没有$ a $ a $ a $ a $ a $ b $ in $ d $中的路径。 Knor，Uskrekovski和Tepeh [关于定向图的Wiener索引的一些言论。 Appl。\ Math。\comput。\ {\ bf 273}]考虑了具有最大Wiener索引的图的方向。作者推测，对于给定的树$ t $，$ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ wiener索引始终包含一个顶点$ v $，以便对于每个顶点$ u $，都有一个$（u，v）$ - 路径或$（v，v，u）$。在本文中，我们反驳了猜想。 我们还表明，找到给定图的最大Wiener索引方向的问题是NP完整的，因此通过Knor，Uskrekovski和Tepeh回答了一个问题[具有最大Wiener索引的图的方向。离散应用。\ Math。\ 211]。 我们简要讨论了找到给定图的最小维纳索引方向的相应问题，并表明确定$ m $ edges上的给定图的特殊情况是可以在$ n $的时间quadratic quadratic求解维也纳索引$ m $的方向。
The Wiener index of a strong digraph $D$ is defined as the sum of the distances between all ordered pairs of vertices. This definition has been extended to digraphs that are not necessarily strong by defining the distance from a vertex $a$ to a vertex $b$ as $0$ if there is no path from $a$ to $b$ in $D$. Knor, uSkrekovski and Tepeh [Some remarks on Wiener index of oriented graphs. Appl.\ Math.\ Comput.\ {\bf 273}] considered orientations of graphs with maximum Wiener index. The authors conjectured that for a given tree $T$, an orientation $D$ of $T$ of maximum Wiener index always contains a vertex $v$ such that for every vertex $u$, there is either a $(u,v)$-path or a $(v,u)$-path in $D$. In this paper we disprove the conjecture. We also show that the problem of finding an orientation of maximum Wiener index of a given graph is NP-complete, thus answering a question by Knor, uSkrekovski and Tepeh [Orientations of graphs with maximum Wiener index. Discrete Appl.\ Math.\ 211]. We briefly discuss the corresponding problem of finding an orientation of minimum Wiener index of a given graph, and show that the special case of deciding if a given graph on $m$ edges has an orientation of Wiener index $m$ can be solved in time quadratic in $n$.
