Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871860 | Discrete Applied Mathematics | 2016 | 9 Pages |
Abstract
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 a to a vertex b, we follow the convention that 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 Îa,b,0 and Îa,b,1 which result in the maximum Wiener index. In addition, orientations with the maximum Wiener index among strongly connected orientations of Îa,b,c are characterized. We conclude the paper with several open problems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Knor, Riste Å krekovski, Aleksandra Tepeh,