Orientations of graphs with maximum Wiener index

详细信息    查看全文

• 作者：Martin Knor^a ; ^{knor@math.sk" class="auth_mail" title="E-mail the corresponding author} ; Riste &Scaron ; krekovski^b ; ^c ; ^{skrekovski@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Aleksandra Tepeh^b ; ^d ; ^{aleksandra.tepeh@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Wiener index ; Directed graph ; Strongly connected orientations
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：1 October 2016
• 年：2016
• 卷：211
• 期：Complete
• 页码：121-129
• 全文大小：412 K

文摘

In this paper we study the Wiener index (i.e., the total distance or the transmission number) of not necessarily strongly connected digraphs. In order to do so, if in a digraph there is no directed path from a vertex 246ddda4e1" title="Click to view the MathML source">a$a$ to a vertex k to view the MathML source">b$b$, we follow the convention that k to view the MathML source">d(a,b)=0$d(a,b)=0$, which was independently introduced in several studies of directed networks. By extending the results of Plesník and Moon we characterize tournaments with the maximal and the second maximal Wiener index. We also study oriented Theta-graphs and, as a consequence, we obtain that an orientation of a given graph which yields the maximum Wiener index is not necessarily strongly connected. In particular, we characterize orientations of Theta-graphs k to view the MathML source">Θ_a,b,0${\Theta }_{a,b,0}$ and k to view the MathML source">Θ_a,b,1${\Theta }_{a,b,1}$ which result in the maximum Wiener index. In addition, orientations with the maximum Wiener index among strongly connected orientations of k to view the MathML source">Θ_a,b,c${\Theta }_{a,b,c}$ are characterized. We conclude the paper with several open problems.