Wiener complexity versus the eccentric complexity

Knor, Martin (author), Škrekovski, Riste (author)

Let w$_G$(u) be the sum of distances from u to all the other vertices of G. The Wiener complexity, C$_W$(G), is the number of different values of w$_G$(u) in G, and the eccentric complexity, C$_{ec}$(G), is the number of different eccentricities in G. In this paper, we prove that for every integer c there are infinitely many graphs G such that C$_W$(G) – C$_{ec}$(G) = c. Moreover, we prove this statement using graphs with the smallest possible cyclomatic number. That is, if c ≥ 0 we prove this statement using trees, and if c < 0 we prove it using unicyclic graphs. Further, we prove that C$_{ec}$(G) ≤ 2C$_W$(G) − 1 if G is a unicyclic graph. In our proofs we use that the function w$_G$(u) is convex on paths consisting of bridges. This property also promptly implies the already known bound for trees C$_{ec}$(G) ≤ C$_W$(G). Finally, we answer in positive an open question by finding infinitely many graphs G with diameter 3 such that C$_{ec}$(G) < C$_W$(G).

• Language: English
• Keywords: graph, diameter, Wiener index, transmission, eccentricity
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2021
• Number of pages: 9 str.
• Numbering: Vol. 9, iss. 1, art. 79
• PID: 20.500.12556/RUL-134930
• UDC: 519.17
• ISSN on article: 2227-7390
• DOI: 10.3390/math9010079
• COBISS.SI-ID: 46211331
• Publication date in RUL: 11.02.2022

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 01.01.2021

Secondary language

• Language: Slovenian
• Keywords: graf, diameter, Winerjev indeks, transmisija, ekscentričnost