<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">mais</journal-id><journal-title-group><journal-title xml:lang="ru">Моделирование и анализ информационных систем</journal-title><trans-title-group xml:lang="en"><trans-title>Modeling and Analysis of Information Systems</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1818-1015</issn><issn pub-type="epub">2313-5417</issn><publisher><publisher-name>Yaroslavl State University</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.18255/1818-1015-2025-1-16-31</article-id><article-id custom-type="elpub" pub-id-type="custom">mais-1913</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Discrete Mathematics in Relation to Computer Science</subject></subj-group></article-categories><title-group><article-title>Экстремальные оценки индекса Винера для слабо связных ориентированных графов</article-title><trans-title-group xml:lang="en"><trans-title>Extremal estimates of the Wiener index for weakly connected directed graphs</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0003-0553-7387</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Чалый</surname><given-names>Дмитрий Юрьевич</given-names></name><name name-style="western" xml:lang="en"><surname>Chalyy</surname><given-names>Dmitry Y.</given-names></name></name-alternatives><email xlink:type="simple">chaly@uniyar.ac.ru</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Ярославский государственный университет им. П.Г. Демидова</institution><country>Россия</country></aff><aff xml:lang="en"><institution>P.G. Demidov Yaroslavl State University</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2025</year></pub-date><pub-date pub-type="epub"><day>22</day><month>03</month><year>2025</year></pub-date><volume>32</volume><issue>1</issue><fpage>16</fpage><lpage>31</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Чалый Д.Ю., 2025</copyright-statement><copyright-year>2025</copyright-year><copyright-holder xml:lang="ru">Чалый Д.Ю.</copyright-holder><copyright-holder xml:lang="en">Chalyy D.Y.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://www.mais-journal.ru/jour/article/view/1913">https://www.mais-journal.ru/jour/article/view/1913</self-uri><abstract><p>В статье рассматривается индекс Винера для слабо связных ориентированных графов. Для таких графов из-за слабой связности не всегда определено расстояние $d(u,v)$ между вершинами $u$ и $v$, что требует уточнения чтобы индекс Винера имел содержательный смысл. Достаточно хорошо изучен случай, когда полагают что $d(u,v)=0$ при отсутствии пути между вершинами. Мы рассматриваем уточнение, когда $d(u,v)$ равно количеству вершин в графе при отсутствии пути между вершинами $u$ и $v$. В статье представлены графы на $n$ вершинах, где индекс Винера с таким уточнением достигает минимального и максимального значения. Мы также представляем результаты экспериментов, которые показывают как изменяется индекс Винера (с учетом обоих способов уточнения расстояния) при добавлении дуг в слабо связный ориентированный граф как фиксированной, так и случайной структуры.</p></abstract><trans-abstract xml:lang="en"><p>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.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>слабо ориентированный граф</kwd><kwd>индекс Винера</kwd></kwd-group><kwd-group xml:lang="en"><kwd>weakly connected graph</kwd><kwd>Wiener index</kwd></kwd-group><funding-group><funding-statement xml:lang="ru">ЯрГУ (проект VIP-016).</funding-statement><funding-statement xml:lang="en">Yaroslavl State University (project VIP-016).</funding-statement></funding-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">H. Wiener, “Structural Determination of Paraffin Boiling Points,” Journal of American Chemical Society, vol. 69, no. 1, pp. 17–20, 1947.</mixed-citation><mixed-citation xml:lang="en">H. Wiener, “Structural Determination of Paraffin Boiling Points,” Journal of American Chemical Society, vol. 69, no. 1, pp. 17–20, 1947.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">F. Harary, “Status and Contrastatus,” Sociometry, vol. 22, no. 1, pp. 23–43, 1959.</mixed-citation><mixed-citation xml:lang="en">F. Harary, “Status and Contrastatus,” Sociometry, vol. 22, no. 1, pp. 23–43, 1959.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">C. P. Ng and H. H. Teh, “On Finite Graphs of Diameter 2,” Nanta Math, vol. 1, pp. 72–75, 1966/67.</mixed-citation><mixed-citation xml:lang="en">C. P. Ng and H. H. Teh, “On Finite Graphs of Diameter 2,” Nanta Math, vol. 1, pp. 72–75, 1966/67.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">D. B. West, Introduction to Graph Theory, Second Edition. Pearson Education, 2001.</mixed-citation><mixed-citation xml:lang="en">D. B. West, Introduction to Graph Theory, Second Edition. Pearson Education, 2001.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">R. Durstenfeld, “Algorithm 235: Random permutation,” Communications of ACM, vol. 7, no. 7, p. 420, 1964, doi: 10.1145/364520.364540.</mixed-citation><mixed-citation xml:lang="en">R. Durstenfeld, “Algorithm 235: Random permutation,” Communications of ACM, vol. 7, no. 7, p. 420, 1964, doi: 10.1145/364520.364540.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, 3rd ed., vol. 2. Addison-Wesley, 1998.</mixed-citation><mixed-citation xml:lang="en">D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, 3rd ed., vol. 2. Addison-Wesley, 1998.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
