Extremal estimates of the Wiener index for weakly connected directed graphs
https://doi.org/10.18255/1818-1015-2025-1-16-31
Abstract
The article considers the Wiener index for weakly connected directed graphs. For such graphs, the distance $d(u,v)$ between vertices $u$ and $v$ is not always defined, which requires a correction for the Wiener index to be meaningful. The convention where it is assumed that $d(u,v)=0$ in the absence of a path between vertices is well-studied. We consider the convention where $d(u,v)$ is equal to the number of vertices in the graph when there is no path between vertices $u$ and $v$. The article presents graphs with $n$ vertices for which the Wiener index with this сonvention reaches minimal and maximal values. We also present experimental results showing how the Wiener index (considering both conventions of distance) changes when arcs are added to a weakly connected directed graph with fixed and random structures.
Supporting agencies: Yaroslavl State University (project VIP-016).
References
1. H. Wiener, “Structural Determination of Paraffin Boiling Points,” Journal of American Chemical Society, vol. 69, no. 1, pp. 17–20, 1947.
2. A. A. Dobrynin, R. Entringer, and I. Gutman, “Wiener Index of Trees: Theory and Applications,” Acta Applicandae Mathematicae, vol. 66, pp. 211–249, 2001, doi: 10.1023/a:1010767517079.
3. F. Harary, “Status and Contrastatus,” Sociometry, vol. 22, no. 1, pp. 23–43, 1959.
4. C. P. Ng and H. H. Teh, “On Finite Graphs of Diameter 2,” Nanta Math, vol. 1, pp. 72–75, 1966/67.
5. M. Knor, R. vSkrekovski, and A. Tepeh, “Some Remarks on Wiener Index of Oriented Graphs,” Applied Mathematics and Computation, vol. 273, pp. 631–636, 2016, doi: 10.1016/j.amc.2015.10.033.
6. M. Knor, R. vSkrekovski, and A. Tepeh, “Orientations of graphs with maximum Wiener index,” Discrete Applied Mathematics, vol. 211, pp. 121–129, 2016, doi: 10.1016/j.dam.2016.04.015.
7. P. Dankelmann, “On the Wiener index of orientations of graphs,” Discrete Applied Mathematics, vol. 336, pp. 125–131, 2023, doi: 10.1016/j.dam.2023.04.004.
8. M. Knor, R. vSkrekovski, and T. A., “Digraphs with large maximum Wiener index,” Applied Mathematics and Computation, vol. 284, pp. 260–267, 2016, doi: 10.1016/j.amc.2016.03.007.
9. R. A. Botafogo, E. Rivlin, and B. Shneiderman, “Structural Analysis of Hypertexts: Identifying Hierarchies and Useful Metrics,” ACM Transactions on Information Systems, vol. 10, no. 2, pp. 142–180, 1992, doi: 10.1145/146802.146826.
10. D. B. West, Introduction to Graph Theory, Second Edition. Pearson Education, 2001.
11. C. Greenhill, “Generating graphs randomly,” K. K. Dabrowski, M. Gadouleau, N. Georgiou, M. Johnson, G. B. Mertzios, and D. Paulusma, Eds. Cambridge University Press, 2021, pp. 133–186.
12. R. Durstenfeld, “Algorithm 235: Random permutation,” Communications of ACM, vol. 7, no. 7, p. 420, 1964, doi: 10.1145/364520.364540.
13. D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, 3rd ed., vol. 2. Addison-Wesley, 1998.
14. M. Knor and R. Skrekovski, “On maximum Wiener index of directed grids,” The Art of Discrete and Applied Mathematics, vol. 6, no. 3, p. #P3.02, 2023, doi: 10.26493/2590-9770.1526.2b3.
Review
For citations:
Chalyy D.Y. Extremal estimates of the Wiener index for weakly connected directed graphs. Modeling and Analysis of Information Systems. 2025;32(1):16-31. (In Russ.) https://doi.org/10.18255/1818-1015-2025-1-16-31
Views:
129
Email this article 